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
hide comments
|
ayush_chavan:
2024-11-17 14:11:52
Dont waste time in thinking and deriving anything just go and see the formula for Lcm sum otherwise its impossible to do it |
|
subhaammmm:
2024-07-12 18:18:14
Euler's totient function. but we wont precompute the result like seive. as it will give a TLE |
|
pnm03:
2023-12-09 10:55:06
Ans wrong. Thử nghiệm vẫn đúng ???
|
|
berlin03spoj:
2023-07-27 12:16:59
If you faced TLE, read about LcmSum formula , it using ETF to caculate |
|
under_rated:
2023-06-20 07:24:40
everyone talk about TLE , but you will waste hours if don't know the formula Last edit: 2023-06-20 07:33:29 |
|
nitin12384:
2023-02-05 10:21:52
Does this problem has anything to do with Mobius Inversion ? |
|
rouge_kitty:
2022-08-29 18:41:11
you can check out my method here if you are getting a TLE and cannot figure out why: <snip>
|
|
tadros:
2022-06-06 23:53:28
how could you solve this problem guys?
|
|
minhnguyent546:
2022-03-27 11:55:04
Just avoid t * sqrt(n)
|
|
lakshya_1412:
2021-10-21 13:01:05
WA in ALL GO's |
| 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