MCD su un intervallo di numeri
Dati
n interi, è necessario rispondere a q interrogazioni del tipo: “Qual è il Massimo Comune Divisore (MCD) di TUTTI i numeri compresi tra gli indici l e r?”Input
La prima riga dell’input contiene due interi
n (1 ≤ n ≤ 5000) e q (1 ≤ q ≤ 10).La riga successiva contiene
n numeri interi separati da spazi, che rappresentano l’array (1 ≤ ≤ ).Le successive
q righe contengono coppie di numeri che definiscono gli intervalli delle interrogazioni (0 ≤ ≤ < n).Output
Il programma deve stampare il Massimo Comune Divisore di tutti i numeri compresi tra gli indici
l e r inclusi.Esempi
Ingresso | Uscita |
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