Chef recently took a course in linear algebra and learned about linear combinations of vectors. Therefore, in order to test his intelligence, Raj gave him a "fuzzy" problem to solve.
A sequence of integers $B_1, B_2, \ldots, B_M$ generates an integer $K$ if it is possible to find a sequence of integers $C_1, C_2, \ldots, C_M$ such that $C_1 \cdot B_1 + C_2 \cdot B_2 + \ldots + C_M \cdot B_M = K$.
In this problem, Chef has a sequence $A_1, A_2, \ldots, A_N$ and he should answer $Q$ queries. In each query, he is given an integer $K$; the answer to this query is the number of pairs $(l, r)$ such that $1 \le l \le r \le N$ and the subsequence $(A_l, A_{l+1}, \ldots, A_r)$ generates $K$.
Chef has no idea how to solve this problem ― can you help him find the answers to all queries?

-----Input-----
- The first line of the input contains a single integer $N$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.
- The third line contains a single integer $Q$.
- The following $Q$ lines describe queries. Each of these lines contains a single integer $K$.

-----Output-----
For each query, print a single line containing one integer ― the number of contiguous subsequences that generate $K$.

-----Constraints-----
- $1 \le N, Q \le 10^5$
- $1 \le A_i \le 10^9$ for each valid $i$
- $1 \le K \le 10^6$

-----Subtasks-----
Subtask #1 (10 points): $1 \le N \le 1,000$
Subtask #2 (90 points): original constraints

-----Example Input-----
2
2 4
3
1
2
8

-----Example Output-----
0
2
3

-----Explanation-----
The sequence $(2, 4)$ has three contiguous subsequences: $(2)$, $(4)$ and $(2, 4)$. 
- In the first query, $1$ cannot be generated by any subsequence.
- In the second query, $2$ is generated by subsequences $(2)$ and $(2, 4)$. For example, for the subsequence $(2, 4)$, we can choose $C_1 = 1$ and $C_2 = 0$.
- In the third query, $8$ is generated by all three subsequences.

Source: codechef | Difficulty: VERY_HARD
Tags: Number theory

Preprocessing

Mathematics


Solutions:
import math as mt
sz = 1000501
n = int(input())
x = [0] * sz
gcs = [0] * int(n)
a = [int(temp) for temp in input().split()]
gcs[n - 1] = a[n - 1]
i = n - 2
while i >= 0:
	gcs[i] = mt.gcd(gcs[i + 1], a[i])
	i -= 1
i = 0
while i < n:
	curr = a[i]
	if curr < sz:
		x[curr] += 1
	j = i + 1
	while j < n:
		curr = mt.gcd(curr, a[j])
		if curr == gcs[j]:
			x[curr] += n - j
			break
		elif curr < sz:
			x[curr] += 1
		j += 1
	i += 1
q = int(input())
for i in range(q):
	q1 = int(input())
	ans = 0
	for t in range(1, int(mt.sqrt(q1) + 1)):
		if q1 % t == 0:
			if q1 / t == t:
				ans += x[t]
			else:
				ans += x[t]
				ans += x[int(q1 / t)]
	print(ans)


import math
n = int(input())
a = [int(i) for i in input().split()]
op = [0 for i in range(10 ** 6 + 1)]
gcd = {}
for i in a:
	gcd[i] = 1
while len(a) != 0:
	newa = []
	x = a[0]
	for i in a[1:]:
		z = math.gcd(x, i)
		try:
			gcd[z] += 1
		except:
			gcd[z] = 1
		newa.append(z)
		x = i
	a = newa
for i in gcd:
	j = i
	while j < 10 ** 6 + 1:
		op[j] += gcd[i]
		j += i
q = int(input())
for _ in range(q):
	print(op[int(input())])


import math
import bisect
from functools import reduce
from collections import defaultdict

def inn():
	return int(input())

def inl():
	return list(map(int, input().split()))
MOD = 10 ** 9 + 7
INF = inf = 10 ** 18 + 5
n = inn()
a = inl()
k = []
for q in range(inn()):
	k.append(inn())
gcdn = reduce(math.gcd, a)
lim = max(k) + 1
ans = defaultdict(int)
ans[1] = 0
for i in range(n):
	cur_gcd = a[i]
	for j in range(i, n):
		cur_gcd = math.gcd(cur_gcd, a[j])
		if cur_gcd == 1 or cur_gcd // gcdn == 1:
			ans[cur_gcd] += n - j
			break
		ans[cur_gcd] += 1
