| 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
Input: 3 1 2 5 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
|
||||||||
|
2012-02-21 04:17:08 Benjamin Pinaya
One does not simply uses Java in Spoj <Boromir> :D |
||||||||
|
2011-12-23 04:11:57 David
Not enough time or too many test cases for Java. Precompute sum for all n from 1 to 1000000 and store results in array. Elapsed time for this effort is 0.250 sec. Still get TLE. Java I/O too slow. Sigh. Last edit: 2011-12-23 04:12:37 |
||||||||
RSS