GCD en el Arreglo


Submit solution


Points: 100 (partial)
Time limit: 0.2s
Memory limit: 64M

Authors:
Problem types
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Python, Swift, VB

Fernando tiene un arreglo de N (1 \le N \le 10^5) números enteros y quiere llevar a cabo M(1 \le M \le 10^5) operaciones. Una operación consiste en elegir un elemento del arreglo y dividirlo por un valor dado. Se garantiza que el elemento es divisible por el valor elegido. Después de cada actualización se debe calcular el máximo común divisor de todos los elementos del arreglo.

Entrada

La primera línea contiene los valores enteros N y M.

La segunda línea contiene los N valores enteros que representan los elementos del arreglo. Estos valores están en el rango 1 \dots 2\cdot10^9.

Cada una de las siguientes M líneas contiene dos números enteros. El primer entero es un número entre 1 y N que representa el índice del elemento en la operación. El segundo entero representa el valor por el cual se divide el elemento elegido.

Salida

La salida debe contener M líneas. En cada línea se debe imprimir el valor del máximo común divisor, después de cada operación de actualización.

Ejemplo de Entrada

3 3
36 24 72 
1 3
3 12
2 4

Ejemplo de Salida

12
6
6

Comments


  • 19
    EnmanuelPM  commented on Feb. 14, 2024, 2:57 p.m.

    el problema tiene el tiempo apretado pongan esto si les da tle:

    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout.setf(ios::fixed); cout.precision(0);

  • -5
    Hd  commented on Dec. 18, 2023, 8:17 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.