keys = list(ans.keys())
ans1 = [0] * lim
for i in keys:
	for j in range(i, lim, i):
		ans1[j] += ans[i]
for i in k:
	print(ans1[i])


import math
from collections import defaultdict
n = int(input())
a = [int(i) for i in input().split()]
op = defaultdict(int)
gcd = defaultdict(int)
for i in a:
	gcd[i] = 1
while len(a) != 0:
	newa = []
	x = a[0]
	for i in a[1:]:
		z = math.gcd(x, i)
		gcd[z] += 1
		newa.append(z)
		x = i
	a = newa
for i in gcd:
	j = i
	while j < 10 ** 6 + 1:
		op[j] += gcd[i]
		j += i
q = int(input())
for _ in range(q):
	print(op[int(input())])


__author__ = 'Ronald Kaiser'
__email__ = 'raios dot catodicos at gmail dot com'
from math import gcd
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
K = [int(input()) for _ in range(Q)]
D = defaultdict(int)
t = A[0]
for i in range(1, N):
	t = gcd(t, A[i])
for i in range(N):
	v = A[i]
	for j in range(i, N):
		v = gcd(v, A[j])
		if v == 1:
			D[1] += N - j
			break
		elif v // t == 1:
			D[v] += N - j
			break
		D[v] += 1
i = D[1] if 1 in D else 0
max_k = max(K)
T = [i for _ in range(max_k + 1)]
for (k, v) in D.items():
	if k == 1:
		continue
	j = k
	x = 1
	while j <= max_k:
		T[j] += v
		x += 1
		j = k * x
for k in K:
	print(T[k])


from math import gcd

def SieveOfEratosthenes(n, prime):
	p = 2
	while p <= n:
		if prime[p] == 0:
			for i in range(p, n + 1, p):
				if prime[i] == 0:
					prime[i] = p
		p += 1

def fac2(nu):
	d = {}
	while nu > 1:
		p = prime[nu]
		nu = nu // p
		if d.get(p, 0) == 0:
			d[p] = 1
		else:
			d[p] += 1
	return d

def fg(i, d, l, cf, ans):
	if i == len(d):
		if cf <= M:
			ans[0] += gcdcount[cf]
		return 0
	mp = d[l[i]]
	pn = l[i]
	cm = 1
	i += 1
	for pow in range(0, mp + 1):
		fg(i, d, l, cm * cf, ans)
		cm *= pn
M = 1000001
prime = [0] * M
SieveOfEratosthenes(M - 1, prime)
n = int(input())
l = list(map(int, input().split()))
q = int(input())
ql = []
i = 0
while i < q:
	ql.append(int(input()))
	i += 1
gcdcount = [0] * 1000001
prevgcd = []
prevgcdcount = {}
for i in range(0, n):
	gcdn = len(prevgcd)
	el = l[i]
	currgcd = []
	currgcddict = {}
	currgcdcount = {}
	for j in range(0, gcdn):
		el2 = prevgcd[j]
		g = gcd(el, el2)
		incr = prevgcdcount[el2]
		if currgcddict.get(g, 0) == 0:
			currgcd.append(g)
			currgcdcount[g] = incr
			currgcddict[g] = 1
		else:
			currgcdcount[g] += incr
		if g <= M:
			gcdcount[g] += incr
	if currgcddict.get(el, 0) == 0:
		currgcd.append(el)
		currgcdcount[el] = 1
		currgcddict[el] = 1
	else:
		currgcdcount[el] += 1
	if el <= M:
		gcdcount[el] += 1
	prevgcd = currgcd
	prevgcdcount = currgcdcount
for i in ql:
	ans = [0]
	if i == 1:
		print(gcdcount[i])
	else:
		d = fac2(i)
		l = list(d.keys())
		gv = fg(0, d, l, 1, ans)
		print(ans[0])


import itertools
from math import gcd, ceil, sqrt
from collections import defaultdict
MAXK = 10 ** 6
spf = [0 for i in range(MAXK)]

def preprocess():
	spf[1] = 1
	for i in range(2, MAXK):
		spf[i] = i
	for i in range(4, MAXK, 2):
		spf[i] = 2
	for i in range(3, ceil(sqrt(MAXK))):
		if spf[i] == i:
			for j in range(i * i, MAXK, i):
				if spf[j] == j:
					spf[j] = i

def multiplyListElements(myList):
	result = 1
	for x in myList:
		result *= x
	return result

