P2398 GCD SUM
题目大意：
求：
\[\sum ^n _{i=1} \sum ^n _{j=1} \gcd(i,j) \]solution：
推一下柿子：
设 \(\gcd(x,y)=1\) 则 \(\gcd(xk,yk)=k\)。
那么原式就变成：
再变为：
\[\sum ^n _{i=1} \times ( (2\times \sum ^{\lfloor n/i\rfloor} _{i=1} \varphi(i))-1) \]可以预处理前缀和：
\[\sum ^{\lfloor n/i\rfloor} _{i=1} \varphi(i) \]所以最后柿子变为：
\[\sum ^n _{i=1} \times (2pre(\lfloor n/i \rfloor ) -1) \]欧拉函数可以通过线性筛来预处理出，同时计算前缀和。
最后时间复杂度：\(O(n)\) 。
细节处理：
不开 \(\text{long long }\) 见祖宗（言简意赅）。
代码
#include<cstdio>
using namespace std;
typedef long long LL;
const int N=1e7+5;
int n;
int phi[N],pr[N],cnt;
LL pre[N];
inline void xxs(){
phi[1]=1,pre[1]=1;
for(int i=2;i<=n;i++){
if(!phi[i]) pr[++cnt]=i,phi[i]=i-1;
pre[i]=pre[i-1]+phi[i];
for(int j=1;j<=cnt;j++){
if(i*pr[j]>n) break;
if(i%pr[j]==0)
phi[i*pr[j]]=phi[i]*pr[j];
else
phi[i*pr[j]]=phi[i]*(pr[j]-1);
}
}
}
int main(){
scanf("%d",&n);
xxs();
LL ans=0;
for(int i=1;i<=n;i++)
ans+=(pre[n/i]*2-1)*i;
printf("%lld",ans);
return 0;
}