Bereichs-GGT-Abfragen (Range GCD Queries)
Sie haben ein Array mit
n Elementen sowie q Anfragen. Es gibt zwei Arten von Anfragen: Zum einen wird der größte gemeinsame Teiler (Greatest Common Divisor, GCD) in einem bestimmten Indexbereich berechnet, zum anderen können Sie ein Element an einer angegebenen Position aktualisieren. Ihre Aufgabe besteht darin, diese Anfragen möglichst effizient zu verarbeiten.Eingabe
Die erste Zeile der Eingabe enthält zwei ganze Zahlen
n und q (1 ≤ n, q ≤ 100 000). Sie geben an, wie viele Elemente sich im Array befinden und wie viele Anfragen gestellt werden.Die zweite Zeile enthält
n durch Leerzeichen getrennte ganze Zahlen (). Diese Werte bilden die Ausgangselemente des Arrays.Die folgenden
q Zeilen beschreiben die Anfragen im Detail:- For range GCD queries: The line starts with the number 1 followed by two integers and (), representing the range of indices
[]for which the GCD needs to be calculated.
- For array update queries: The line starts with the number 2 followed by two integers and (), representing the index of the element to be updated and its new value .
Ausgabe
Geben Sie für jede Bereichs-GGT-Anfrage den Wert des berechneten GCD auf einer eigenen Zeile aus.
Beispiele
Input | Output |
6 4
12 8 16 24 36 48
1 2 5
2 4 10
1 1 6
1 3 6 | 4
2
2 |
Constraints
Time limit: 0.8 seconds
Memory limit: 512 MB
Output limit: 1 MB