Akash and GCD 1
Practice
3.9 (754 votes)
Approved
Fenwick tree
Math
Medium
Number theory
Segment trees
Problem
82% Success 11779 Attempts 30 Points 1s Time Limit 256MB Memory 1024 KB Max Code

Akash is interested in a new function F such that,

F(x) = GCD(1, x) + GCD(2, 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:
1. 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)
2. 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 the elements of A.
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 <= N <= 106
1 <= Q <= 105
1 <= Ai <= 5*105

For Update ,
1 <= X <= N
1 <= Y <= 5*105

For Compute ,
1 <= X <= Y <= N

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

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
41 votes
Tags:
ApprovedGraphsGreedy AlgorithmsMediumOpenSegment TreesTrees
Points:30
23 votes
Tags:
AlgorithmsApprovedMediumOpenTreesTwo pointer
Points:30
114 votes
Tags:
ApprovedData StructuresDynamic ProgrammingFenwick TreeHiringMediumReadySegment Trees