Consultas de GCD em Intervalos
Temos um array de
n elementos e q consultas. Existem dois tipos de consultas: calcular o maior divisor comum (GCD) num intervalo específico e atualizar um elemento em determinada posição. O seu objetivo é processar estas consultas de forma eficiente.Entrada
A primeira linha da entrada contém dois inteiros
n e q (1 ≤ n, q ≤ 100 000), que representam a quantidade de elementos no array e o número de consultas, respetivamente.A segunda linha contém
n inteiros separados por espaços (), que são os valores iniciais do array.As
q linhas seguintes descrevem cada consulta:- 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 .
Saída
Para cada consulta de GCD em intervalo, imprima numa linha separada o valor do GCD correspondente aos elementos desse intervalo.
Exemplos
Entrada | Saída |
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