Akash and GCD 1

Problem link: Akash_gcd_1

We need to perform query based on given function F, that

F(x) = GCD(1, x) + GCD(2, x) + ..... + GCD(x, x)
Where GCD is the Greatest Common Divisor
Now in the problem, 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 A[X] = Y

Solution:

At first we need to pre compute the value of F(x). Also we need help of Euler's Totient Function for this purpose. You can learn Euler Totient from here: Euler's Totient
Also we need to compute summation of GCD(i,n) for i = 1 to n. If you don't know how to do that, see here: GCD summation

This problem can be solved by segment tree. But as we only need prefix sum and simple update query, we can also solve it using binary indexed tree. As binary indexed tree is easy to code and simple, it's preferable.

Code:

	#include <bits/stdc++.h>
	#include <ext/pb_ds/assoc_container.hpp>
	#include <iostream>
	using namespace std;
	using namespace __gnu_pbds;
	#define ll long long
	#define pb push_back
	#define MOD 1000000007
	#define MAX 1000010
	//typedef __int128 bigll;
	ll a[MAX],n;
	ll f[MAX],phi[MAX];
	ll bit[MAX];
	void pre_compute()
	{
	// compute phi
	for(ll i = 1; i < MAX; i += 2)phi[i] = i;
	for(ll i = 2; i < MAX; i += 2)phi[i] = i/2;
	for(ll i = 3; i < MAX; i += 2)
	{
	if(phi[i] == i)
	{
	phi[i]--;
	for(ll j = i+i; j < MAX; j += i)
	phi[j] -= phi[j]/i;
	}
	}
	// compute gcd (i,n) for i = 1 to n
	for(ll i = 1; i < MAX; i++)
	{
	for(ll j = i; j < MAX; j += i)
	{
	f[j] += phi[j/i]*i;
	if(f[j] >= MOD)f[j] -= MOD;
	}
	}
	}
	void update(ll x,ll val)
	{
	for( ; x <= n; x += x&(-x))
	{
	bit[x] += val;
	if(bit[x] >= MOD)bit[x] -= MOD;
	}
	}
	ll query(ll x)
	{
	ll sum=0;
	for( ; x > 0; x -= x&(-x))
	{
	sum += bit[x];
	if(sum >= MOD)sum -= MOD;
	}
	return sum;
	}
	int main()
	{
	//ios_base::sync_with_stdio(false);
	//cin.tie(NULL);
	//FILE*f=freopen("input.txt","r",stdin);
	//FILE*o=freopen("output.txt","w",stdout);
	pre_compute();
	scanf("%lld",&n);
	ll q,x,y;
	for(int i=1; i<=n; i++)
	{
	scanf("%lld",&a[i]);
	update(i,f[a[i]]); // update the tree with f [ a[i] ]
	}
	scanf("%lld",&q);
	while(q--)
	{
	char ch;
	scanf(" %c %lld %lld",&ch,&x,&y);
	if(ch=='C')
	{
	ll ans = query(y)-query(x-1);
	while(ans < 0)ans += MOD;
	printf("%lld\n",ans%MOD);
	}
	else
	{
	update(x,f[y]-f[a[x]]);
	a[x] = y;
	}
	}
	//fclose(f);
	//fclose(o);
	return 0;
	}

view raw Akash_gcd_1.cpp hosted with ❤ by GitHub

Notice at line 86, the computed value might go negative less than 10^9+7. So we used a while loop to check while the value is below zero, we will add the mod value to make it positive. If we checked the negative value mod in the qeury function, this wouldn't be necessary.