BZOJ2705: [SDOI2012]Longge的问题

Portal

求 ∑ni=1gcd(i,n) 对于 1<=i<=n ， gcd(i,n) 只可能会是 n 的因数。 然后就考虑每一个因数对答案的贡献，也就是算有多少个i满足 gcd(i,n) 为这个因数。 因为 gcd(m,n)=k ,所以 gcd(m/k,n/k)=1 . 那么我们枚举每一个因数，令为 fac[i] ， ans=∑sumfaci=1fac[i]∗phi(n/fac[i])

【代码】

#include <iostream> #include <cstdio> #include <algorithm> #define N 10000005 #define mod 1000000007 #define INF 0x7fffffff using namespace std; typedef long long ll; typedef pair<int,int> pa; ll read() { ll x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();} while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } ll n,ans; ll phi(ll x) { ll rtn=x; for(ll i=2;i*i<=x;i++) { if(x%i==0) { rtn=rtn/i*(i-1); while(x%i==0) x/=i; } } if(x!=1) rtn=rtn/x*(x-1); return rtn; } void Solve() { ll i; for(i=1;i*i<n;i++) { if(n%i==0) { ans+=i*phi(n/i); ans+=(n/i)*phi(i); } } if(i*i==n) ans+=i*phi(i); printf("%lld\n",ans); } int main() { n=read(); Solve(); return 0; }