CGCDSSQ

题意翻译

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

题目描述

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.

输入输出样例

输入样例 #1

3
2 6 3
5
1
2
3
4
6

输出样例 #1

1
2
2
0
1

输入样例 #2

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

输出样例 #2

14
0
2
2
2
0
2
2
1
1