好吧，确实是个水题，但是网上的题解似乎都不怎么靠谱。
首先我们可以用反演：
∵ Σφ(d)=n (d|n)
∴ Answer(N)=Σ gcd(i,N) (i∈N*∧ i∈[1,N])
=Σ Σ φ(d) (i∈N*∧ i∈[1,N],d|i)
=Σ φ(d)×N/d (d|N)
但这样还不够，复杂度还是O(N)的。
我们可以看到，这其实是函数f(x)=φ(x)与函数g(x)=x的狄利克雷卷积，又因为f与g都是积性函数，所以Answer函数也是积性函数。
所以我们将N分解为p1k1×p2k2 ×···×pnkn
对于每一个pk直接根据公式计算就行了，这样总的复杂度就只有因式分解的O(√n)了（或许可以用其他神奇的算法再降下来呢~）。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <cmath> 6 using namespace std; 7 typedef long long LL; 8 LL N,p,k;//N=p^k 9 inline LL calc() 10 { 11 LL ans=0; 12 for(LL f=1,i=0,num=1;i<=k;i++,num*=p) 13 ans+=f*N/num,f*=i?p:p-1; 14 return ans; 15 } 16 int main(int argc, char *argv[]) 17 { 18 LL Ans=1,n;cin>>n; 19 for(LL i=2;i*i<=n;i++) 20 if(n%i==0) 21 { 22 for(k=0,N=1;n%i==0;k++)n/=i,N*=i; 23 p=i;Ans*=calc(); 24 } 25 if(n>1)N=p=n,k=1,Ans*=calc(); 26 cout<<Ans<<endl; 27 return 0; 28 }
BZOJ2705: [SDOI2012]Longge的问题,布布扣,bubuko.com
原文：http://www.cnblogs.com/zhuohan123/p/3575709.html