Given an integer N, find the sum of GCD(i, N) where i = 1 to N. GCD denotes the greatest common divisor. Provide the answer modulus 10^{9} + 7.
Example 1:
Input: N = 2
Output: 3
Explanation:
GCD(1,2)+GCD(2,2) = 1 + 2 = 3
​Example 2:
Input: N = 10
Output: 27
Explanation:
GCD(1,10)+GCD(2,10)+...
+GCD(9, 10)+GCD(10, 10)=1+2+..+1+10=27
Your Task:
You don't need to read input or print anything. Your task is to complete the function sumOfGCDofPairs() which takes N as inputs and returns the answer.
Expected Time Complexity: O(sqrt(N))
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{6}

见题面

见题面