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
Rishav Goyal: 2014-06-19 13:52:49

w**********k is wrong with spoj!!
AC in 2 sec. even with max N=4000000 on UVA but tle on spoj with max N=1000000.
its disappointing .!!

Last edit: 2015-01-11 16:49:36
Yu Zhijingcheng: 2014-03-20 16:29:59

Look here if you got TLE
1. N is in the range [1, 1000000]
2. The input may end with EOF instead of 0 in the sample input.

王泽宇: 2014-03-13 08:41:28

Practice mathematics!

Guilherme Sena: 2014-03-07 22:14:20

ATTENTION: MAXIMAL N = 1000000!!!

Piyush Raman Srivastava: 2014-01-24 20:42:15

so much to understand for this problem!! :-/
Taught me how things relate to each other in mathematics!! :)

Last edit: 2014-01-25 14:14:48
hahaha: 2013-11-27 08:31:03

Time limit is too strict got AC in UVA
but get TLE here

$iddharth prasad: 2013-09-21 09:15:45

getting tle how to optimize ??

YangYue: 2012-12-07 08:19:57

O(n) can solve it

Renato Ferreira: 2012-07-10 17:39:21

Optimization tips: do not overuse long long and read the whole input using fread, then parse the integers.


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