Поиск

НОД подпоследовательности


Ограничение времени - 2 секунды

Ввод - стандартный ввод или input.txt

Ограничение памяти - 256Mb

Вывод - стандартный вывод или output.txt

Наибольший общий делитель (НОД) двух чисел может вычислен по формуле:

  • НОД$$$(a,b)=a$$$, если $$$b=0$$$;
  • НОД$$$(a,b)=$$$НОД$$$(b, a \% b),$$$ если $$$b>0$$$, где $$$\%$$$ — остаток от деления.
Наибольший общий делитель нескольких чисел вычисляется последовательным применением НОД к парам чисел:
  • НОД$$$(a,b,c)=$$$НОД(НОД($$$a,b),c)$$$
  • НОД$$$(a)=a$$$

Вам дана последовательность $$$a_1, a_2,\dots, a_N$$$. Требуется подсчитать количество различных НОД подпоследовательностей $$$a_i, a_{i+1},\dots, a_j$$$ (где $$$1 \le i \le j \le N)$$$ этой последовательности.

Входные данные

Первая строка ввода содержит одно целое число $$$N~(1 \le N \le 500000)$$$. Вторая строка ввода содержит $$$N$$$ целых чисел в диапазоне от 1 до $$$10^{18}$$$, разделенных пробелами —последовательность $$$a_1, a_2,\dots, a_N$$$.

Выходные данные

Вывести одно целое число — количество различных значений среди $$$\gcd$$$ для всех непрерывных подпоследовательностей в заданной последовательности.

Примеры

Входные данные
4
9 6 2 4
Выходные данные
6
Входные данные
4
9 6 3 4
Выходные данные
5
  • Tutorials MathJax.Hub.Config({ tex2jax: {inlineMath: [['$$$','$$$']], displayMath: [['$$$$$$','$$$$$$']]} });

    Переберем начало подпоследовательности и будем добавлять новое число и считать НОД. Получившиеся значение положим в множество. В конце выведем размер множества. Но такое решение будет работать за $$$O(N^2 log_2~10^{18})$$$. Если добавить следующее отсечение: НОД последовательности стал равен 1, то больше добавлять новые числа нет смысла, так как НОД не изменится. Такая оптимизация позволит пройти ещё несколько тестов, но всё равно не даёт решить задачу на полный балл.

    Заметим, что НОД подпоследовательности чисел не может возрастать при добавлении очередных элементов в подпоследовательность и таким образом не может принять более $$$log_2~10^{18}$$$ значений (примерно 64). Пусть $$$D_i = \{ $$$НОД$$$(a_j , a_{j+1}, \dots, a_{i-1}, a_i )~|~j \le i \}$$$ при этом размер $$$D_i$$$ не превышает $$$O(log_2~a_{i} )$$$. Тогда можно рассчитать $$$D_{i+1} = \{ $$$НОД$$$(v, a_{i+1})~|~v \in D_i \}~\cup~\{ a_{i+1} \}$$$. Все новые значения добавить в множество, в котором будем хранить все НОД. Тогда время работы алгоритма $$$O(N log_2^2~10^{18})$$$

    • Для отправки решения задачи необходимо авторизоваться!

    Разбор задачи