In this HackerEarth Akash and GCD 1 problem-solution 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


HackerEarth Akash and GCD 1 problem solution


HackerEarth Akash and GCD 1 problem solution.

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cassert>


using namespace std;
const int MAX = 500005;
const int MAX1 = 1000005;
const long long MOD = 1e9 + 7;
long long toti[MAX], totiS[MAX], A[MAX1], tree[MAX1];

void update(int idx, long long val, int n)
{
val %= MOD;
while(idx <= n)
{
tree[idx] = (tree[idx] + val) % MOD;
idx += (idx & -idx);
}
}

long long read(int idx)
{
long long sum = 0;
while(idx > 0)
{
sum = (sum + tree[idx]) % MOD;
idx -= (idx & -idx);
}
return sum;
}

void compute()
{
int i, j, k, ans;
for(i = 0;i < MAX;++i)
toti[i] = i;
for(i = 2;i < MAX;++i)
{
if(toti[i] == i)
{
toti[i] = i - 1;
for(j = 2*i;j < MAX;j += i)
toti[j] -= (toti[j] / i);
}
}
for(i = 1;i < MAX;++i)
{
for(j = i, k = 1;j < MAX;j += i, k++)
{
totiS[j] += i*toti[k];
}
}
}



int main()
{
int n, q, x, y;
char c;
long long ans = 0;
compute();
cin >> n;
assert(n >= 1 and n <= 1000000);
for(int i = 1;i <= n;++i)
{
cin >> A[i];
assert(A[i] >= 1 and A[i] <= 500000);
update(i, totiS[A[i]], n);
}
cin >> q;
assert(q >= 1 and q <= 100000);
while(q--)
{
cin >> c >> x >> y;
assert(x >= 1 and x <= n);
if(c == 'C')
{
assert(y >= 1 and y <= n);
ans = (read(y) - read(x-1)) % MOD;
if(ans < 0)
ans += MOD;
assert(ans >= 0 and ans < MOD);
printf("%lld\n", ans);
}
else
{
assert(y >= 1 and y <= 500000);
update(x, -totiS[A[x]], n);
update(x, totiS[y], n);
A[x] = y;
}
}
return 0;
}

Second solution

#include<bits/stdc++.h>

using namespace std;

#define vi vector < int >
#define pii pair < int , int >
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define foreach(it,v) for( __typeof((v).begin())it = (v).begin() ; it != (v).end() ; it++ )
#define ll long long
#define llu unsigned long long
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define dbg(x) { cout<< #x << ": " << (x) << endl; }
#define dbg2(x,y) { cout<< #x << ": " << (x) << " , " << #y << ": " << (y) << endl; }
#define all(x) x.begin(),x.end()
#define mset(x,v) memset(x, v, sizeof(x))
#define sz(x) (int)x.size()

int tot[500005];
int gs[500005];

void prec()
{
int i,j;
for(i=1;i<=500000;i++)
{
tot[i] = i;
}

for(i=2;i<=500000;i++)
{
if(tot[i] == i)
{
for(j=i;j<=500000;j+=i)
{
tot[j] -= tot[j]/i;
}
}
}

for(i=1;i<=500000;i++)
{
for(j=i;j<=500000;j+=i)
{
gs[j] += i*tot[j/i];
}
}
}

ll a[1000006];
ll b[1000006];

void upd(int x,ll val)
{
val %= MOD;
if(val < 0)
val += MOD;
while(x <= 1000000)
{
b[x] += val;
b[x] %= MOD;
x += (x&-x);
}
}

ll get(int x)
{
ll sum = 0;
while(x > 0)
{
sum += b[x];
sum %= MOD;
x -= (x&-x);
}
return sum;
}

int main()
{
prec();
int n,i;
scanf("%d",&n);
assert(1 <= n && n <= (int)1e6);
for(i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
assert(1 <= a[i] && a[i] <= 500000);
upd(i,gs[a[i]]);
}
int q;
scanf("%d",&q);
while(q--)
{
char op[3];
int x,y;
scanf("%s%d%d",op,&x,&y);
if(op[0] == 'U')
{
assert(1 <= x && x <= n);
assert(1 <= y && y <= 500000);
upd(x,-gs[a[x]]);
a[x] = y;
upd(x,gs[y]);
}
else
{
assert(1 <= x && x <= n);
assert(x <= y && y <= n);
ll ans = (get(y) - get(x-1) + MOD)%MOD;
printf("%lld\n",ans);
}
}
return 0;
}