MCD en un rango de números
Dado
n enteros, se solicita responder q consultas en las que se pregunta: “¿Cuál es el máximo común divisor de TODOS los números comprendidos entre los índices l y r?”Entrada
La primera línea de la entrada contiene dos enteros
n (1 ≤ n ≤ 5000) y q (1 ≤ q ≤ 10).La siguiente línea contiene
n enteros separados por espacio que representan el arreglo dado (1 ≤ ≤ ).Las siguientes
q líneas contienen pares de números que definen los rangos de consulta (0 ≤ ≤ < n).Salida
El programa debe imprimir el máximo común divisor de todos los números comprendidos entre los índices
l y r (inclusive).Ejemplos
Entrada | Salida |
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