302467: CF475D. CGCDSSQ

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

CGCDSSQ

题意翻译

给出一个长度为$n(1<=n<=10^{5})$ 的序列和$q(1<=q<=3*10^{5})$ 个询问,每个询问输出一行,询问$gcd(a_l,a_{l+1},...,a_r)=x$ 的$(i,j)$ 的对数. 感谢@凌幽 提供的翻译

题目描述

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} $ . ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF475D/57fa10a542946ca7729b1feeb84648963b002c6d.png) 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} $ . ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF475D/57fa10a542946ca7729b1feeb84648963b002c6d.png) 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

Input

题意翻译

给出一个长度为$n(1<=n<=10^{5})$ 的序列和$q(1<=q<=3*10^{5})$ 个询问,每个询问输出一行,询问$gcd(a_l,a_{l+1},...,a_r)=x$ 的$(i,j)$ 的对数. 感谢@凌幽 提供的翻译

加入题单

上一题 下一题 算法标签: