| Submit | All submissions | Best solutions | Back to list |
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
Sample Input: 3 1 2 5 Sample Output: 1 4 55
Constraints
1 <= T <= 300000
1 <= n <= 1000000
| 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 |
hide comments
|
||||||||
|
2017-04-02 13:54:53
Learned a lot..!! Nice Question..!! |
||||||||
|
2016-10-13 13:33:03
Wonderful mathematics!! |
||||||||
|
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# |
||||||||
|
2016-07-08 16:59:03 vaibhav goyal
scanf is also giving tle's finally got ac by fast i/o nice problem :) |
||||||||
|
2016-07-04 05:39:57
learnt new concepts from this problem Last edit: 2016-07-04 05:40:16 |
||||||||
|
2015-10-06 13:41:37
getting tle in c as well as in python also. but learn a lot |
||||||||
|
2014-11-03 12:02:03 Infinity
interesting problem.Had to refer the web to get the first idea. Last edit: 2014-11-03 13:05:20 |
||||||||
|
2014-10-23 08:50:15 pankaj
final AC |
||||||||
|
2014-02-16 19:20:51 Bhavik
learnt something new..:) Last edit: 2014-02-16 19:21:14 |
||||||||
|
2013-09-20 20:53:58 adhikari vushesh babu
At last green light :) use scanf and printf instead of cin and cout which costed me many TLE. |
||||||||
RSS