/onlineJudge/questionCode.html#!problemId=1594
参考及详细推导：/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}{d}}\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。 +
+欢迎访问我的博客：/luyouqi233/ +
+++++++++++++++++++++++++++++++++++++++++++
