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

$\operatorname{gcd}(v_{1}, v_{2}, \ldots, v_{n})$ 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}.


-----Input-----

The first line of the input contains integer n, (1 ≤ n ≤ 10^5), denoting the length of the sequence. The next line contains n space separated integers a_1, ..., a_{n}, (1 ≤ a_{i} ≤ 10^9).

The third line of the input contains integer q, (1 ≤ q ≤ 3 × 10^5), denoting the number of queries. Then follows q lines, each contain an integer x_{i}, (1 ≤ x_{i} ≤ 10^9).


-----Output-----

For each query print the result in a separate line.


-----Examples-----
Input
3
2 6 3
5
1
2
3
4
6

Output
1
2
2
0
1

Input
7
10 20 3 15 1000 60 16
10
1
2
3
4
5
6
10
20
60
1000

Output
14
0
2
2
2
0
2
2
1
1

Difficulty: HARD
Tags: Data structures

Mathematics

Complete search
Skill types: Data structures

Complete search

Starter code:

Solutions:
from sys import stdin
import math
from collections import defaultdict
input = stdin.readline
n = int(input())
l = list(map(int, input().split(' ')))
k = math.ceil(math.log2(n))
dp = [[0] * k for i in range(2 ** k)]

def make_sparse(l, n, k):
	for i in range(n):
		dp[i][0] = l[i]
	for j in range(1, k + 1):
		i = 0
		while i + (1 << j) <= n:
			dp[i][j] = math.gcd(dp[i][j - 1], dp[i + (1 << j - 1)][j - 1])
			i += 1

def querys(l, r):
	j = int(math.log2(r - l + 1))
	return math.gcd(dp[l][j], dp[r - (1 << j) + 1][j])
make_sparse(l, n, k)
d = defaultdict(int)
g = defaultdict(int)
d[l[0]] = 1
g[l[0]] = 1
for i in range(1, n):
	t = defaultdict(int)
	t[l[i]] = 1
	g[l[i]] += 1
	for (k, v) in list(d.items()):
		gcd = math.gcd(k, l[i])
		t[gcd] += v
		g[gcd] += v
	d = t
for i in range(int(input())):
	a = g[int(input())]
	if not a:
		print(0)
	else:
		print(a)


import os, sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
mod = 998244353
from math import ceil, gcd, log2
n = int(int(input()))
a = list(map(int, input().split()))
d = dict()
ck = [int(input()) for _ in range(int(input()))]
curr = dict()
for i in a:
	curr1 = dict()
	for j in curr:
		t = gcd(i, j)
		d[t] = d.get(t, 0) + curr[j]
		curr1[t] = curr1.get(t, 0) + curr[j]
	curr1[i] = curr1.get(i, 0) + 1
	d[i] = d.get(i, 0) + 1
	curr = curr1
for i in ck:
	if i in d:
		print(d[i])
	else:
		print(0)


from sys import stdin
import math
from collections import defaultdict
input = stdin.readline
n = int(input())
l = list(map(int, input().split(' ')))
k = math.ceil(math.log2(n))
dp = [[0] * k for i in range(2 ** k)]
d = defaultdict(int)
g = defaultdict(int)
d[l[0]] = 1
g[l[0]] = 1
for i in range(1, n):
	t = defaultdict(int)
	t[l[i]] = 1
	g[l[i]] += 1
	for (k, v) in d.items():
		gcd = math.gcd(k, l[i])
		t[gcd] += v
		g[gcd] += v
	d = t
for i in range(int(input())):
	a = g[int(input())]
	if not a:
		print(0)
	else:
		print(a)


from math import gcd
from collections import defaultdict
from sys import stdin, stdout

def main():
	GCD_count = defaultdict(int)
	GCD_map = defaultdict(int)
	arr_len = int(stdin.readline())
	arr = [int(x) for x in stdin.readline().split()]
	for start in range(arr_len):
		temp = defaultdict(int)
		GCD_count[arr[start]] += 1
		temp[arr[start]] += 1
		for (gcd_now, occurence) in GCD_map.items():
			res = gcd(gcd_now, arr[start])
			temp[res] += occurence
			GCD_count[res] += occurence
		GCD_map = temp
	num_queries = int(stdin.readline())
	for _ in range(num_queries):
		print(GCD_count[int(stdin.readline())])
main()


from bisect import insort, bisect_right, bisect_left
from sys import stdout, stdin, setrecursionlimit
from math import sqrt, ceil, floor, factorial, gcd
from io import BytesIO, IOBase
from collections import *
from itertools import *
from random import *
from string import *
from queue import *
from heapq import *
from re import *
from os import *

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = read(self._fd, max(fstat(self._fd).st_size, 8192))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = read(self._fd, max(fstat(self._fd).st_size, 8192))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(stdin, stdout) = (IOWrapper(stdin), IOWrapper(stdout))
(graph, mod, szzz) = ({}, 10 ** 9 + 7, lambda : sorted(zzz()))

def getStr():
	return input()

def getInt():
	return int(input())

def listStr():
	return list(input())

def getStrs():
	return input().split()

def isInt(s):
	return '0' <= s[0] <= '9'

def input():
	return stdin.readline().strip()

def zzz():
	return [int(i) for i in input().split()]

def output(answer, end='\n'):
	stdout.write(str(answer) + end)

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)

