s71_avançado.cpp

#include <bits/stdc++.h>
#define mp make_pair
using namespace std;
typedef pair < int, int > ii;
int n, vet[100005], stm[400005], stq[400005]; //stm é a segtree que guarda o mdc do intervalo, e stq é a segtree que guarda 
                                             //a quantidade de valores que sao iguais ao mdc

inline void build_tree(int p, int i, int j)
{
    if(i == j) //se i e j forem iguais, o mdc é igual ao proprio valor, e apenas um valor é igual ao mdc (ele mesmo)
    {
        stm[p] = vet[i];
        stq[p] = 1;
        return;
    }
    int middle = (i+j)/2;
    build_tree(p*2, i, middle);
    build_tree(p*2+1, middle+1, j);

    stq[p] = 0;
    stm[p] = __gcd(stm[p*2], stm[p*2+1]); //calculo o mdc do intervalo da esquerda com o intervalo da direita
    if(stm[p] == stm[p*2]) stq[p] += stq[p*2]; //se o mdc da esquerda for igual ao mdc atual, entao os valores iguais ao mdc da esquerda sao iguais ao desse intervalo
    if(stm[p] == stm[p*2+1]) stq[p] += stq[p*2+1]; // o mesmo pra direita
}

inline ii query(int p, int i, int j, int x, int y)
{
    if(i > y or j < x) return mp(-1, -1); //se estou fora do intervalo, retorno -1
    else if(i >= x and j <= y) return mp(stm[p], stq[p]); //se estou totalmente no intervalo, retorno meus valores

    int middle = (i+j)/2;
    ii p1 = query(p*2, i, middle, x, y); //chamo pra esquerda e para a direita
    ii p2 = query(p*2+1, middle+1, j, x, y);

    if(p1.first == -1) return p2; //se algum dos dois não esta dentro do intervalo, entao retorno o outro
    if(p2.first == -1) return p1;

    int mdc = __gcd(p1.first, p2.first); //calculo o mdc entre os dois resultados
    ii t = mp(mdc, 0); //t.first guarda o mdc e t.second guarda a quantidade de valores iguais a esse mdc
    if(p1.first == mdc) t.second += p1.second; //se o mdc da esquerda for igual ao mdc atual, entao os valores iguais ao mdc da esquerda sao iguais ao desse intervalo
    if(p2.first == mdc) t.second += p2.second; //o mesmo para a direita

    return t;
}

int main()
{
    cin >> n; //leio o n
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> vet[i]; //leio os valores
    }
    build_tree(1, 1, n); //construo as segs
    int q;
    cin >> q; //leio o q
    while(q--)
    {
        int a, b;
        cin >> a >> b; //leio os valores a e b que representam o intervalo
        cout << (b-a+1) - query(1, 1, n, a, b).second << endl; //faço a query e subtraio o resultado do tamanho do intervalo 
    }
}