| 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
|
||||||||
|
2021-06-27 17:13:18
If you are doing this question in O(n log n +t*sqrt(n) ) (TLE will come) Means you know the concept. Just to avoid sqrt(n) pre-compute answer just like sieve concept. |
||||||||
|
2021-03-22 11:41:51
Don't solve in python :/ , AC in C++ |
||||||||
|
2021-03-20 17:33:45
do not comment useless comment like ac in one go. |
||||||||
|
2020-10-09 12:14:07
Accept in One GO!!!!!!! |
||||||||
|
2020-07-08 09:09:38
I ripped a formula from somewhere so now I can pretend to be a problem solver. Last edit: 2021-06-12 09:29:06 |
||||||||
|
2020-06-11 19:37:31
how to get rid of TLE. my time complexity is O(n log n +t*sqrt(n) ) |
||||||||
|
2020-04-23 20:34:22
lcm(factor of n,n)=n; |
||||||||
|
2020-02-03 19:59:52
I got Tl useing sieve function.what can I do at now?? |
||||||||
|
2020-01-12 15:49:47
Ac in one go. Found the problem by seeing the solution lmao |
||||||||
|
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) |
||||||||
RSS