def getProductOfPrimes(x):
	product_of_primes = defaultdict(int)
	while x != 1:
		product_of_primes[spf[x]] += 1
		x = x // spf[x]
	return product_of_primes
preprocess()
ans = defaultdict(int)
gcds = defaultdict(int)
k = []
s = set()
n = int(input())
a = [int(x) for x in input().split()]
b = list(a)
q = int(input())
for _ in range(q):
	y = int(input())
	k.append(y)
	s.add(y)
x = 1
for i in range(n):
	gcd1 = a[i]
	gcds[gcd1] += 1
	y = x - 1
	for j in range(y, i):
		b[j] = gcd(b[j], b[i])
		if j == y:
			gcds[b[j]] += x
		else:
			gcds[b[j]] += 1
	if i != n - 1:
		first_seq = True
		for z in range(y, i + 1):
			if b[z] == b[z + 1] and first_seq:
				x += 1
			else:
				first_seq = False
for k3 in s:
	prime_fact_k = getProductOfPrimes(k3)
	d = []
	for j in prime_fact_k:
		l = [1]
		f1 = 1
		for k4 in range(1, prime_fact_k[j] + 1):
			f1 *= j
			l.append(f1)
		d.append(l)
	all_factors = []
	for i1 in itertools.product(*d):
		all_factors.append(multiplyListElements(i1))
	for i2 in all_factors:
		ans[k3] += gcds[i2]
for i3 in k:
	print(ans[i3])


import math
import bisect

def inn():
	return int(input())

def inl():
	return list(map(int, input().split()))
MOD = 10 ** 9 + 7
INF = inf = 10 ** 18 + 5
n = inn()
a = inl()
k = []
for q in range(inn()):
	k.append(inn())
lim = max(k) + 1
ans = {}
is_gcd = [0] * lim
ans[1] = 0
for i in range(n):
	cur_gcd = a[i]
	for j in range(i, n):
		cur_gcd = math.gcd(cur_gcd, a[j])
		if cur_gcd == 1:
			ans[1] += n - j
			break
		elif cur_gcd < lim:
			if is_gcd[cur_gcd] == 0:
				is_gcd[cur_gcd] = 1
				ans[cur_gcd] = 0
			ans[cur_gcd] += 1
keys = list(ans.keys())
ans1 = [0] * lim
for i in keys:
	for j in range(i, lim, i):
		ans1[j] += ans[i]
for i in k:
	print(ans1[i])


from math import gcd
n = int(input())
it = list(map(int, input().split()))
q = int(input())
aa = [{} for i in range(n)]
aa[0][it[0]] = 1
for i in range(1, n):
	for j in aa[i - 1]:
		a = gcd(j, it[i])
		try:
			aa[i][a] += aa[i - 1][j]
		except:
			aa[i][a] = aa[i - 1][j]
	try:
		aa[i][it[i]] += 1
	except:
		aa[i][it[i]] = 1
ss = {}
ma = 10 ** 6 + 1
k = -1
for i in aa:
	k += 1
	for j in i:
		if j >= ma:
			continue
		try:
			ss[j] += aa[k][j]
		except:
			ss[j] = aa[k][j]
ll = list(ss.keys())
ll.sort()
pre = [0] * (10 ** 6 + 1)
for i in ll:
	for j in range(i, len(pre), i):
		pre[j] += ss[i]
for _ in range(q):
	k = int(input())
	print(pre[k])


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
(total, ans) = ([], [])
for i in range(1000001):
	total.append(0)
	ans.append(0)
n = int(input())
arr = list(map(int, input().split()))
(l1, l2) = ([], [])
(dict1, dict2) = ({}, {})
for i in range(n):
	l2 = []
	dict2 = {}
	for j in range(len(l1)):
		x = gcd(l1[j], arr[i])
		if dict2.get(x) == None:
			l2.append(x)
			dict2[x] = 0
		dict2[x] += dict1[l1[j]]
		if x < 1000001:
			total[x] += dict1[l1[j]]
	l1 = []
	dict1 = {}
	l1 = l2 + []
	dict1 = dict2
	if dict1.get(arr[i]) == None:
		l1.append(arr[i])
		dict1[arr[i]] = 0
	dict1[arr[i]] += 1
	if arr[i] < 1000001:
		total[arr[i]] += 1
for i in range(1, 1000001):
	if total[i] == 0:
		continue
	for j in range(i, 1000001, i):
		ans[j] += total[i]
q = int(input())
for i in range(q):
	k = int(input())
	print(ans[k])


