poj2480 Longge's problem(数论/欧拉函数性质 gcd求和)
题目
对于N(1<N<(1<<31)),求
思路来源
https://blog.****.net/AgoniAngel/article/details/51308742
https://blog.****.net/wmn_wmn/article/details/7733874
题解
枚举因数d即可,可以同时统计d和n/d的贡献,把复杂度降到
心得
自己板子抄多了都不会写精简代码了
其实这题在线求Eular值然后在线求约数都可以
对于每个n,这样的复杂度是的,
通过足矣,还很省内存
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
bool ok[maxn];
ll prime[maxn],phi[maxn],cnt;
vector<ll>ans;
ll n,v;
void sieve()
{
phi[1]=1;
for(ll i=2;i<maxn;++i)
{
if(!ok[i])
{
prime[cnt++]=i;
phi[i]=i-1;
}
for(int j=0;j<cnt;++j)
{
if(i*prime[j]>=maxn)break;
ok[i*prime[j]]=1;
if(i%prime[j]==0)
{
phi[i*prime[j]]=phi[i]*prime[j];//prime[j]是i的因子 prime[j]的素因子项包含在i的素因子项里
break;
}
else phi[i*prime[j]]=phi[i]*(prime[j]-1);//prime[j]与i互质 phi[i*prime[j]=phi[i]*phi[prime[j]]
}
}
}
ll getphi(ll x)
{
if(x<maxn)return phi[x];
//if(p[x])return p[x];
ll ans=x;
for(int i=0;i<cnt;++i)
{
if(prime[i]*prime[i]>x)break;
if(x%prime[i]==0)
{
ans/=prime[i];
ans*=(prime[i]-1);
while(x%prime[i]==0)
x/=prime[i];
}
}
if(x>1)ans/=x,ans*=x-1;
return ans;
}
vector<ll>divisor(ll x)
{
vector<ll>res;
for(ll i=1;i*i<=x;++i)
{
if(x%i==0)
{
res.push_back(i);
if(i!=x/i)res.push_back(x/i);
}
}
return res;
}
int main()
{
sieve();
while(~scanf("%lld",&n))
{
v=0;
ans=divisor(n);
int len=ans.size();
for(int i=0;i<len;++i)
{
ll d=ans[i];
v+=getphi(n/d)*d;
}
printf("%lld\n",v);
}
return 0;
}