Solução por Sofhia Souza
Conhecimentos prévios necessários:
Nesse problema precisamos saber, para cada intervalo, quantos valores não dividem todos os valores dele. Para que fique mais simples, encontraremos a quantidade de valores que dividem todos os valores do intervalo, e depois subtrairemos isso do tamanho dele. Podemos observar que, para que um valor divida todos os valores do intervalo, ele deve ser igual ao mdc de todos esses valores. Logo, para resolvermos esse problema, faremos duas seg trees: uma para guardar o mdc dos valores do intervalo representado pelo nó, e outra para guardar a quantidade de valores no intervalo que são iguais a esse mdc. Com isso, conseguiremos calcular quantos valores no intervalo dividem todos os valores. Segue o código para melhor entendimento:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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 | |
| } | |
| } |