← 返回题目列表

Codeforces · 475/D

D. 连续最大公约数查询

中文机器翻译题面 查看原题

给定一个整数序列 a1, ..., an 和 q 对其进行查询 x1, ..., xq 。对于每个查询 xi,您必须计算满足 1 ≤ l ≤ r ≤ n 且 gcd(al, al + 1, ..., ar) = xi 的对 (l, r) 的数量。

$$\gcd(v_{1},v_{2},\ldots,v_{n})$$ 是 v1, v2, ..., vn 的最大公约数,等于整除所有 vi 的最大正整数。

输入

输入的第一行包含整数n,(1 ≤ n ≤ 105),表示序列的长度。下一行包含 n 个空格分隔的整数 a1, ..., an, (1 ≤ ai ≤ 109)。

输入的第三行包含整数q,(1 ≤ q ≤ 3 × 105),表示查询的数量。接下来是 q 行,每行包含一个整数 xi,(1 ≤ xi ≤ 109)。

输出

对于每个查询,在单独的行中打印结果。

示例

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