Description

Given n, calculate the sum LCM(1,n) + LCM(2,n) + .. + LCM(n,n), where LCM(i,n) denotes the Least Common Multiple of the integers i and n.

 

题解

 

代码

 1 #include <cstdio>
 2 #include <iostream>
 3 #define N 1000010
 4 #define ll long long
 5 using namespace std;
 6 ll T,bz[N],phi[N],q[N],ans[N];
 7 int main()
 8 {
 9     scanf("%lld",&T),phi[1]=1;
10     for (ll i=2;i<=N;i++)
11     {
12         if (!bz[i]) q[++q[0]]=i,phi[i]=i-1;
13         for (ll j=1;j<=q[0]&&i*q[j]<=N;j++)
14             if (i*q[j]<N)
15             {
16                 bz[i*q[j]]=1;
17                 if (i%q[j]==0) { phi[i*q[j]]=phi[i]*q[j]; break; }
18                 phi[i*q[j]]=phi[i]*(q[j]-1);
19             }
20     }
21     for (int i=1;i<=N;i++) for (int j=1;i*j<=N;j++) ans[i*j]+=j*phi[j]/2;
22     for (ll i=1;i<=N;i++) ans[i]=i*ans[i]+i;
23     for (ll i=1,x;i<=T;i++) scanf("%lld",&x),printf("%lld\n",ans[x]);
24 }