Description
给定数字\(n\)（\(n\le 10^7\))，求：
\[\sum_{i=1}^n\sum_{j=1}^n\varphi(\gcd(i,j))
\]
\]
多组数据输入，数据组数\(T\le5000\)。
Solution
简单的一题，直接推导：
\[\begin{aligned}
\sum_{i=1}^n\sum_{j=1}^n\varphi(\gcd(i,j))&=\sum_{d=1}^n\varphi(d)\sum_{i=1}^{\lfloor \frac n d\rfloor}\sum_{j=1}^{\lfloor \frac n d\rfloor}[\gcd(i,j)==1]\\
&=\sum_{d=1}^n\varphi(d)(2\sum_{i=1}^{\lfloor \frac n d\rfloor}\varphi(i)-1)
\end{aligned}
\]
\sum_{i=1}^n\sum_{j=1}^n\varphi(\gcd(i,j))&=\sum_{d=1}^n\varphi(d)\sum_{i=1}^{\lfloor \frac n d\rfloor}\sum_{j=1}^{\lfloor \frac n d\rfloor}[\gcd(i,j)==1]\\
&=\sum_{d=1}^n\varphi(d)(2\sum_{i=1}^{\lfloor \frac n d\rfloor}\varphi(i)-1)
\end{aligned}
\]
发现后面一个括号带下取整，直接求出\(\varphi\)的前缀和，数论根号分块即可。
Code
#include <cstdio>
using namespace std;
typedef long long ll;
const int N=10000001;
bool vis[N];
int p[N],pcnt;
ll phi[N];
void sieve(){
phi[1]=1;
for(int i=2;i<N;i++){
if(!vis[i]){
p[++pcnt]=i;
phi[i]=i-1;
}
for(int j=1;j<=pcnt&&i*p[j]<N;j++){
int x=i*p[j];
vis[x]=true;
if(i%p[j]==0){
phi[x]=phi[i]*p[j];
break;
}
phi[x]=phi[i]*(p[j]-1);
}
}
for(int i=2;i<N;i++) phi[i]+=phi[i-1];
}
int main(){
sieve();
int T,n;
ll ans;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
ans=0;
for(int i=1,j;i<=n;i=j+1){
j=n/(n/i);
ans+=(2LL*phi[n/i]-1)*(phi[j]-phi[i-1]);
}
printf("%lld\n",ans);
}
return 0;
}