Задача №114321. Евклид
Легенда этой задачи слишком велика, чтобы она уместилась на этой странице, поэтому ее здесь не будет.
Вам дан массив \(V\) длины \(n\), и вы хотите уметь осуществлять над ним следующие операции:
1) get(\(a\), \(b\)) - узнать наибольший общий делитель чисел на отрезке от \(a\) до \(b\).
2) update(\(a\), \(b\), \(k\)) - для всех \(j\) от \(a\) до \(b\) увеличить \(j\)-е число на \(k \cdot (j - a + 1)\), т.е.
\(V_a += k\)
\(V_{a+1} += 2 \cdot k\)
...
\(V_b += (b - a + 1) \cdot k\)
Первая строка входного файла содержит два числа \(1 \le n \le 10^5\) - кол-во числе в массиве и \(1 \le q \le 10^5\) - кол-во запросов. Следующая строка содержит \(n\) чисел - массив \(V\) \(1 \le V_i \le 2 \cdot 10^8\).
Далее в \(q\) строках идет информация о запросах:
Каждый запрос get задается тремя числами 0 \(a\) \(b\)
Каждый запрос update задается четырьмя числами 1 \(a\) \(b\) \(k\) (\(1 \le k \le 2 \cdot 10^8\))
Для каждого запроса get выведите наибольший общий делитель чисел на отрезке от \(a\) до \(b\)
Подзадача 1(20 баллов) \(1 \le n \le 1000\), \(1 \le q \le 1000\)
Подзадача 2(20 баллов) нет запросов update
Подзадача 3(60 баллов) нет дополнительных ограничений
8 3 2 8 12 24 66 33 21 7 0 2 4 1 1 4 2 0 2 4
4 2