# UVa 11426 (欧拉函数 GCD之和) GCD - Extreme (II)

``` 1 #include <cstdio>
2 typedef long long LL;
3
4 const int maxn = 4000000;
5
6 int phi[maxn + 10];
7 LL f[maxn + 10];
8
9 void phi_table()
10 {
11     phi[1] = 1;
12     for(int i = 2; i <= maxn; i++) if(!phi[i])
13         for(int j = i; j <= maxn; j += i)
14         {
15             if(!phi[j]) phi[j] = j;
16             phi[j] = phi[j] / i * (i-1);
17         }
18 }
19
20 int main()
21 {
22     phi_table();
23
24     for(int i = 1; i <= maxn; i++)
25         for(int j = i*2; j <= maxn; j += i)
26             f[j] += i * phi[j / i];
27     for(int i = 3; i <= maxn; i++) f[i] += f[i - 1];
28
29     int n;
30     while(scanf("%d", &n) == 1 && n) printf("%lld\n", f[n]);
31
32     return 0;
33 }```

## UVA 11426 - GCD - Extreme (II) 欧拉函数-数学

Given the value of N, you will have to ?nd the value of G. The de?nition of G is given below:G =i<N∑i=1j∑≤Nj=i+1GCD(i, j)Here GCD(i, j) means the greatest common divisor of integer i and integer j.For those who have trouble understanding summation no

## hdu2588 gcd 欧拉函数

GCD Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1567    Accepted Submission(s): 751 Problem Description The greatest common divisor GCD(a,b) of two positive integers a and b,sometimes writte

## hdoj 1787 GCD Again【欧拉函数】

GCD Again Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2673    Accepted Submission(s): 1123 Problem Description Do you have spent some time to think and try to solve those unsolved problem af