Given n, calculate the sum LCM(1,n) + LCM(2,n) + .. + LCM(n,n), where LCM(i,n) denotes the Least Common Multiple of the integers i and n.


The first line contains T the number of test cases. Each of the next T lines contain an integer n.


Output T lines, one for each test case, containing the required sum.


Sample Input:

Sample Output:


1 <= T <= 300000
1 <= n <= 1000000

hide comments
sid779: 2019-07-01 19:17:11

AC in one go but I looked for the proof on google as I can't think of a solution :(

whyamievenhere: 2018-12-20 17:28:09

Again man useless time limits, how the heck are we supposed to find divisors of a number range without sieve??

DK...: 2018-08-30 18:43:29

i got TL using pragma's, but AC without them...

uvshuvo: 2018-06-29 01:30:42

Learned a lot about phi function nice math logic Thanks.

Last edit: 2018-06-29 01:34:23
crackeree: 2018-05-03 14:49:26

how alien i m. everyone is getting TLE .. and i m getting WA..

chetan4060: 2018-01-01 09:51:18

nice math used:)

epsilonalpha: 2017-12-14 07:37:25

It's a must do NT problem.
AC in one go, however I had already read the solution so it doesn't count I guess. :P

shub120798: 2017-09-27 08:51:33

really nice prblm.. pre-compute each and every thing to avoid tle;..

rohit9934: 2017-06-30 13:09:54

I have got so many TLE's in this
Some points before attempting.
prefer Pre-computation guys otherwise TLE
GCD will not work even the straight forward formula
Don't use endl in c++ use "\n" otherwise TLE
Dont use cin cout , use printf, scanf otherwise TLE.
Must do ,you will learn a lot.

Last edit: 2017-06-30 13:10:30
da_201501181: 2017-04-02 13:54:53

Learned a lot..!! Nice Question..!!

Added by:Varun Jalan
Time limit:0.527s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: PERL6
Resource:own problem used for Codechef Snackdown Onsite