GCD (größter gemeinsamer Teiler) auf einem Bereich von Zahlen
Gegeben sind
n Ganzzahlen. Es sollen q Anfragen beantwortet werden, bei denen für jeden Bereich zwischen den Indizes l und r der GGT (Greatest Common Divisor) aller in diesem Bereich liegenden Zahlen bestimmt werden soll.Eingabe
Die erste Zeile der Eingabe enthält zwei Ganzzahlen
n (1 ≤ n ≤ 5000) und q (1 ≤ q ≤ 10).In der nächsten Zeile stehen
n durch Leerzeichen getrennte Ganzzahlen, die das Array darstellen (1 ≤ ≤ ).Die darauf folgenden
q Zeilen enthalten jeweils zwei Zahlen, die den Abfragebereich (0 ≤ ≤ < n) definieren.Ausgabe
Das Programm soll den GGT aller Zahlen zwischen den Indizes
l und r (einschließlich) ausgeben.Beispiele
Eingabe | Ausgabe |
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