Наибольший общий делитель для всех подотрезков

Go Сложный math

Задача «Наибольший общий делитель для всех подотрезков»

Дан массив целых чисел a длины n. Необходимо для каждого возможного подотрезка [l, r] (1 ≤ l ≤ r ≤ n) вычислить наибольший общий делитель (НОД) элементов этого подотрезка. Затем среди всех полученных НОДов найти количество различных значений. Требуется реализовать эффективный алгоритм, учитывая, что n может быть до 100000, а элементы массива — до 10^9.

Формат ввода

Первая строка содержит одно целое число n (1 ≤ n ≤ 100000). Вторая строка содержит n целых чисел a_i (1 ≤ a_i ≤ 10^9), разделенных пробелами.

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

Выведите одно целое число — количество различных значений НОД среди всех подотрезков массива.

Примеры

Пример 1

ВВОД

3
6 10 15

ВЫВОД

6

Пример 2

ВВОД

4
2 4 8 16

ВЫВОД

4

Пример 3

ВВОД

5
7 14 21 28 35

ВЫВОД

5

Пример 4

ВВОД

5 10 15

ВЫВОД

3

main.go