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

To check your solution you need to sign in
Sign in to continue