Problem J

11426

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: Syed Monowar Hossain

/*
 * Author:  *****
 * Created Time:  2013/8/28 15:48:49
 * File Name: eular.cpp
 * solve: eular.cpp
 * source: UVA11426
 */
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<string>
#include<map>
#include<stack>
#include<set>
#include<iostream>
#include<vector>
#include<queue>
//ios_base::sync_with_stdio(false);
//#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;
#define sz(v) ((int)(v).size())
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define repf(i, a, b) for (int i = (a); i <= (b); ++i)
#define repd(i, a, b) for (int i = (a); i >= (b); --i)
#define clr(x) memset(x,0,sizeof(x))
#define clrs( x , y ) memset(x,y,sizeof(x))
#define out(x) printf(#x" %d\n", x)
#define sqr(x) ((x) * (x))
typedef long long LL;

const int INF = 1000000000;
const double eps = 1e-8;
const int maxn = 4000001;

int sgn(const double &x) {  return (x > eps) - (x < -eps); }
LL phi[maxn];
void phi_table(int n) {
  for(int i = 2; i <= n; i++) phi[i] = 0;
  phi[1] = 1;
  for(int i = 2; i <= n; i++) if(!phi[i])
    for(int j = i; j <= n; j += i) {
      if(!phi[j]) phi[j] = j;
      phi[j] = phi[j] / i * (i-1);
    }
}

LL f[maxn];
LL sum[maxn];

int main() 
{
    //freopen("in.txt","w",stdout);
    clr(phi);
    phi_table(maxn - 1);
    clr(f);
    clr(sum);
    
    for(int i = 1;i < maxn ;++i)
        for(int j = i+i;j<maxn;j+=i)
           f[j] += i*phi[j/i];
    
    for(int i = 2;i<maxn;++i)
    {
        sum[i] = sum[i - 1] + f[i];
       // cout<<sum[i]<<",";
    }
    int n;
   while(scanf("%d",&n) == 1)
    {
        if(n==0)
            break;
       printf("%lld\n",sum[n]); 
    }

    return 0;
}