B3716 题解
听取MLE声一片
·
·
题解
为了保证黄题通过量恰好为 154 水一道黄题。
首先我们知道，对于一个数 n，最多只有一个大于 \sqrt n 的质因子。
证明的话，考虑反证，如果有两个大于的它们的乘积必然大于 n。
所以只需要处理不大于 \sqrt n 的质因数即可，把不大于的质因数全部除掉剩下的必然是大于 n 的质因子。
先考虑暴力的做法，从 2 开始枚举到 \sqrt n，枚举到 x，如果 n 是 x 的倍数，就把 n 不断除以 x，直到 n 不再是 x 的倍数。
这里的正确性，因为一个合数一定比它的质因数要大，所以合数是不会起作用的。
然而这样时间复杂度单次最差是 O(\sqrt x)，不能通过。
我们知道一个大小为 n 的数为素数的概率大约为 $\dfrac{1}{\ln n}
所以我们写一个筛法把前 $10^4$ 个素数筛出来然后把从 $2$ 到 $\sqrt n$ 的素数全跑一遍即可，时间复杂度为 $O(T\dfrac{\sqrt n}{\ln n})$，可以通过。
```
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int N=1e4+10;
int n,prime[N],vis[N],cnt;
int main()
{
for(int i=2;i<N;i++){
if(vis[i])
continue;
prime[++cnt]=i;
for(int j=i+i;j<N;j+=i)
vis[j]=1;
}
int T=read();
while(T--){
int n=read(),res=0;
for(int i=1;i<=cnt&&prime[i]<=sqrt(n);i++){
while(n%prime[i]==0){
n/=prime[i];
res^=prime[i];
}
}
if(n!=1)
res^=n;
printf("%d",res);
putchar('\n');
}
return 0;
}
```