1462. GCD Ledger Total
A shipping ledger lists, for each crate number i from 1 to n, the greatest common divisor of i and n. Return the total of that column modulo 1000000007, as an int. Looping over every crate is hopeless for large n. Instead, factor n once by trial division and combine the prime powers: the total equals the sum over divisors d of n of d * phi(n / d), which is multiplicative in n. Intended cost is O(sqrt(n)) time and O(1) extra space. Beware of products that exceed 2^53 when using JavaScript or TypeScript.
Example 1
- Input:
- n = 6
- Output:
- 15
- Explanation:
The values gcd(i, 6) for i = 1..6 are 1, 2, 3, 2, 1, 6, which add up to 15.
Example 2
- Input:
- n = 10
- Output:
- 27
- Explanation:
The values gcd(i, 10) for i = 1..10 are 1, 2, 1, 2, 5, 2, 1, 2, 1, 10, which add up to 27.
Constraints
1 ≤ n ≤ 1012
The result is taken modulo 1000000007.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(sqrt(n))
- Space
- O(1)