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