PGCD sur un intervalle de nombres
Étant donné
n entiers, vous devez répondre à q requêtes de la forme : « Quel est le plus grand diviseur commun de TOUS les nombres situés entre les indices l et r ? »Entrée
La première ligne de l’entrée contient deux entiers
n (1 ≤ n ≤ 5000) et q (1 ≤ q ≤ 10).La ligne suivante contient
n entiers séparés par des espaces, représentant le tableau donné (1 ≤ ≤ ).Les
q lignes suivantes contiennent des paires de nombres qui définissent les intervalles de requête (0 ≤ ≤ < n).Sortie
Le programme doit afficher le plus grand diviseur commun pour tous les nombres compris entre les indices
l et r, inclusivement.Exemples
Entrée | Sortie |
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