# HackerEarth Akash and GCD 1 problem solution

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.

`#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;}`