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

A9583 | CGCDSSQ

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

题目描述

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}$ .

![](/uploads/acgo/image/e4beb7eee8fbae1e_c06e5cdda580.jpeg) 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}$ .

![](/uploads/acgo/image/ecadf3408b1637b7_35b20399b2bd.jpeg) 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
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++ 编辑器
输入
输出