题意
多组询问，每次给定 (n) ,求：(sum_{i=1}^nlcm(i,n)) 。
- ( m T leq 3 imes 10^4 ,n leq 10^6)。
分析
- 推式子:
[sum_{i=1}^n{frac{in}{gcd(i,n)}}
]
- 枚举 (gcd) :
[nsum_{d|n}{sum_{i=1}^n[gcd(i,n)=d]frac{i}{d}}
]
[nsum_{d|n}{sum_{i=1}^{frac{n}{d}}[iperp frac{n}{d}]i}
]
[nsum_{d|n}{sum_{i=1}^d{[iperp 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
",ans*n);
}
return 0;
}