題目大意：給定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;新聞熱點
疑難解答
