Reducción con primos#13085
A Fady le encanta jugar con arreglos. Le dan un arreglo formado por enteros positivos. Su objetivo final es reducir cada elemento del arreglo exactamente a usando el mínimo número de operaciones.
En una sola operación, Fady puede:
Elegir un número primo .
Elegir un subsegmento contiguo [l, r] (1 \le l \le r \le n) tal que todo elemento a_i del subsegmento (l \le i \le r) sea múltiplo de .
Dividir entre cada elemento a_i del subsegmento elegido.
El amigo de Fady lo desafía modificando el arreglo repetidamente. Hay actualizaciones. En cada actualización, a Fady se le dan dos enteros y , lo que significa que debe cambiar el elemento en la posición por (a_{idx} = x).
Después de cada actualización, halla el mínimo número de operaciones necesarias para que todos los elementos del arreglo sean iguales a .
Las actualizaciones son acumulativas. Las operaciones no se realizan realmente y no afectan a las actualizaciones posteriores.
La primera línea contiene un único entero (1 \le t \le 10^4) — el número de casos de prueba.
La primera línea de cada caso de prueba contiene dos enteros y (1 \le n, q \le 5 \cdot 10^5) — el tamaño del arreglo y el número de actualizaciones.
La segunda línea contiene enteros a_1, a_2, \dots, a_n (1 \le a_i \le 10^7) — los elementos iniciales del arreglo.
Luego siguen líneas. Cada línea contiene dos enteros y (1 \le idx \le n, 1 \le x \le 10^7), que describen una actualización.
Se garantiza que la suma de sobre todos los casos de prueba no excede 5 \cdot 10^5, y que la suma de sobre todos los casos de prueba no excede 5 \cdot 10^5.
Para cada caso de prueba, imprime líneas. La -ésima línea debe contener un único entero — el mínimo número de operaciones que Fady necesita para que todos los elementos del arreglo sean iguales a después de la -ésima actualización.
Ejemplo 1
En el primer caso de prueba, el arreglo inicial es a = [12, 6, 12, 2].
Después de la primera actualización, el arreglo pasa a ser a = [12, 1, 12, 2]. El mínimo número de operaciones es :
Aplicar operaciones a a_1 (p \in \{2, 2, 3\}).
Aplicar operaciones al subsegmento . La operación con p=2 se aplica simultáneamente a a_3 y a_4, mientras que las operaciones con p \in \{2, 3\} se aplican solo a a_3.
Después de la segunda actualización, el arreglo pasa a ser a = [12, 1, 2, 2]. El mínimo número de operaciones es :
Aplicar operaciones a a_1 (p \in \{2, 2, 3\}).
Aplicar operación al subsegmento (p=2).
En el segundo caso de prueba, el arreglo es inicialmente a = [30, 30, 30]. Después de la primera actualización, pasa a ser a = [30, 1, 30]. Como a_2 = 1, los elementos restantes no pueden compartir operaciones. Aplicamos operaciones (p \in \{2, 3, 5\}) a a_1 y operaciones a a_3, en total operaciones.
Subtarea ( puntos): \sum n \le 2000 y \sum q \le 2000.
Subtarea ( puntos): 1 \le a_i, x \le 1000.
Subtarea ( puntos): Sin restricciones adicionales.