所有子段的最大公约数

Go Hard math

任务 «所有子段的最大公约数»

给定一个长度为 n 的整数数组 a。需要对于每个可能的子段 [l, r]（1 ≤ l ≤ r ≤ n），计算该子段元素的最大公约数（GCD）。然后在所有得到的 GCD 中，找出不同值的数量。要求实现一个高效算法，考虑到 n 最多可达 100000，数组元素最多可达 10^9。

第一行包含一个整数 n (1 ≤ n ≤ 100000)。第二行包含 n 个整数 a_i (1 ≤ a_i ≤ 10^9)，用空格分隔。

输出一个整数——数组所有子段中不同GCD值的数量。

输入

3
6 10 15

输出

6

输入

4
2 4 8 16

输出

4

输入

5
7 14 21 28 35

输出

5

输入

5 10 15

输出

3

main.go