A9583. CGCDSSQ
编程题
普及/提高-
知识点
题目描述
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}$ .
 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}$ .
 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}$ .
 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}$ .
 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