bzoj 2226: [Spoj 5971] LCMSum线性筛欧拉函数

题目大意：给定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; }