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:

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

Problemsetter: Shahriar Manzoor

Special Thanks: Syed Monowar Hossain

 1 #include<iostream> 2 #include<stdio.h> 3 #include<cstring> 4 #include<cstdlib> 5 using namespace std; 6 const int maxn = 503; 7  8 int G[maxn]; 9 int opl[maxn];10 void init()11 {12     int i,j;13     memset(G,0,sizeof(G));14     for(i=2;i<maxn;i++) opl[i] = i;15     for(i=2;i<maxn;i++)16     {17         if(opl[i]==i)18         {19             for(j=i;j<maxn;j=j+i)20                 opl[j] = opl[j]/i*(i-1);21         }22         for(j=1;i*j<maxn;j++)/**opl [ i  ] 此时已经算出**/23             G[j*i] = G[j*i] + opl[i]*j;24     }25     for(i=3;i<maxn;i++)26         G[i] +=G[i-1];27 }28 int main()29 {30     int n;31     init();32     while(scanf("%d",&n)>0)33     {34         if(n==0)break;35         printf("%d\n",G[n]);36     }37     return 0;38 }