Constraints
1 <= T <= 300000
1 <= n <= 1000000
$\sum_{i=1}^{n}lcm(i,n)$
$=\sum_{i=1}^{n}\frac{i\times n}{gcd(i,n)}$
$=\frac{1}{2}(\sum_{i=1}^{n-1}\frac{i\times n}{gcd(i,n)}+\sum_{i=n-1}^{1}\frac{i\times n}{gcd(i,n)})+n$
因为$gcd(a,b)=gcd(a-b,b)$，所以上面的两个$\sum$可以合起来。
$=\frac{1}{2}\sum_{i=1}^{n-1}\frac{n^2}{gcd(i,n)}+n$
设$gcd(i,n)=d$，把式子改为枚举$d$,那么与$n$的$gcd$为$d$的数有$φ(\frac{n}{d})$个。
$=\frac{1}{2}\sum_{d|n}\frac{n^2\times φ(\frac{n}{d})}{d}+n$
设$d‘=\frac{n}{d}$，上下约分一下
$=\frac{1}{2}\sum_{d‘|n}d‘\times φ(d‘)+n$
预处理出$φ$数组，然后枚举每一个约数去计算它对它所有倍数的贡献，复杂度是调和级数的$O(nlogn)$。
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #define N (1000009) 5 #define MAX (1000000) 6 #define LL long long 7 using namespace std; 8 9 inline int read() 10 { 11 int x=0,w=1; char c=getchar(); 12 while (c<‘0‘ || c>‘9‘) {if (c==‘-‘) w=-1; c=getchar();} 13 while (c>=‘0‘ && c<=‘9‘) x=x*10+c-‘0‘, c=getchar(); 14 return x*w; 15 } 16 17 LL T,n,cnt,phi[N],ans[N],vis[N],prime[N]; 18 19 void Preprocess() 20 { 21 phi[1]=1; 22 for (int i=2; i<=MAX; ++i) 23 { 24 if (!vis[i]) prime[++cnt]=i, phi[i]=i-1; 25 for (int j=1; j<=cnt && i*prime[j]<=MAX; ++j) 26 { 27 vis[i*prime[j]]=1; 28 if (i%prime[j]) phi[i*prime[j]]=phi[i]*(prime[j]-1); 29 else {phi[i*prime[j]]=phi[i]*prime[j]; break;} 30 } 31 } 32 for (int i=1; i<=MAX; ++i) 33 for (int j=i; j<=MAX; j+=i) 34 ans[j]+=i*phi[i]/2; 35 for (int i=1; i<=MAX; ++i) ans[i]=ans[i]*i+i; 36 } 37 38 int main() 39 { 40 Preprocess(); 41 T=read(); 42 while (T--) n=read(), printf("%lld\n",ans[n]); 43 }
原文：https://www.cnblogs.com/refun/p/10371410.html