BZOJ2705: [SDOI2012]Longge的问题

好吧，确实是个水题，但是网上的题解似乎都不怎么靠谱。

首先我们可以用反演：

(egin{align*}ecause sum_{d|n} phi(d) &= n \ herefore Answer(N)&=sum_{i=1}^N gcd(i,N) \&=sum_{i=1}^N sum_{d|i}phi(d)\&=sum_{d|N} phi(d) imes frac{N}{d}end{align*} )

但这样还不够，复杂度还是(O(N))的。

我们可以看到，这其实是函数(f(x)=phi(x))与函数(g(x)=x)的狄利克雷卷积，又因为(f)与(g)都是积性函数，所以(Answer)函数也是积性函数。

所以我们将(N)分解为(p_1^{k_1} imes p_1^{k_1} imesldots imes p_m^{k_m})

对于每一个(p^k)直接根据公式计算就行了，这样总的复杂度就只有因式分解的(O(sqrt{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 }