GCDEX - GCD Extreme


Given the value of N, you will have to find the value of G. 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 20000 lines of inputs. Each line contains an integer N (1 < N < 1000001). 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.

Example

Input:
10
100
200000
0

Output:
67
13015
143295493160

Time limit has been changed. Some AC solutions get TLE

hide comments
Ravi Kiran: 2010-04-07 06:40:47

Can be done without using phi values!And in much quicker time,because of the same! :)

~ adieus ~: 2009-09-11 09:26:11

O(n^(3/2)) wont work ??

Yeah it doesnt, we need a Pure sieve's implementation for getting phi values.

very easy optimizations to my logic has got AC :)

Last edit: 2009-09-11 11:43:41
.:: Pratik ::.: 2009-06-14 15:22:13

got ACC on UVA in 0.032s but TLE here :(

Last edit: 2009-06-14 15:22:30
zhengxi: 2009-03-12 17:52:13

correct task: http://icpcres.ecs.baylor.edu/onlinejudge/external/114/11424.html
the only difference is bigger maximal N (about 1000000 instead of 200000 there)

Last edit: 2009-03-12 17:52:13
[Trichromatic] XilinX: 2009-03-07 15:00:10

The problem setter has been banned for his cheating actions. To see the original description, you may go to UVa Online Judge(http://icpcres.ecs.baylor.edu) and find that problem(id:11426).


Added by:Phenomenal
Date:2009-02-16
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:ACM World Final Warm up 1 - 2008