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 Next >

	fetus: 2020-07-08 09:09:38 ∑LCM(i, n) = ((∑(d * ETF(d)) + 1) * n) / 2 where ETF(d) is Euler totient function of d and d belongs to the set of divisors of n. try to use this formula... source--geeksforgeeks
	priyankarai: 2020-06-11 19:37:31 how to get rid of TLE. my time complexity is O(n log n +t*sqrt(n) )
	abuhuraira071: 2020-04-23 20:34:22 lcm(factor of n,n)=n;
	zakir_1999: 2020-02-03 19:59:52 I got Tl useing sieve function.what can I do at now??
	alexardelean: 2020-01-12 15:49:47 Ac in one go. Found the problem by seeing the solution lmao
	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...

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