Akash and GCD 1, Amazon Developer Hiring Challenge. Hackerearth

This question is taken from Hackerearth.com

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⁶
1 <= Q <= 10⁵
1 <= A_i <= 5*10⁵

For Update ,
1 <= X <= N
1 <= Y <= 5*10⁵

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).

Time Limit:1.0 sec(s) for each input file.

Memory Limit:256 MB

Source Limit:1024 KB

Marking Scheme:Marks are awarded if any testcase passes.

Allowed Languages:C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

Solution:

#include <stdio.h>

int gcd (int a, int b)
{
    if (a == 0)
        return b;
    return gcd(b%a, a);
}

int compute(int *a, int x, int y)
{
    int sum = 0;
   
    for(int i = x; i <= y; i++)
    {
        sum += a[i-1];
    }
    printf("%d\n", sum);
    return 0;
}

int update(int *a, int x, int y)
{
    int sum =0;
    for(int j = 1; j < y; j++)
    {      
        sum += gcd(j, y);
    }
    sum += y;

    a[x - 1] = sum;
 
    return 0;
}

int main()
{
    int n;
    int a[100000];
    int nq;
    int q[100000];
    int i;
    int x , y;
    char c;
    scanf("%d", &n);
    for(i = 0; i < n; i++)
    {
        int t;
        scanf("%d", &t);
        int j;
        for(j = 1; j < t; j++)
        {
            a[i] += gcd(j, t);
        }
        a[i] += t;
    }
    scanf("%d\n", &nq);

    for(i = 0; i < nq; i++)
    {
        scanf("%c %d %d\n", &c, &x, &y);

    if(c == 'C')
    {
        compute(&a, x, y);
    }
    else if (c == 'U')
    {
        update(&a, x, y);
    }
    else
        printf("input = %c\n", c);
    }
    return 0;
}