B3716题解

· · 题解

一道预处理就行的题

这道题一看感觉很简单，实际上正常的暴力找过不去，因为有这句话：对于全部的测试点，保证 1 \leq T \leq 5 \times 10^5，2 \leq n \leq 10^8

数据既然这么大，那么第一时间想到的肯定是预处理了啊。我们使用一个欧拉筛，把所有的质数都先筛出来，再去做就会节省很多时间了。不会的小伙伴可以先做这道题：线性筛质数。

要注意的是：这道题在筛的时候可以将每一个合数都标记上它是从哪里得到这个标记的，这样每一个需要找的数就可以直接跳回去，不需要质因数分解了。具体实现也很简单，只需要将打标记的这一句话

v[prime[j]*i]=1;

改为

v[prime[j]*i]=prime[j];

就可以知道它是哪来的了。

下面是完整代码

#include<bits/stdc++.h>
using namespace std;
int v[100000010],prime[5770000],cnt,t,n;
int main()
{
    for(int i=2;i<=100000000;i++)
    {
        if(!v[i])
            prime[++cnt]=i;
        for(int j=1;j<=cnt&&(long long)prime[j]*i<=100000000;j++)
        {
            v[prime[j]*i]=prime[j];//标记它是从哪里来的部分
            if(!(i%prime[j]))
                break;
        }
    }//欧拉筛预处理
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        int ans=0;
        if(v[n]==0)
        {
            printf("%d\n",n);
            continue;
        }//如果是质数就直接输出
        while(1)
        {
            if(!v[n])
            {
                ans^=n;
                break;
            }
            ans^=v[n];
            n/=v[n];
        }//不是就从前往后找，每一次都异或一下那个质因数，直到找到一个质数
        printf("%d\n",ans);
    }
    return 0;
}

完结撒花！

注；萌新的第一篇题解，求管理大大给过啊