﻿ uva 11426-欧拉函数 - 鸿网互联

# uva 11426-欧拉函数

Problem J GCD Extreme (II) 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: HereGCD(i,j) means the greatest common divisor of integeriand integer

Problem J
GCD Extreme (II)
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

##### 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                              Output for Sample Input

 10 100 200000 0 67 13015 143295493160

```#include<stdio.h>
#include<string.h>
#define MAXD 4000010
const int N = 4000000;
typedef long long LL;
int phi[MAXD];
LL a[MAXD];
void prep()
{
memset(a, 0, sizeof(a));
for(int i = 1; i <= N; i ++) phi[i] = i;
for(int i = 2; i <= N; i ++)
{
if(phi[i] == i)
{
for(int j = i; j <= N; j += i)
phi[j] = phi[j] / i * (i - 1);
}
for(int j = 1; j * i <= N; j ++)
a[j * i] += j * phi[i];
}
for(int i = 1; i <= N; i ++) a[i] += a[i - 1];
}
int main()
{
prep();
int n;
while(scanf("%d", &n), n) printf("%lld\n", a[n]);
return 0;
}```

<