题目大意：给定n，求1到n中所有数与n的lcm之和 题解：枚举d=GCD(i,n),令F(n)为n以内与n互质的数之和，则ans=Σ（d|n）d*F(d)*n/d=nΣF(d) F(d)有一个性质，就是与d互质的数一定能两两组合成d，可以用辗转相除法轻松证明，只有1和2特殊，特判即可。
#include<cstdio>#include<cstdlib>#include<iostream>#include<iomanip>#include<ctime>#include<cmath>#include<cstring>#include<string>#include<algorithm>using namespace std;int n;long long f[1010000];bool pd[1010000];int my_stack[1010000];int top=0;void shai(){ f[1]=1; for(int i=2;i<=1000000;i++) { if(!pd[i]) { my_stack[++top]=i; f[i]=i-1; } for(int j=1;i*my_stack[j]<=1000000;j++) { pd[i*my_stack[j]]=true; if(i%my_stack[j]==0) { f[i*my_stack[j]]=f[i]*my_stack[j]; break; } f[i*my_stack[j]]=f[i]*(my_stack[j]-1); } } //for(int i=2;i<=1000000;i++) f[i]=i*f[i]/2;}inline long long F(int x){ if(x==1) return 1; return f[x]*x/2;}int main(){ //freopen("a.in","r",stdin); //freopen("a.out","w",stdout); int T; scanf("%d",&T); shai(); while(T--) { scanf("%d",&n); long long ans=0; int i; for(i=1;i*i<n;i++) { if(n%i==0) { ans+=F(i); ans+=F(n/i); } } if(i*i==n) ans+=f[i]*i/2; PRintf("%lld",ans*n); printf("/n"); } return 0;}新闻热点
疑难解答
