Problem H
GCD Extreme
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*/ |
The input file contains at most 20000 lines of inputs. Each line contains an integer N (1<N<200001). The meaning of N is given in the problem statement. Input is terminated by a line containing a single zero.
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.
10 100 20000 0 |
67 13015 1153104356 |
Problemsetter: Shahriar Manzoor and Syed Monowar Hossain
Special
Thanks: Shahriar Manzoor and Syed
Monowar Hossain