题解
1.数组最大能开到1e8
2.vector比数组容易mle
3.筛素数的时间复杂度是O(n)
4.由于一个数最多有 \(log_2(n)\) 个因子,我们标记每一个合数的最小质因子,然后直接除就行(递归思想?)
code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<ll> prime;
int vis[100000005]={0};
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
for(ll k=2;k<=1e8+4;k++)
{
if(!vis[k]) prime.push_back(k);
for(ll i=0;i<prime.size()&&prime[i]*k<=1e8+2;i++)
{
vis[k*prime[i]]=prime[i];
if(k%prime[i]==0) break;
}
}
ll t;
cin>>t;
while(t--)
{
ll n;
cin>>n;
ll ans=0;
while(vis[n])
{
ans^=vis[n];
n/=vis[n];
}
ans^=n;
cout<<ans<<"\n";
}
return 0;
}
标签:int,cout,B3716,ll,vis,因子,分解,ans
From: https://www.cnblogs.com/pure4knowledge/p/18177147