求 $\sum_{i=1}^{n}\sum_{j=1}^{n}\varphi(gcd(i,j))$ 。
推式子:$\sum_{T=1}^{n}\lfloor{n\over T}\rfloor^2\sum_{d|T}\mu(d)\varphi({n\over d})$ 。
调和级数TLE,所以要想办法线性筛求出后面那个积性函数。
翰爷表示可以这样:记 $H(i)=\sum_{d|i}\mu(d)\varphi({i\over d})$ ,求出 $H(p^a)$ 和 $pw_i$ 表示 $i$ 最小质因子的幂对应的数,然后就可以直接这么求 $H(i)=H({i\over pw_i})H(pw_i)$ 。那么 $H(p^a)$ 分类讨论一下:
$$ H(p^a)= \begin{cases} p-2&a=1\\ (p-1)(p^{a-1}-p^{a-2})&a>1 \end{cases} $$
这样常数稍大但是很无脑啊,感觉挺资瓷的。
#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=10000000;
int te,n,p[maxn+5],pw[maxn+5];bool pri[maxn+5];LL H[maxn+5],ans;
inline void Make(){
pri[0]=pri[1]=true;H[1]=1;
for (int i=2;i<=maxn;i++){
if (!pri[i]) p[++p[0]]=i,pw[i]=i,H[i]=i-2;
for (int j=1,t;j<=p[0]&&(t=(i*p[j]))<=maxn;j++)
if (!(i%p[j])){pw[t]=pw[i]*p[j];
if (t==pw[t]) H[t]=(LL)(p[j]-1)*(i-i/p[j]);
else H[t]=H[t/pw[t]]*H[pw[t]];pri[t]=true;break;
} else pw[t]=p[j],H[t]=H[i]*H[p[j]],pri[t]=true;
}for (int i=1;i<=maxn;i++) H[i]+=H[i-1];
}
int main(){
freopen("program.in","r",stdin);freopen("program.out","w",stdout);
for (Make(),scanf("%d",&te);te;printf("%lld\n",ans),te--){scanf("%d",&n);ans=0;
for (int l=1,r;l<=n;l=r+1) r=n/(n/l),ans+=(H[r]-H[l-1])*(n/l)*(n/l);
}return 0;
}