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.

样例 #1

样例输入 #1

3
2 6 3
5
1
2
3
4
6

样例输出 #1

1
2
2
0
1

样例 #2

样例输入 #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