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 64bit signed integer.
Example
Input: 10 100 200000 0 Output: 67 13015 143295493160 Time limit has been changed. Some AC solutions get TLE
hide comments
badboy_1496:
20180717 06:08:56
hurray!!!! ac in one go...nice way of using sieves


excel_blaze:
20180521 16:07:54
simple logic and implementation(^_^)


nadstratosfer:
20180321 19:09:52
Took me 7+ hours in 3 sittings to fit within this retarded TL in PyPy. Props to julkas for showing it's possible. 

anupamwadhwa:
20180207 19:30:21
Try NTG after this one. 

include_sajal:
20180113 18:13:41
Using Euler Phi will bring extra overheads. Try something different. Though one can apply Euler Phi cautiously to get AC. BTW, an awesome one! 

chetan4060:
20180101 11:00:39
very good concept mobius function. Last edit: 20180416 21:05:26 

vib_s02:
20170902 15:12:56
How does one find all divisors of N multiple times?


hacker_sk:
20160925 15:54:50
AC in one go :D.. 0.27 sec


mkfeuhrer:
20160815 11:23:29
euler phi :) 

visvats_141095:
20160617 15:05:26
9 tle and finally accepted! learnt a lot from this question! 
Added by:  Phenomenal 
Date:  20090216 
Time limit:  0.237s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  ACM World Final Warm up 1  2008 