UVa 11426

首先我们了解一下欧拉函数phi[x],phi[x]表示的是不超过x且和x互素的整数个数

phi[x]=n*(1-1/p1)*(1-1/p2)....(1-1/pn);

计算欧拉函数的代码为

 1 int euler_phi(int n){
 2     int m=(int)sqrt(n+0.5);
 3     int ans=n;
 4     for(int i=2;i*i<=m;i++){
 5         if(n%i==0){//
 6             ans=ans/i*(i-1);
 7             while(n%i==0)n=n/2;
 8         }
 9     }
10     if(n>1)ans=ans/n*(n-1);
11     return ans;
12 }

也可以通过类似于素数打表的方法来对欧拉函数进行打表

 1 void phi_table(int n){
 2     for(int i=2;i<=n;i++)phi[i]=0;
 3     phi[1]=1;
 4     for(int i=2;i<=n;i++){
 5         if(phi[i]==0)
 6         for(int j=i;j<=n;j=j+i){
 7             if(phi[j]==0)phi[j]=j;
 8             phi[j]=phi[j]/i*(i-1);
 9         }
10     }
11 }

题意

Given the value of N, you will have to find the value of G. The definition of G is given below:

Here GCD(i,j) means the greatest common divisor of integer i and integer j.

For those who have trouble understanding summation notation, the meaning of G is given in the following code:

G=0;

for(i=1;i<N;i++)

for(j=i+1;j<=N;j++)

{

G+=gcd(i,j);

}

/*Here gcd() is a function that finds the greatest common divisor of the two input numbers*/

Input

The input file contains at most 100 lines of inputs. Each line contains an integer N (1<N<4000001). The meaning of N is given in the problem statement. Input is terminated by a line containing a single zero.

Output

For each line of input produce one line of output. This line contains the value of G for the corresponding N. The value of G will fit in a 64-bit signed integer.

Sample Input

10
100
200000
0

Sample Output

67
13015
143295493160

设f(n)=gcd(1,2)+gcd(1,3)+gcd(2,3)+....+gcd(n-1,n); 题意是求1<=i<j<=n的数对（i,j）所对应的gcd(i,j)的和s(j)

s(n)=f(1)+f(2)+f(3)+f(4)+....f(n);

当i为n的约数的时候

我们选择t(i)表示gcd(x,n)=i(x<n)的正整数的个数则f(n)=sum{i*t(i)}

gcd(x,n)=i<==>gcd(x/i,n/i)=1;

满足下t(i)为phi[n/i];(感觉还是可以理解的）

在代码实现中，如果枚举（1-n）的约数的话明显效率慢，所以我们可以枚举i的倍数来更新f(n);

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<queue>
 7 #include<map>
 8 #include<set>
 9 #include<vector>
10 #include<cstdlib>
11 #include<string>
12 #define eps 0.000000001
13 typedef long long ll;
14 typedef unsigned long long LL;
15 using namespace std;
16 const int N=4000000+100;
17 ll S[N],f[N];
18 ll phi[N];
19 ll euler_phi(int n){
20     int m=(int)sqrt(n+0.5);
21     ll ans=n;
22     for(int i=2;i*i<=m;i++){
23         if(n%i==0){//2一定是素因子
24             ans=ans/i*(i-1);
25             while(n%i==0)n=n/2;
26         }
27     }
28     if(n>1)ans=ans/n*(n-1);
29     return ans;
30 }
31 void phi_table(int n){
32     for(int i=2;i<=n;i++)phi[i]=0;
33     phi[1]=1;
34     for(int i=2;i<=n;i++){
35         if(phi[i]==0)
36         for(int j=i;j<=n;j=j+i){
37             if(phi[j]==0)phi[j]=j;
38             phi[j]=phi[j]/i*(i-1);
39         }
40     }
41 }
42 void init(){
43     int n=N;
44     phi_table(N);
45     memset(f,0,sizeof(f));
46     for(int i=1;i<=n;i++){
47         for(int j=i*2;j<=n;j=j+i)f[j]=f[j]+i*phi[j/i];
48     }
49     memset(S,0,sizeof(S));
50     S[2]=f[2];
51     for(int i=3;i<=n;i++)S[i]=S[i-1]+f[i];
52 }
53 int main(){
54     int n;
55     init();
56     while(scanf("%d",&n)!=EOF){
57         //init(n);
58         if(n==0)break;
59         printf("%lld
",S[n]);
60     }
61 }