CGCDSSQ

题目描述

给定一个整数序列 $a_{1},\dots,a_{n}$，以及 $q$ 个查询 $x_{1},\dots,x_{q}$。对于每个查询 $x_{i}$，你需要统计有多少对 $(l, r)$ 满足 $1 \leq l \leq r \leq n$，并且 $\gcd(a_{l},a_{l+1},\dots,a_{r}) = x_{i}$。

表示 $v_{1},v_{2},\dots,v_{n}$ 的最大公约数，即能整除所有 $v_{i}$ 的最大正整数。

输入格式

输入的第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示序列的长度。接下来的一行包含 $n$ 个由空格分隔的整数 $a_1, \dots, a_n$（$1 \le a_i \le 10^9$）。

输入的第三行包含一个整数 $q$（$1 \le q \le 3 \times 10^5$），表示查询的数量。接下来的 $q$ 行，每行包含一个整数 $x_i$（$1 \le x_i \le 10^9$）。

输出格式

对于每个查询，在单独的一行中输出结果。

样例 #1

样例输入

3
2 6 3
5
1
2
3
4
6

样例输出

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

样例输出

14
0
2
2
2
0
2
2
1
1

说明/提示

由 ChatGPT 5 翻译