%你赛打到一半来写个题解
link：疯狂lcm
题意，求：
\[\sum_{i=1}^{n}lcm(i,n)
\]
不多说废话，直接开推：
\[\begin{aligned}
&=n\sum_{i=1}^{n}\frac{i}{gcd(i,n)}\\
&=n\sum_{d\mid n}\sum_{i=1}^{n}\frac{i}{d}[gcd(i,n)=d]\\
&=n\sum_{d\mid n}\sum_{i=1}^{n}\frac{i}{d}[gcd(\frac{i}{d},\frac{n}{d})=1]\\
&=n\sum_{d\mid n}\sum_{i=1}^{\frac{n}{d}}i[gcd(i,\frac{n}{d})=1]\\
\end{aligned}
\]
我们发现这个 \(\frac{n}{d}\) 实际上还是枚举的 \(d\)，那我们来直接替换：
\[n\sum_{d\mid n}\sum_{i=1}^{d}i[gcd(i,d)=1]
\]
那么后边这个 \(\sum_{i=1}^{d}i[gcd(i,d)=1]\) 实际上就是小于 \(d\) 且与 \(d\) 互质的数的和，这玩意就等于 \(\frac{\varphi(n)\times n}{2}\)，证明如下：
由于更相减损法 \(gcd(n,x)=gcd(n,n-x)\) 可知，所有与 \(n\) 互质的数都是成对出现的，每一对的和为 \(n\)，一共有 \(\frac{\varphi(n)}{2}\) 对，那么和为 \(\frac{\varphi(n)\times n}{2}\)，当然要在 \(n>1\) 的条件下满足。
那么原式即变为：
\[n\sum_{d\mid n}\frac{\varphi(d)\times d}{2}
\]
但是如果 \(d=1\) 上式变为 \(0\)，就不成立了，因此 \(d=1\) 的时候特判一下就好。
容易发现这是一个 \(\Theta(\sqrt{n})\) 的算法，优化一下，设 \(f(n)=\sum_{d\mid n}\varphi(d)\times d\)，也就是 \(1*(\varphi(n)\times n)\)，它显然是个积性函数，那可以考虑用个筛子筛一下，很容易将复杂度降到 \(\log n\) 级别。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int n,T;
int prim[N],phi[N],f[N];
void init(){
phi[1]=1;
for(int i=2;i<=N;++i){
if(!phi[i]) prim[++prim[0]]=i,phi[i]=i-1;
for(int j=1;j<=prim[0]&&i*prim[j]<=N;++j){
if(!(i%prim[j])){
phi[i*prim[j]]=prim[j]*phi[i];
break;
}else phi[i*prim[j]]=(prim[j]-1)*phi[i];
}
}
for(int i=1;i<=N;++i)
for(int j=i;j<=N;j+=i) f[j]+=(i==1)?1:(phi[i]*i/2);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
init();
cin>>T;
while(T-->0){
cin>>n;
cout<<f[n]*n<<'\n';
}
return 0;
}