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 >

	rohan_c_23: 2016-10-13 13:33:03 Wonderful mathematics!!
	square1001: 2016-07-23 13:36:06 I suggest this problem: LCM Rush(Japanese). But problem statement is simple. You're given N and K. Calculate LCM(1,K) + LCM(2,K) + LCM(3,K) + ... + LCM(N,K). http://abc020.contest.atcoder.jp/tasks/abc020_d#
	vaibhav goyal: 2016-07-08 16:59:03 scanf is also giving tle's finally got ac by fast i/o nice problem :)
	ritik_agr: 2016-07-04 05:39:57 learnt new concepts from this problem Last edit: 2016-07-04 05:40:16
	sanghpriya785: 2015-10-06 13:41:37 getting tle in c as well as in python also. but learn a lot
	Infinity: 2014-11-03 12:02:03 interesting problem.Had to refer the web to get the first idea. Last edit: 2014-11-03 13:05:20
	pankaj: 2014-10-23 08:50:15 final AC
	Bhavik: 2014-02-16 19:20:51 learnt something new..:) Last edit: 2014-02-16 19:21:14
	adhikari vushesh babu: 2013-09-20 20:53:58 At last green light :) use scanf and printf instead of cin and cout which costed me many TLE.
	Ouditchya Sinha: 2013-04-29 08:40:16 Great Problem! Learnt a lot about totient function... But I think there's some server instability, my earlier solution ran in 4.19s on ideone & here it TLE'd, my improved solution ran in 0.42s on ideone & here it took 4.13s. Strange. :)

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