E-GCD Party

#include<bits/stdc++.h>
using namespace std;

ifstream fin("GCDP.in");
ofstream fout("GCDP.out");

int n, a[100002][18];
long long s[100002];

// cel mai mare divizor comun
int cmmdc(int a, int b)
{
    while (b)
    {
        int r = a % b;
        a = b;
        b = r;
    }

    return a;
}

// returneaza cmmdc pe intervalul [x, y]
int sub(int x, int y)
{
    int j = log2(y - x + 1);

    return cmmdc(a[x][j], a[y - (1 << j) + 1][j]);
}

long long suma(long long x, long long y)
{
    return 1LL * (x + y) * (y - x + 1) / 2;
}

int main()
{
    // citire
    fin >> n;

    for (int i = 1; i <= n; i++)
    {
        fin >> a[i][0];
    }

    // RMQ

    for (int j = 1; (1 << j) <= n; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            a[i][j] = cmmdc(a[i][j - 1], a[i + (1 << (j - 1))][j - 1]);

    for (int i = 1; i <= n; i++)
    {
        int poz = i, l, r;

        l = 1, r = i;

        while (l <= r)
        {
            int m = (l + r) / 2;

            if (sub(m, i) == 1)
                l = m + 1;
            else
            {
                poz = m;
                r = m - 1;
            }
        }

        s[i] = s[i - 1] + (long long)(i - poz + 1);
    }

    for (int i = 1; i <= n; i++)
    {
        if(a[i][0] == 1)
        {
            fout << "0 ";
            continue;
        }
        int poz = i, l, r;

        l = i, r = n;

        while (l <= r)
        {
            int m = (l + r) / 2;

            if (m - (s[m] - s[m - 1]) + 1 <= i)
            {
                poz = m;
                l = m + 1;
            }
            else
                r = m - 1;
        }

        long long aux = s[poz] - s[i - 1] - suma(0, poz - i);
        fout << aux << ' ';
    }

    return 0;
}