Requêtes GCD sur une plage
Vous disposez d’un tableau de
n éléments ainsi que de q requêtes. Deux types de requêtes sont possibles : calculer le plus grand commun diviseur (GCD) sur une plage donnée et mettre à jour un élément à un emplacement précis. Votre objectif est de traiter ces requêtes de manière efficace.Entrée
La première ligne de l’entrée contient deux entiers
n et q (1 ≤ n, q ≤ 100 000), qui représentent respectivement le nombre d’éléments du tableau et le nombre de requêtes.La deuxième ligne contient
n entiers séparés par des espaces, (), qui correspondent aux valeurs initiales du tableau.Les
q lignes suivantes décrivent chacune une requête :- 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 .
Sortie
Pour chaque requête de type « GCD sur une plage », affichez sur une ligne séparée la valeur du GCD des éléments dans la plage concernée.
Exemples
Entrée | Sortie |
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