SPOJ.com - Problem LCMSUM

LCMSUM - LCM Sum

#number-theory

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:
3
1
2
5

Sample Output:
1
4
55

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

< Previous 1 2 3 4 5 Next >

	shammya: 2019-11-23 17:21:06 1.use printf scanf for I/O to avoid TLE 2.Learn the formula to calculate LCM sum. 3.use sieve to calculate phi() in O(nlogn) time 4.using the formula pre-calculate ans in O(nlogn) time Total complexity = O(nlogn)
	kamesh11: 2019-09-10 15:41:34 Very nice problem. Took me almost 4-5 hours to eliminate that TLE...huh!
	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;..

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