CGCDSSQ

给出一个长度为 $n(1 \leq n \leq 10^{5})$ 的序列和 $q(1 \leq q \leq 3 \times 10^{5})$ 个询问,每个询问输出一行,询问 $ \gcd(a_l,a_{l+1},...,a_r)=x$ 的 $(i,j)$ 的对数. $a_i \leq 10^9$ 感谢@凌幽 提供的翻译

Given a sequence of integers $ a_{1},...,a_{n} $ and $ q $ queries $ x_{1},...,x_{q} $ on it. For each query $ x_{i} $ you have to count the number of pairs $ (l,r) $ such that $ 1<=l<=r<=n $ and $ gcd(a_{l},a_{l+1},...,a_{r})=x_{i} $ .  is a greatest common divisor of $ v_{1},v_{2},...,v_{n} $ , that is equal to a largest positive integer that divides all $ v_{i} $ .

Given a sequence of integers $ a_{1},...,a_{n} $ and $ q $ queries $ x_{1},...,x_{q} $ on it. For each query $ x_{i} $ you have to count the number of pairs $ (l,r) $ such that $ 1<=l<=r<=n $ and $ gcd(a_{l},a_{l+1},...,a_{r})=x_{i} $ .  is a greatest common divisor of $ v_{1},v_{2},...,v_{n} $ , that is equal to a largest positive integer that divides all $ v_{i} $ .

For each query print the result in a separate line.

3
2 6 3
5
1
2
3
4
6

1
2
2
0
1

7
10 20 3 15 1000 60 16
10
1
2
3
4
5
6
10
20
60
1000

14
0
2
2
2
0
2
2
1
1