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:
https://gist.github.com/sofhiasouza/d6fd7afec2f62abdafdc52f95828cd68