GCD Sum

3.3

3 votes
Medium, Fenwick Tree, Number Theory, Segment tree, Mathematics, Approved
Problem

Function F is defined as,

F(x)=GCD(1,x)+GCD(2,x)+...+GCD(x,x)

where GCD is the Greatest Common Divisor.

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(109+7))
2. U X Y: Update the element of array A[X]=Y

Input:
First line of input contains integer N, size of the array.
Next line contains N space separated integers the elements of A.
Next line contains integer Q, number of queries.
Next Q lines contains one of the two queries.

Output:
For each of the first type of query, output the required sum (mod(109+7)).

Constraints:
1N106
1Q105
1Ai5105

For Update ,
1XN
1Y5105

For Compute,
1XYN

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

A[1]=3,A[2]=4,A[3]=3
F(3)=GCD(1,3)+GCD(2,3)+GCD(3,3)=1+1+3=5.
F(4)=GCD(1,4)+GCD(2,4)+GCD(3,4)+GCD(4,4)=1+2+1+4=8.

First query, the sum will be F(3)+F(4)=5+8=13(mod(109+7)).
Second query, the sum will be F(3)+F(4)+F(3)=5+8+5=18(mod(109+7)).
Third query, the sum will be F(3)=5(mod(109+7)).
Fourth query will update A[1]=4.
Fifth query, the sum will be F(4)+F(4)+F(3)=8+8+5=21(mod(109+7)).
Sixth query, the sum will be F(4)+F(4)=8+8=16(mod(109+7)).

Editor Image

?