%你赛打到一半来写个题解
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;
}