← 返回题目
题库练习 CGCDSSQ
← 上一题 下一题 →

A6893 | CGCDSSQ

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

给定一个整数序列 $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}$。

![](/uploads/luogu/CF475D/57fa10a542946ca7729b1feeb84648963b002c6d_d5e63f3eaf8f.png) 表示 $v_{1},v_{2},\dots,v_{n}$ 的最大公约数，即能整除所有 $v_{i}$ 的最大正整数。

输入格式

给定一个整数序列 $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}$。

![](/uploads/luogu/CF475D/57fa10a542946ca7729b1feeb84648963b002c6d_d5e63f3eaf8f.png) 表示 $v_{1},v_{2},\dots,v_{n}$ 的最大公约数，即能整除所有 $v_{i}$ 的最大正整数。

输出格式

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

输入输出样例

输入 #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
C++ 编辑器
输入
输出