SPOJ.com - Problem GCDEX

GCDEX - GCD Extreme

#number-theory

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.

Submit solution!

hide comments

< Previous 1 2 3 4 5 Next >

	uwu_3b3ziz: 2024-10-08 16:09:33 +2 hours tl cause using #define int long long
	repper: 2024-05-16 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: 2023-03-08 07:07:32 such a nice problem of euler totient function concept
	rouge_kitty: 2022-08-29 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> Concepts: Euler Totient + Sieve. (P.S try to pre-compute your answer to avoid tle) [Simes]: No thanks, we don't want links to solutions. @Simes Sorry for that will keep it in mind henceforth! Last edit: 2022-08-30 13:19:33
	chhavisinha_12: 2021-07-09 20:33:31 WA
	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

Submit solution!

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