自动搬运

查看原文

来自洛谷，原作者为

	EurekaStriker 终于蓝√了，今年NOIP打得不好就AFO，进不了省队也AFO，国赛打不好也AFO，反正就是AFO，这bydOI不学了去搞伞兵文化课

搬运于2025-08-24 21:14:35，当前版本为作者最后更新于2023-02-23 17:44:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一道预处理就行的题

这道题一看感觉很简单，实际上正常的暴力找过不去，因为有这句话：对于全部的测试点，保证 $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;
}

完结撒花！

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