akash-and-gcd-1-15

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 ≤ 10^6
1 ≤ Q ≤ 10^5
1 ≤ Ai ≤ 5*10^5

For Update ,
1 ≤ X ≤ N
1 ≤ Y ≤ 5*10^5

For Compute ,
1 ≤ X ≤ Y ≤ N  

SAMPLE INPUT
3
3 4 3
6
C 1 2
C 1 3
C 3 3
U 1 4
C 1 3
C 1 2

SAMPLE OUTPUT
13
18
5
21
16

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 10^9 + 7).
Second query, the sum will be F(3) + F(4) + F(3) = 5 + 8 + 5 = 18 (mod 10^9 + 7).
Third query, the sum will be F(3) = 5 (mod 10^9 + 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 10^9 + 7).
Sixth query, the sum will be F(4) + F(4) = 8 + 8 = 16 (mod 10^9 + 7).

Source: hackerearth | Difficulty: MEDIUM
Tags: Number theory

Range queries

Mathematics

Segment trees revisited


Solutions:
# Problem: https://www.hackerearth.com/problem/algorithm/akash-and-gcd-1-15/
# To compute the SUM (gcd(i, n)) for 1 <= i <= n, we do SUM (d * phi(n/d)) for 1 <= d <= n where d | n.
# To compute range sums we use the Binary Indexed Tree here.


MAX_N = 500001
MOD = 1000000007

phi = [i for i in range(MAX_N)]
gcd_sum = [0] * MAX_N


def main():
	preprocess()
	N = int(input().strip())
	numbers = list(map(int, input().strip().split()))
	size = (N << 1) + 2
	bin_idx_tree = [0] * size
	for (idx, n) in enumerate(numbers):
		if gcd_sum[n] >= MOD:
			gcd_sum[n] %= MOD
		update(bin_idx_tree, size, idx+1, gcd_sum[n])
	Q = int(input().strip())
	for q in range(Q):
		op, x, y = input().strip().split()
		x, y = list(map(int, [x, y]))
		if op == 'C':
			print(compute(bin_idx_tree, size, x, y))
		else:
			update(bin_idx_tree, size, x, -gcd_sum[numbers[x-1]])
			update(bin_idx_tree, size, x, gcd_sum[y])
			numbers[x-1] = y


def preprocess():
	for i in range(2, MAX_N):
		if phi[i] == i:
			j = i
			while j < MAX_N:
				phi[j] -= phi[j]/i
				j += i
	for i in range(1, MAX_N):
		j, k = i, 1
		while j < MAX_N:
			gcd_sum[j] += phi[k] * i
			j += i
			k += 1


def update(bin_idx_tree, size, idx, val):
	while idx < size:
		bin_idx_tree[idx] += val
		bin_idx_tree[idx] %= MOD
		# if bin_idx_tree[idx] >= MOD:
		#     bin_idx_tree[idx] -= MOD
		idx += (idx & -idx)


def compute(bin_idx_tree, size, st, en):
	ans = compute_helper(bin_idx_tree, en) - compute_helper(bin_idx_tree, st-1)
	if ans < 0:
		ans += MOD
	return ans


def compute_helper(bin_idx_tree, idx):
	sum = 0
	while idx > 0:
		sum += bin_idx_tree[idx]
		if sum >= MOD:
			sum -= MOD
		idx -= (idx & -idx)
	return sum


if __name__ == '__main__':
	main()