「CF475D」CGCDSSQ

2014年10月6日4,5840

Given a sequence of integers a1, …, an and q queries x1, …, xq on it. For each query xi you have to count the number of pairs (l, r)such that 1 ≤ l ≤ r ≤ n and gcd(al, al + 1, …, ar) = xi.

is a greatest common divisor of v1, v2, …, vn, that is equal to a largest positive integer that divides all vi.

Input

The first line of the input contains integer n, (1 ≤ n ≤ 105), denoting the length of the sequence. The next line contains n space separated integers a1, …, an, (1 ≤ ai ≤ 109).

The third line of the input contains integer q, (1 ≤ q ≤ 3 × 105), denoting the number of queries. Then follows q lines, each contain an integer xi, (1 ≤ xi ≤ 109).

Output

For each query print the result in a separate line.

Sample test(s)
input

output

input

output

题解
由于gcd(a,b)=a或者<=a/2
那么枚举区间的左端点,随着右端点的推移动,区间gcd最多变化log次
那么只要通过二分找出这log个区间即可
至于区间gcd询问,可以考虑线段树或者st表,但这题线段树会多一个log是会被卡的T T
线段树(超时)

ST表

注意不要调用系统的log,会很慢

 

 

avatar
  Subscribe  
提醒