转载请注明出处： http://www.cnblogs.com/fraud/          ——by fraud

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:

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

Problemsetter: Shahriar Manzoor

Special Thanks: SyedMonowarHossain

设dp[i]=gcd(1,i)+gcd(2,i)+……+gcd(i-1,i);

则ans[n]=dp[2]+dp[3]+……+dp[n].

由此问题已经转化成如何求dp[i]了，即需要求1到i-1所有数与i的gcd的和。

设k为满足gcd(x,i)=j且x<i的正整数的个数，则dp[i]=∑j*k;

同时，由于gcd(x,i)=j等价于gcd(x/j,i/j)=1,也就是phi[i/j];

接下来反过来求，那就不需要分解素因子了

 #include <iostream>

 #include <cstring>

 using namespace std;

 typedef long long ll;

 const int maxn=;

 int phi[maxn];

 ll dp[maxn+];

 ll ans[maxn+];

 void phi_table()

 {

     phi[]=;

     for(int i=;i<maxn;i++)

     {

         if(!phi[i])

         {

             for(int j=i;j<maxn;j+=i)

             {

                 if(!phi[j])phi[j]=j;

                 phi[j]=phi[j]/i*(i-);

             }

         }

     }

 }

 int main()

 {

     ios::sync_with_stdio(false);

     phi_table();

     for(int i=;i<maxn;i++)

     {

         for(int j=i*;j<maxn;j+=i)dp[j]+=(long long)i*(long long)phi[j/i];

     }

     ans[]=dp[];

     for(int i=;i<maxn;i++)ans[i]=ans[i-]+dp[i];

     int n;

     while(cin>>n&&n)

     {

         cout<<ans[n]<<endl;

     }

     return ;

 }