| 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
|
||||||||
|
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) |
||||||||
|
2019-09-10 15:41:34
Very nice problem. Took me almost 4-5 hours to eliminate that TLE...huh! |
||||||||
|
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 :( |
||||||||
|
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?? |
||||||||
|
2018-08-30 18:43:29 DK...
i got TL using pragma's, but AC without them... |
||||||||
|
2018-06-29 01:30:42
Learned a lot about phi function nice math logic Thanks. Last edit: 2018-06-29 01:34:23 |
||||||||
|
2018-05-03 14:49:26
how alien i m. everyone is getting TLE .. and i m getting WA.. |
||||||||
|
2018-01-01 09:51:18
nice math used:) |
||||||||
|
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 |
||||||||
|
2017-09-27 08:51:33
really nice prblm.. pre-compute each and every thing to avoid tle;.. |
||||||||
RSS