Solução Informática - Nível Avançado - Semana 7

Solução por Leonardo Paes

Conhecimento prévio necessário:

• Sparse Table

Para resolvermos esse problema, uma observação importante para que um intervalo $[l, r]$ seja válido é: $min(l, r) = mdc(l, r)$, onde $min(l, r)$ é o mínimo $a_i$ no intervalo $[l, r]$ e $mdc(l, r)$ é o máximo divisor comum do intervalo $[l, r]$ do vetor $a$.

Uma maneira de provar isso é: Suponha que existe um inteiro $x$ que divide um outro inteiro $y$, tal que $x > y$. Isso por si só gera um absurdo, pois o maior divisor de $y$ é $y$.

Então, está provado por absurdo que $min(l, r) = mdc(l, r)$ deve ser verdade para que o intervalo $[l, r]$ seja um candidato à resposta.

Então, suponha que nós fixemos $a_i$ como parte de um intervalo $[l, r], l \leq i \leq r$ tal que $min(l, r) = mdc(l, r) = a_i$. Para cada inteiro $i, 1 \leq i \leq n$, nós iremos fixá-lo. Para saber o maior intervalo que contém $a_i$, podemos fazer duas buscas binárias, uma tentando diminuir ao máximo o $l$ do intervalo, e outra tentando aumentar ao máximo o $r$ do intervalo. Para checarmos se as respectivas bordas mantém a condição $min(l, r) = mdc(l, r) = a_i$ verdadeira, iremos utilizar uma estrutura de dados que nos responde, para qualquer intervalo $[l, r]$ do vetor $a$, o seu mínimo e o seu máximo divisor comum, em $O(1)$.

Essa estrutura de dados é chamada de Sparse Table. Iremos utilizar duas Sparse Tables, uma de mínimo e outra de máximo. Note que ambas as operações são comutativas, ou seja, a ordem das operações não altera o resultado. Portanto, elas satisfazem o pré-requisito para que a Sparse Table funcione!

Código de Exemplo: