UVa10426

Input: Standard Input Output:

Standard Output

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

Output for Sample Input

67 13015 143295493160

Problemsetter: Shahriar Manzoor

Special Thanks: Syed Monowar Hossain

/* 【题意】

求sum(gcd(i,j),1<=i<j<=n)1<n<4000001

【题解】 1.建立递推关系，s(n)=s(n-1)+gcd(1,n)+gcd(2,n)+……+gcd(n-1,n);

2.设f(n)=gcd(1,n)+gcd(2,n)+……+gcd(n-1,n)。

gcd(x,n)=i是n的约数（x<n），按照这个约数进行分类。设满足gcd（x,n）=i的约束有g(n,i)个，则有f(n)=sum(i*g(n,i))。

而gcd(x,n)=i等价于gcd(x/i,n/i)=1，因此g(n,i)等价于phi(n/i).phi(x)为欧拉函数。

3.降低时间复杂度。用筛法预处理phi[x]表

用筛法预处理f(x)->枚举因数，更新其所有倍数求解。

/* 欧拉函数的应用，以后看到互质的数第一个就要想到欧拉函数。今天又学到了好多家伙。欧拉定理：欧拉定理表明，若n,a为正整数，且n,a互质，(a,n) = 1，则a^φ(n) ≡ 1 (mod n) 费马小定理：且(a,p)=1，那么 a^(p-1) ≡1（mod p）假如p是质数，且a,p互质，那么 a的(p-1)次方除以p的余数恒等于1 */

  1 //1285ms
  2 
  3 #include<stdio.h>
  4 #include<string.h>
  5 #include<algorithm>
  6 #include<math.h>
  7 #include<queue>
  8 #include<set>
  9 #include<vector>
 10 #include<bitset>
 11 using namespace std;
 12 typedef long long ll;
 13 
 14 const int M=4000010;
 15 int phi[M];
 16 ll s[M],f[M];//f[n]=sum(phi[i]*j)    (i*j=n) (去掉n*phi[1],因为gcd（n,n）不符合题意！！)
 17 
 18 int get(){
 19     char c;
 20     int res=0;
 21     while(c=getchar(),!isdigit(c));
 22     do{
 23         res=(res<<3)+(res<<1)+(c-'0');
 24     }while(c=getchar(),isdigit(c));
 25     return res;
 26 }
 27 
 28 
 29 void phi_table()//类似素数刷表！！ 
 30 {
 31     phi[1]=1;
 32     for(int i=2;i<M;i++)phi[i]=i;    
 33     for(int i=2;i<M;i+=2)phi[i]/=2;    
 34     for(int i=3;i<M;i+=2)
 35     if(phi[i]==i)//说明i是素数！！！ 
 36     for(int j=i;j<M;j+=i)
 37     {
 38         phi[j]-=phi[j]/i;//保证i是素数且是j的素因子！！！ 
 39     }
 40 }  
 41 
 42 int main()
 43 {
 44     int n,i,j,k;
 45     phi_table();
 46     memset(f,0,sizeof(f));
 47     phi[1]=0;
 48     for(i=1;i<(int)sqrt(M);i++)
 49     {
 50         f[i*i]+=phi[i]*i;
 51         for(n=i*i+i;n<M;n+=i)
 52         f[n]+=(ll)(i*phi[n/i]+n/i*phi[i]);//之前令phi[1]=0；因为gcd(n,n)不符合题意！！ 
 53     }        
 54     s[2]=1;
 55     for( n=3;n<M;n++)    s[n]=s[n-1]+f[n];
 56     while(1)
 57     {
 58         n=get();
 59         if(n==0)break;
 60         printf("%lld
",s[n]);
 61     }
 62     return 0;
 63 }
 64 
 65 
 66 
 67 
 68 
 69 //2382ms
 70 #include<stdio.h>
 71 #include<string.h>
 72 #include<algorithm>
 73 #include<math.h>
 74 #include<queue>
 75 #include<set>
 76 #include<vector>
 77 #include<bitset>
 78 using namespace std;
 79 typedef long long ll;
 80 
 81 const ll M=4000010;
 82 ll phi[M];
 83 ll s[M],f[M];
 84 
 85 void phi_table()//类似素数刷表！！ 
 86 {
 87     phi[1]=1;
 88     for(int i=2;i<M;i++)phi[i]=i;    
 89     for(int i=2;i<M;i+=2)phi[i]/=2;    
 90     for(int i=3;i<M;i+=2)

 91     if(phi[i]==i)//说明i是素数！！！ 
 92     for(int j=i;j<M;j+=i)
 93     {
 94         phi[j]-=phi[j]/i;//保证i是素数且是j的素因子！！！ 
 95     }
 96 }  
 97 int main()
 98 {
 99     phi_table();
100     memset(f,0,sizeof(f));
101     for(int i=1;i<M;i++)
102     for(int n=i+i;n<M;n+=i)
103         f[n]+=i*phi[n/i];
104     s[2]=1;
105     for(int n=3;n<M;n++)    s[n]=s[n-1]+f[n];
106     int n;
107     while(scanf("%d",&n)==1&&n)
108     {
109         printf("%lld
",s[n]);
110     }
111     return 0;
112 }
113 
114 
115 
116 
117 
118 #include<stdio.h>
119 #include<string.h>
120 #include<algorithm>
121 #include<math.h>
122 #include<queue>
123 #include<set>
124 #include<vector>
125 #include<bitset>
126 using namespace std;
127 typedef long long ll;
128 
129 const ll M=4100000;
130 ll phi[2*M];
131 ll s[M],f[M];
132 
133 void phi_table()//类似素数刷表！！ 
134 {
135     for(int i=2;i<=M;i++)phi[i]=0;
136     phi[1]=1;
137     for(int i=2;i<=M;i++)
138     if(!phi[i])//说明i是素数！！！ 
139     for(int j=i;j<=M;j+=i)
140     {
141         if(!phi[j])phi[j]=j;
142         phi[j]=phi[j]/i*(i-1);//保证i是素数且是j的素因子！！！ 
143     }
144 }  
145 int main()
146 {
147     phi_table();
148     memset(f,0,sizeof(f));
149     for(int i=1;i<=M;i++)
150     for(int n=i+i;n<=M;n+=i)
151         f[n]+=i*phi[n/i];
152     s[2]=1;
153     for(int n=3;n<=M;n++)    s[n]=s[n-1]+f[n];
154     int n;
155     while(scanf("%d",&n)==1&&n)
156     {
157         printf("%lld
",s[n]);
158     }
159     return 0;
160 }

View Code