Свойства функции НОД

Введение

\(НОД\) (или \(gcd\) - наибольший общий делитель двух чисел. То есть для \(a,b\), \(gcd(a,b)\) - максимальное \(p\), что \( a \% p = 0, b \% p = 0\).

Нахождение

поиск НОД за O(log(n))

НОД массива

Пускай дан массив \(a\) длины \(n\), где \( a_i \le C \). Асимптотика поиска НОД массива (наибольшее число, являющееся делителем каждого числа массива) будет не \(O( n \log{C})\), как может показаться, а \(O( \log{C} + n)\)

gcd-стек

Дан массив натуральных чисел \(a_1, a_2... a_n\). Необходимо посчитать сумму по всем \(f(l,r) = gcd(a_l,a_{l+1}...a_r) \).

Зафиксируем \(r\). Выпишем все \(f(l,r)\) по убыванию \(l\):

Замечание 1: последовательность будет невозрастать - \( gcd(a,b) \le min(a,b) \).

Замечание 2: \( f(l_1,r) \) делится на \(f(l_2,r)\) при \(l_2 < l_2 \) - \(a\) делится на \(gcd(a,b)\).

Замечание 3: количество уникальных значений в последовательности - \( O(\log{a_r}) \).

Тогда мы можем перебрать все \(r\) и поддерживать все суффиксы, заканчивающиеся в \(r\) в т.н. gcd-стеке. Пусть уже посчитан \(gcdStack\) для \(r-1\), тогда ко всем суффиксам применим \( gcdStack[j] := gcd( gcdStack[j], a_r )\). Также добавим еще один суффикс - само \(a_r\). Удалим повторения и получим корректный gcd-стек.

Так мы получили оценку количеству уникальных НОД на всех отрезках - \(O(n*\log{n})\). Теперь для решения задачи достаточно поддерживать gcd-стек и определять сколько суффиксов имеют такой-то НОД.

Задачи на gcd-стек

Codeforces Div1B

Codeforces Div2E

НОД на отрезке

Пускай надо уметь отвечать на запросы НОД на отрезке, а также уметь прибавлять на отрезке. Тогда построим разностный массив \(b\), \(b_i = a_i - a_{i-1}, i>1\), поверх нашего массива \(a\).

Очевидно, что \( gcd(a_l,a_{l+1}...a_r) = gcd(a_l, a_{l+1}-a_l ... a_r - a_{r-1} ) \). А это тоже самое, что \( gcd(a_l, b_{l+1}...b_r) \).

Чтобы прибавлять на разностном массиве достаточно изменить два элемента в точке, что не составляет труда.