#CW18. 最大公约数(gcd)

最大公约数(gcd)

题目描述

给定一个包含 nn 个数的序列 aia_i,定义 f(l,r)f(l,r)(1≤l≤r≤n1 \le l \le r \le n)为从 ala_l 到 ara_r(包含两端)所有数的最大公约数。

注意,ll 和 rr 是下标,而不是列表中的元素。

考虑所有可能的 ll 和 rr 取值,f(l,r)f(l,r) 会有多少个不同的值?

我们认为单个数的最大公约数是他本身。

输入格式

第一行包含一个整数 nn,表示序列的长度。

第二行包含 nn 个整数,表示 aia_i。

输出格式

输出一个整数,表示输入序列中 f(l,r)f(l,r) 可能取到的不同值的个数。

样例 1 输入

3
3 6 8

样例 1 输出

5

数据范围

对于所有测试数据,保证 1≤n≤1051 \le n \le 10^5,1≤ai≤1001 \le a_i \le 100。

测试点 n≤n \le 特殊性质
1∼71 \sim 7 10001000 无
8∼118 \sim 11 1000010000
12∼1512 \sim 15 10510^5 aia_i 都是质数
16∼2016 \sim 20 无