Akash is interested in a new function F such that,
\(F(x) = \frac{1}{GCD(1, x)} + \frac{2}{GCD(2, x)} + ... + \frac{x}{GCD(x, x)}\)
where \(GCD\) is the Greatest Common Divisor.
Now, the problem is quite simple. Given an array A of size N, there are 2 types of queries:
- C X Y : Compute the value of \(F(A[X] ) + F(A[X + 1]) + F(A[X + 2]) + .... + F( A[Y] ) \) (mod\( 10^9 + 7\))
- U X Y: Update the element of array \(A[X] = Y\)
Input:
First line of input contain integer N, size of the array.
Next line contain N space separated integers.
Next line contain integer Q, number of queries.
Next Q lines contain one of the two queries.
Output:
For each of the first type of query, output the required sum (mod \(10^9 + 7\)).
Constraints:
\(1 \le N \le 10^6\)
\(1 \le Q \le 10^5\)
\(1 \le A[i] \le 5 * 10^5\)
For \(1^{st}\) type of query,
\(1 \le X \le Y \le N\)
For \(2^{nd}\) type of query
\(1 \le X \le N\)
\(1 \le Y \le 5 * 10^5\)
3 3 4 3 6 C 1 2 C 1 3 C 3 3 U 1 4 C 1 3 C 1 2
10 14 4 16 12
\(A[1] = 3, A[2] = 4, A[3] = 3\)
\(F(3) = \frac{1}{GCD(1, 3)} + \frac{2}{GCD(2, 3)} + \frac{3}{GCD(3, 3)} = 1 + 2 + 1 = 4\)
\(F(4) = \frac{1}{GCD(1, 4)} + \frac{2}{GCD(2, 4)} + \frac{3}{GCD(3, 4)} + \frac{4}{GCD(4, 4)} = 1 + 1 + 3 + 1 = 6.\)
First query, the sum will be \(F(3) + F(4) = 4 + 6 = 10 (mod 10^9 + 7)\).
Second query, the sum will be \(F(3) + F(4) + F(3) = 4 + 6 + 4 = 14 (mod 10^9 + 7)\).
Third query, the sum will be \(F(3) = 4 (mod 10^9 + 7)\).
Fourth query will update \(A[1] = 4\).
Fifth query, the sum will be \(F(4) + F(4) + F(3) = 6 + 6 + 4 = 16 (mod 10^9 + 7)\).
Sixth query, the sum will be \(F(4) + F(4) = 6 + 6 = 12 (mod 10^9 + 7).\)
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor