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

Наибольший общий делитель нескольких чисел вычисляется последовательным применением НОД к парам чисел:

НОД(a,b,c) =НОД(НОД(a,b),c)НОД(a) = a

Вам дана последовательность a1,a2,…,aN. Требуется подсчитать количество различных НОД подпоследовательностей ai,ai+1,…,aj (где 1 ≤ i ≤ j ≤ N) этой последовательности.

Формат ввода

Первая строка ввода содержит одно целое число N(1 ≤ N ≤ 500000). Вторая строка ввода содержит N целых чисел в диапазоне от 1 до 1018, разделенных пробелами —последовательность a1,a2,…,aN.

Формат вывода

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

Пример 1

ВВОД

4
9 6 2 4

ВЫВОД

6

Пример 2

ВВОД

4
9 6 3 4

ВЫВОД

5

Сначала немного теории.
Тут у нас импликация(если..то...), комбинированная с конъюнкцией(и).
Таблица истинности импликации(стрелочки):
0 0 1
0 1 1
1 0 0
1 1 1
Общее правило: если a<=b, тогда правда
Таблица истинности конъюнкции(/\):
0 0 0
0 1 0
1 0 0
1 1 1
Общее правило: если есть одна ложь-всё ложь.
Про НЕ и гуманитарий поймёт.
Про данный пример:
Нам нужен вариант, где оба выражения являются правдой, т.к. между ними стоит И
Подробно рассмотрим первый вариант:
Ирина
Первая буква гласная-правда
Вторая буква гласная-ложь
Значит, результат импликации-ложь, в чём можно убедиться взглянув на таблицу истинности, но, так как НЕ так же присутствует в данном условии, это выражение возвращает правду.
Последняя буква гласная-правда
Так как оба выражения при конъюнкции правда, всё выражение является правдой и удовлетворяет условию.

PascalABC.NET 3.7:

###RS.AdjacentGroup.SelectMany(x → x.Len >= 3 ? x.Len + x[0] : x.Str).Pr

Пояснение:

RS - ReadString: Возвращает значение типа string, введенное с клавиатуры.

AdjacentGroup: Группирует одинаковые подряд идущие элементы, получая последовательность массивов.

SelectMany: Проецирует каждый элемент последовательности в новую последовательность и объединяет результирующие последовательности в одну последовательность.

.Len - .Length: Длина массива.

.Str - .JoinToString: Преобразует последовательность символов в строку, не используя разделитель (при последовательность другого типа данных в качестве разделителя используется пробел).

.Pr - .Print: Выводит последовательность символов на экран, не используя разделитель (при последовательность другого типа данных в качестве разделителя используется пробел).

Пример работы: