http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1594

參考及詳細推導：http://www.cnblogs.com/rir1715/p/8584083.html

設\(cnt_i=\sum_{j=1}^n[\phi(j)==i]\)，這個可以在\(O(n)\)處理出來。

我們用它把\(\phi(i)\phi(j)\)換元得：

\(\sum_{i=1}^n\sum_{j=1}^n\phi(gcd(i,j))\times cnt_i\times cnt_j\)

\(=\sum_{d=1}^n\phi(d)\sum_{i=1}^n\sum_{j=1}^n[gcd(i,j)==d]\times cnt_i\times cnt_j\)

好的最難的部分已經過去了，隨著一陣套路，這個式子索然無味。

\(=\sum_{d=1}^n\phi(d)\sum_{d'=1}^n\mu(d')(\sum_{i=1}^{\frac{n}{dd^`}}cnt_{idd'})^2\)

令\(sum(t)=\sum_{i=1}^{\frac{n}{t}}cnt_{it}\)，這個可以在\(O(nlogn)\)處理出來（調和級數）。

式子

\(=\sum_{d=1}^n\phi(d)\sum_{d'=1}^n\mu(d')sum(dd')^2\)

然后我們發現當\(dd'>n\)時\(sum(dd')=0\)，所以我們\(d'\)不需要枚舉那么多，所以最終的式子為：

\(\sum_{d=1}^n\phi(d)\sum_{d'=1}^{\frac{n}ze8trgl8bvbq}\mu(d')sum(dd')^2\)

這個式子可以在\(O(nlogn)\)運算（調和級數）。

#include<map> #include<cmath> #include<stack> #include<queue> #include<cstdio> #include<cctype> #include<vector> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int N=2e6+5; inline int read(){int X=0,w=0;char ch=0;while(!isdigit(ch)){w|=ch=='-';ch=getchar();}while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } bool he[N]; int su[N],tot; ll phi[N],mu[N],cnt[N],sum[N]; void Euler(int n){phi[1]=mu[1]=1;for(int i=2;i<=n;i++){if(!he[i]){su[++tot]=i;phi[i]=i-1;mu[i]=-1;}for(int j=1;j<=tot&&i*su[j]<=n;j++){int p=su[j];he[i*p]=1;if(i%p==0){mu[i*p]=0;phi[i*p]=phi[i]*p;break;}else{mu[i*p]=mu[i]*mu[p];phi[i*p]=phi[i]*phi[p];}}} } int main(){Euler(N-5);int t=read();while(t--){memset(cnt,0,sizeof(cnt));memset(sum,0,sizeof(sum));int n=read();for(int i=1;i<=n;i++)cnt[phi[i]]++;for(int i=1;i<=n;i++)for(int j=1;j<=n/i;j++)sum[i]+=cnt[i*j];for(int i=1;i<=n;i++)sum[i]*=sum[i];ll ans=0;for(int i=1;i<=n;i++)for(int j=1;j<=n/i;j++)ans+=phi[i]*mu[j]*sum[i*j];printf("%lld\n",ans);}return 0; }

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。 　　　　　　　　　　　　　　+

+歡迎訪問我的博客：http://www.cnblogs.com/luyouqi233/ +

+++++++++++++++++++++++++++++++++++++++++++

轉載于:https://www.cnblogs.com/luyouqi233/p/9158444.html

總結

以上是生活随笔為你收集整理的51NOD 1594：Gcd and Phi——题解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。