LCMSUM - LCM Sum
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.
Input
The first line contains T the number of test cases. Each of the next T lines contain an integer n.
Output
Output T lines, one for each test case, containing the required sum.
Example
Input: 3 1 2 5 Output: 1 4 55
Constraints
1 ≤ T ≤ 300000
1 ≤ n ≤ 1000000
hide comments
|
vaibhav goyal:
2016-07-08 16:59:03
scanf is also giving tle's
|
|
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.
|
|
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 :)
|
|
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. :) |
|
Rajarshi Sarkar:
2013-04-29 06:55:43
One does not simply calculate LCM :D |
|
saket diwakar:
2013-01-30 23:14:57
finally got AC....:)
|
| 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 |
RSS