题意
多组询问，每次给定 \(n\) ,求：\(\sum_{i=1}^nlcm(i,n)\) 。
- \(\rm T \leq 3\times 10^4\ ,n \leq 10^6\)。
分析
- 推式子:
\[\sum_{i=1}^n{\frac{in}{gcd(i,n)}}
\]
- 枚举 \(gcd\) :
\[n\sum_{d|n}{\sum_{i=1}^n[gcd(i,n)=d]\frac{i}{d}}
\]
\[n\sum_{d|n}{\sum_{i=1}^{\frac{n}{d}}[i\perp \frac{n}{d}]i}
\]
\[n\sum_{d|n}{\sum_{i=1}^d{[i\perp d]i}}
\]
-
对于后面的求和可以看成函数 \(f_d\) ,表示所有和 \(d\) 互质的数字之和。
-
根据辗转相减可以得到 \(gcd(i,d)=gcd(d-i,d)\) ,表明所有与 \(d\) 互质的数字可以两两配对得到 \(d\) 。
-
所以 \(f_d=\frac{\varphi(d)*d}{2}\) 。
-
处理 \(\varphi\) 的时间 \(O(n)\) 加上单次处理的时间 \(O(\sqrt n)\),总时间复杂度为 \(O(2n)\) 。
技巧：辗转相减的使用
代码
#include<bits/stdc++.h>
using namespace std;
#define go(u) for(int i=head[u],v=e[i].to;i;i=e[i].last,v=e[i].to)
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define pb push_back
typedef long long LL;
inline int gi(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
return x*f;
}
template<typename T>inline bool Max(T &a,T b){return a<b?a=b,1:0;}
template<typename T>inline bool Min(T &a,T b){return b<a?a=b,1:0;}
const int N=1e6 + 7;
int T,pric,n;
int phi[N],pri[N],vis[N];
LL f[N];
void pre(int Num){
phi[1]=1;int to;
for(int i=2;i<=Num;++i){
if(!vis[i]) { phi[i]=i-1,pri[++pric]=i;}
for(int j=1;j<=pric&&(to=i*pri[j])<=Num;++j){
vis[to]=1;
if(i%pri[j]==0){
phi[to]=phi[i]*pri[j];
break;
}
phi[to]=phi[i]*phi[pri[j]];
}
}
}
int main(){
T=gi();
pre(1000000);
f[1]=1;
for(int i=2;i<=1000000;++i) f[i]=1ll*phi[i]*i/2;
while(T--){
n=gi();LL ans=0;
int l=1,r=1000;
while(l<r){
int mid=l+r+1>>1;
if(mid*mid<=n) l=mid;
else r=mid-1;
}
for(int i=1;i<=l;++i)if(n%i==0){
ans+=f[i];
if(i*i!=n)
ans+=f[n/i];
}
printf("%lld\n",ans*n);
}
return 0;
}
