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
uwu_3b3ziz:
20241008 16:09:33
+2 hours tl cause using #define int long long


repper:
20240516 08:26:40
Check proof of Gauss Theorem related to Euler's Totient's Function this problem would be cakewalk, only thing would be clever implementation to pass the strict TL. 

jakaria_jaki:
20230308 07:07:32
such a nice problem of euler totient function concept


rouge_kitty:
20220829 20:16:00
It honestly feels so good to get AC in the first attempt on this one XD Anyways, for those who are struggling, here's my solution: <snip>


chhavisinha_12:
20210709 20:33:31
WA 

sankalp_7:
20210628 06:07:04
Totient Function + Sieve concept


sunny_saraff:
20200709 12:24:14
Time limit is too strict although AC in 2 GO!!


fairooj_04:
20200425 11:47:19
I used euler Totient function.....and getting runtime (SIGSEV) , can anyone help me here? 

mushfiq4513:
20190512 16:21:48
modified sieve and totient function..... AC :) 

DK...:
20190316 15:13:43
Try to compute everything into arrays, using vector's push_back function makes TL 
Added by:  Phenomenal 
Date:  20090216 
Time limit:  1s 
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 