def getPrimes(N=10 ** 5):
	SN = int(sqrt(N))
	sieve = [i for i in range(N + 1)]
	sieve[1] = 0
	for i in sieve:
		if i > SN:
			break
		if i == 0:
			continue
		for j in range(2 * i, N + 1, i):
			sieve[j] = 0
	prime = [i for i in range(N + 1) if sieve[i] != 0]
	return prime

def primeFactor(n, prime=getPrimes()):
	lst = []
	mx = int(sqrt(n)) + 1
	for i in prime:
		if i > mx:
			break
		while n % i == 0:
			lst.append(i)
			n //= i
	if n > 1:
		lst.append(n)
	return lst
dx = [-1, 1, 0, 0, 1, -1, 1, -1]
dy = [0, 0, 1, -1, 1, -1, -1, 1]
daysInMounth = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
n = getInt()
l = zzz()
d = defaultdict(int)
g = defaultdict(int)
d[l[0]] = 1
g[l[0]] = 1
for i in range(1, n):
	t = defaultdict(int)
	t[l[i]] = 1
	g[l[i]] += 1
	for (k, v) in d.items():
		gg = gcd(k, l[i])
		t[gg] += v
		g[gg] += v
	d = t
for i in range(int(input())):
	a = g[getInt()]
	print(a)


from sys import stdin
import math
from collections import defaultdict
input = stdin.readline
n = int(input())
arr = list(map(int, input().rstrip().split(' ')))
q = int(input())
d = defaultdict(lambda : 0)
current = defaultdict(lambda : 0)
for i in range(n):
	newCurrent = defaultdict(lambda : 0)
	newCurrent[arr[i]] += 1
	for (key, value) in current.items():
		g = math.gcd(arr[i], key)
		if g > 1:
			newCurrent[g] += value
	for (key, value) in newCurrent.items():
		d[key] += value
	current = newCurrent
totalCombi = n * (n + 1) // 2
d[1] = totalCombi - sum(d.values()) + arr.count(1)
for _ in range(q):
	x = int(input())
	print(d[x])


from sys import stdin
n = int(stdin.readline())
a = [int(x) for x in stdin.readline().split()]
q = int(stdin.readline())

def gcd(a, b):
	while a != 0:
		(a, b) = (b % a, a)
	return b
totals = {}
new = {}
for x in a[::-1]:
	old = new
	new = {}
	for y in old:
		g = gcd(x, y)
		if g in new:
			new[g] += old[y]
		else:
			new[g] = old[y]
	if x in new:
		new[x] += 1
	else:
		new[x] = 1
	for y in new:
		if y in totals:
			totals[y] += new[y]
		else:
			totals[y] = new[y]
for x in range(q):
	c = int(stdin.readline())
	if c in totals:
		print(totals[c])
	else:
		print(0)


from os import path
import sys, time
mod = int(1000000000.0 + 7)
from math import ceil, floor, gcd, log, log2, factorial, sqrt
from collections import defaultdict, Counter, OrderedDict, deque
from itertools import combinations, permutations
from bisect import *
from functools import reduce
from operator import mul
maxx = float('inf')
I = lambda : int(sys.stdin.buffer.readline())
lint = lambda : [int(x) for x in sys.stdin.buffer.readline().split()]
S = lambda : sys.stdin.readline().strip('\n')
grid = lambda r: [lint() for i in range(r)]
localsys = 0
start_time = time.time()
nCr = lambda n, r: reduce(mul, range(n - r + 1, n + 1), 1) // factorial(r)

def ceill(n, x):
	return (n + x - 1) // x
T = 0

def solve():
	n = I()
	a = lint()
	ans = defaultdict(int)
	d = defaultdict(int)
	for i in a:
		t = defaultdict(int)
		t[i] = 1
		ans[i] += 1
		for j in d:
			gc = gcd(i, j)
			ans[gc] += d[j]
			t[gc] += d[j]
		d = t
	for _ in range(I()):
		print(ans[I()])

def run():
	if path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
run()
T = I() if T else 1
for _ in range(T):
	solve()
if localsys:
	print('\n\nTime Elased :', time.time() - start_time, 'seconds')


from sys import stdin
import math
from collections import defaultdict
input = stdin.readline
n = int(input())
l = list(map(int, input().split(' ')))
d = defaultdict(int)
g = defaultdict(int)
d[l[0]] = 1
g[l[0]] = 1
for i in range(1, n):
	t = defaultdict(int)
	t[l[i]] = 1
	g[l[i]] += 1
	for (k, v) in d.items():
		gcd = math.gcd(k, l[i])
		t[gcd] += v
		g[gcd] += v
	d = t
for i in range(int(input())):
	a = g[int(input())]
	print(a)


import sys
from collections import defaultdict
from math import gcd, sqrt
MAX = pow(10, 5)
ip = sys.stdin
n = int(ip.readline())
a = list(map(int, ip.readline().split()))
gcd_count = defaultdict(int)
main_gcd = defaultdict(int)
main_gcd[a[0]] = 1
gcd_count[a[0]] = 1
for i in range(1, n):
	ele = a[i]
	temp_gcd = defaultdict(int)
	temp_gcd[ele] = 1
	gcd_count[ele] += 1
	for (k, v) in main_gcd.items():
		temp = gcd(ele, k)
		temp_gcd[temp] += v
		gcd_count[temp] += v
	main_gcd = temp_gcd
q = int(ip.readline())
for _ in range(q):
	k = int(ip.readline())
	print(gcd_count[k])