GCD2

#include<bits/stdc++.h>
using namespace std;
ifstream fin("gcd2.in");
ofstream fout("gcd2.out");
vector<vector<long long>> rmq;
vector<long long> lg;

//calculeaza cmmdc(a,b)
long long gcd(long long a, long long b) {
    while (b) {
        long long c = a % b;
        a = b;
        b = c;
    }
    return a;
}

//returneaza valoarea cmmdcului secventei st...dr
long long query(long long st, long long dr) {
    long long power = lg[dr - st + 1] - 1;
    return gcd(rmq[st][power], rmq[dr - (1 << power) + 1][power]);
}

int main() {

    //citirea
    long long n;
    fin >> n;
    vector<long long> a(n + 1);
    for (long long i = 1; i <= n; ++i) {
        fin >> a[i];
    }

    //precompute la floorul logaritmilor
    lg = vector<long long>(n + 1);
    for (long long i = 1; i <= n; ++i) {
        lg[i] = lg[i / 2] + 1;
    }

    //calulam dinamica pentru RMQ
    rmq = vector<vector<long long>>(n + 1, vector<long long>(lg[n] + 1));
    for (long long i = 1; i <= n; ++i) {
        rmq[i][0] = a[i];
    }
    for (long long j = 1; j <= lg[n]; ++j) {
        for (long long i = 1; i + (1 << j) - 1 <= n; ++i) {
            rmq[i][j] = gcd(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
        }
    }

    long long ans = 0;
    long long unde = 0;
    vector<long long> rez(n + 1);
    for (long long i = n; i >= 1; --i) {
        long long p = i;
        long long cmmdc = a[i];

        //caz special
        if (a[i] == 0) {
            rez[i] = rez[unde];
            continue;
        }

        //cat timp exista alte cmmdcuri posibile le cautam
        while (true) {
            long long st = p + 1, dr = n;
            long long rep = n + 1;
            while (st <= dr) {
                long long mid = (st + dr) / 2;
                if (query(i, mid) < cmmdc) {
                    dr = mid - 1;
                    rep = mid;
                }
                else {
                    st = mid + 1;
                }
            }
            rez[i] += ((rep * 1ll) - (p * 1ll)) * (cmmdc * 1ll);
            if (rep == n + 1) {
                break;
            }
            p = rep;
            cmmdc = query(i, rep);
        }

        //pentru cazul special
        if (a[i] > 0) {
            unde = i;
        }
    }

    //calculam raspunsul
    for (long long i = 1; i <= n; ++i) {
        ans += rez[i];
    }
    fout << ans;
}