[UVA] 11417 - GCD
Problem A
GCD
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<501). The meaning of N is given in the problem statement. Input is terminated by a line containing a single zero. This zero should not be processed.
Output
For each line of input produce one line of output. This line contains the value of G for corresponding N.
Sample Input Output for Sample Input
|
10 100 500 0
|
67 13015 442011 |
int gcd(int x, int y) {
int tmp;
while(x%y) {
tmp = x, x = y, y = tmp%y;
}
return y;
}
int main() {
int n, i, j;
int ans[501] = {}, map[501][501] = {};
for(i = 1; i < 501; i++) {
for(j = i+1; j < 501; j++) {
map[i][j] = map[i][j-1] + gcd(i, j);
ans[j] += map[i][j];
}
}
while(scanf("%d", &n) == 1 && n) {
printf("%d\n", ans[n]);
}
return 0;
}