题目描述
给定一个包含 n 个数的序列 ai,定义 f(l,r)(1≤l≤r≤n)为从 al 到 ar(包含两端)所有数的最大公约数。
注意,l 和 r 是下标,而不是列表中的元素。
考虑所有可能的 l 和 r 取值,f(l,r) 会有多少个不同的值?
我们认为单个数的最大公约数是他本身。
输入格式
第一行包含一个整数 n,表示序列的长度。
第二行包含 n 个整数,表示 ai。
输出格式
输出一个整数,表示输入序列中 f(l,r) 可能取到的不同值的个数。
样例 1 输入
3
3 6 8
样例 1 输出
5
数据范围
对于所有测试数据,保证 1≤n≤105,1≤ai≤100。
| 测试点 |
n≤ |
特殊性质 |
| 1∼7 |
1000 |
无 |
| 8∼11 |
10000 |
| 12∼15 |
105 |
ai 都是质数 |
| 16∼20 |
无 |