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.


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.


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.




Time limit has been changed. Some AC solutions get TLE

hide comments
chhavisinha_12: 2021-07-09 20:33:31


sankalp_7: 2021-06-28 06:07:04

Totient Function + Sieve concept
Nice problem :D

sunny_saraff: 2020-07-09 12:24:14

Time limit is too strict although AC in 2 GO!!
precalculate all divisors of numbers upto given range

fairooj_04: 2020-04-25 11:47:19

I used euler Totient function.....and getting runtime (SIGSEV) , can anyone help me here?

mushfiq4513: 2019-05-12 16:21:48

modified sieve and totient function..... AC :)

DK...: 2019-03-16 15:13:43

Try to compute everything into arrays, using vector's push_back function makes TL

whyamievenhere: 2018-12-19 20:02:17

TLE is killing me here... time limit is really ridiculous,

badboy_1496: 2018-07-17 06:08:56

hurray!!!! ac in one go...nice way of using sieves

excel_blaze: 2018-05-21 16:07:54

simple logic and implementation(^_^)
nice for beginners

Last edit: 2018-05-21 16:08:46
nadstratosfer: 2018-03-21 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.

Edit: Thanks to psetter or admins for sensible TL correction.

Last edit: 2020-12-22 22:19:37

Added by:Phenomenal
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