CF475D 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$）。

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

由 ChatGPT 5 翻译