MDC num intervalo de números
Dado um conjunto de
n inteiros, é necessário responder a q consultas do tipo: “Qual é o Máximo Divisor Comum (MDC) de TODOS os números entre os índices l e r?”Entrada
A primeira linha da entrada contém dois inteiros
n (1 ≤ n ≤ 5000) e q (1 ≤ q ≤ 10).A linha seguinte contém
n inteiros separados por espaço, representando o array dado (1 ≤ ≤ ).As próximas
q linhas contêm pares de inteiros que definem os intervalos da consulta (0 ≤ ≤ < n).Saída
O programa deve imprimir o Máximo Divisor Comum de todos os números entre os índices
l e r (inclusive).Exemplos
Entrada | Saída |
8 4
12 24 198 64 9 8 4 100
0 1
1 2
1 4
5 7 | 12 6 1 4 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB