[SDOI2012]Longge的问题 [SDOI2012]Longge的问题
BZOJ
luogu
考虑n的每个约数的贡献
求[1,n]有多少i与gcd(i,n)=k
即求$$sum_{k|n}ksum_{i=1}^n[gcd(i,n)=k]$$
[=sum_{k|n}ksum_{i=1}^{frac{n}{k}}[gcd(i,frac{n}{k})=1]
]
[=sum_{k|n}kphi(k)
]
由于k|n,所以预处理n的不同质因子,可以做到(O(logn))求(phi(k))
复杂度:(O(sqrt nlogn))
#define ll long long
#include<bits/stdc++.h>
using namespace std;
int cnt;
ll n,ans,z[100000];
void fact(ll x){
for(int i=2,sq=sqrt(x);i<=sq;i++){
if(x%i==0){
z[++cnt]=i;
while(x%i==0)x/=i;
}
}
if(x>1)z[++cnt]=x;
}
ll getphi(ll x){
ll res=x;
for(int i=1;i<=cnt;i++)
if(x%z[i]==0){
res/=z[i];res*=z[i]-1;
while(x%z[i]==0)x/=z[i];
}
if(x>1)res/=x,res*=x-1;
return res;
}
int main(){
cin>>n;
fact(n);
for(int i=sqrt(n);i>=1;i--)
if(n%i==0){
ans+=getphi(n/i)*i;
if(i*i^n)ans+=getphi(i)*n/i;
}
cout<<ans<<endl;
return 0;
}