from collections import Counter
from math import gcd
K_MAX = 10 ** 6
n = int(input())
A = list(map(int, input().split()))
st = [Counter() for _ in range(n)]
st[0][A[0]] += 1
for i in range(1, n):
	st[i][A[i]] += 1
	for (el, times) in st[i - 1].items():
		st[i][gcd(el, A[i])] += times
cum_st = Counter()
for i in range(n):
	cum_st.update(st[i])
ans = [0] * (K_MAX + 1)
for (el, times) in cum_st.items():
	for i in range(el, K_MAX + 1, el):
		ans[i] += times
q = int(input())
for _ in range(q):
	k = int(input())
	print(ans[k])


LIMIT = 10 ** 6 + 1

def gcd(a, b):
	while a > 0:
		(a, b) = (b % a, a)
	return b

def pop_gcds(A):
	gcds = [0] * LIMIT
	prev_updates = [len(A)]
	last_gcd = A[-1]
	for start in range(len(A) - 1, -1, -1):
		cur_gcd = A[start]
		updates = [start]
		cur = start
		for end in prev_updates:
			spaces = end - cur
			if cur_gcd < len(gcds):
				gcds[cur_gcd] += spaces
			if end >= len(A):
				break
			cand_gcd = gcd(cur_gcd, A[end])
			if cand_gcd != cur_gcd:
				updates.append(end)
				cur_gcd = cand_gcd
			cur = end
		updates.append(len(A))
		prev_updates = updates
	return gcds

def pop_muls(gcds):
	muls = [0] * LIMIT
	for (index, count) in enumerate(gcds):
		if count > 0:
			cur_index = index
			while cur_index < len(muls):
				muls[cur_index] += count
				cur_index += index
	return muls
N = int(input())
A = list(map(int, input().strip().split()))
gcds = pop_gcds(A)
muls = pop_muls(gcds)
Q = int(input())
for _ in range(Q):
	q = int(input())
	print(muls[q])


import math
n = int(input(''))
a = list(map(int, input('').split(' ')))
q = int(input(''))
qu = []
for i in range(q):
	qu.append(int(input('')))
gd = {}
gcds = [1] * n
g = a[n - 1]
for i in range(n - 1, -1, -1):
	g = math.gcd(g, a[i])
	gcds[i] = g
	if g == 1:
		break
for i in range(n):
	g = a[i]
	for j in range(i, n, 1):
		g = math.gcd(g, a[j])
		if g not in gd:
			gd[g] = 0
		gd[g] = gd[g] + 1
		if j < n - 1 and g == gcds[j + 1]:
			gd[g] = gd[g] + n - j - 1
			break
d = {}
for k in gd:
	i = k
	while i < 10 ** 6 + 1:
		if i not in d:
			d[i] = 0
		d[i] = d[i] + gd[k]
		i = i + k
for k in qu:
	if k not in d:
		print(0)
	else:
		print(d[k])


__author__ = 'Ronald Kaiser'
__email__ = 'raios dot catodicos at gmail dot com'
from collections import defaultdict
from functools import reduce
from math import gcd
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
K = [int(input()) for _ in range(Q)]
MAX_K = max(K)
D = defaultdict(int)
gcd_all = reduce(gcd, A)
for i in range(N):
	v = A[i]
	for j in range(i, N):
		v = gcd(v, A[j])
		if v == 1 or v // gcd_all == 1:
			D[v] += N - j
			break
		D[v] += 1
s = D[1] if 1 in D else 0
T = [s for _ in range(MAX_K + 1)]
for (k, v) in D.items():
	if k == 1:
		continue
	for i in range(k, MAX_K + 1, k):
		T[i] += v
for k in K:
	print(T[k])


import math
from collections import defaultdict
n = int(input())
a = [int(i) for i in input().split()]
q = int(input())
k = [int(input()) for i in range(q)]
K = max(k)
op = defaultdict(int)
gcd = defaultdict(int)
smallestgcd = a[0]
for i in a:
	gcd[i] += 1
	smallestgcd = math.gcd(smallestgcd, i)
s = [a[0]]
for i in range(1, n):
	for j in range(len(s)):
		if s[j] != 1 and s[j] != smallestgcd:
			s[j] = math.gcd(a[i], s[j])
		gcd[s[j]] += 1
	s.append(a[i])
for i in gcd:
	j = i
	while j < K + 1:
		op[j] += gcd[i]
		j += i
for z in range(q):
	print(op[k[z]])