Given an array of positive integers and many queries for divisibility. In every query Q[i], we are given an integer K , we need to count all elements in the array which are perfectly divisible by K.
 
Example 1:
Input:
N = 6
A[] = { 2, 4, 9, 15, 21, 20}
M =  3
Q[] = { 2, 3, 5}
Output:
3 3 2
Explanation:
Multiples of '2' in array are:- {2, 4, 20}
Multiples of '3' in array are:- {9, 15, 21}
Multiples of '5' in array are:- {15, 20}
 
Example 2:
Input:
N = 3
A[] = {3, 4, 6}
M = 2
Q[] = {2, 3}
Output:
2 2
Your Task:  
You don't need to read input or print anything. Your task is to complete the function leftElement() which takes the array A[] and its size N, array Q[] and its size M as inputs and returns the array containing the required count for each query Q[i].
 
Expected Time Complexity: O(Mx*log(Mx))
Expected Auxiliary Space: O(Mx)
where Mx is the maximum value in array elements.
 
Constraints:
1<=N,M<=10^{5}
1<=A[i],Q[i]<=10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Number theory

Data structures

Mathematics

Starter code: #User function Template for python3



def getMaxandMinProduct( A, Q, N, M):

    # code here

    

    

    

Solutions:
from collections import Counter

def getMaxandMinProduct(A, Q, N, M):
	(s, m) = (Counter(A), max(A))
	ans = [0] * len(Q)
	for (i, e) in enumerate(Q):
		if e != 0:
			for k in range(e, m + 1, e):
				ans[i] += s.get(k, 0)
	return ans


def getMaxandMinProduct(A, Q, N, M):
	m = max(A)
	ans = [0] * (m + 1)
	cnt = [0] * (m + 1)
	for i in range(N):
		cnt[A[i]] += 1
	for i in range(1, m + 1):
		for j in range(i, m + 1, i):
			ans[i] += cnt[j]
	res = []
	for i in Q:
		if i > m:
			res.append(0)
		else:
			res.append(ans[i])
	return res


def getMaxandMinProduct(A, Q, N, M):
	n = max(A)
	sieve = [0] * (n + 1)
	for x in A:
		sieve[x] += 1
	res = []
	for x in Q:
		if x == 0:
			res.append(0)
			continue
		cnt = 0
		mul = 1
		while mul * x <= n:
			cnt += sieve[mul * x]
			mul += 1
		res.append(cnt)
	return res


from collections import Counter

def getMaxandMinProduct(A, Q, N, M):
	set1 = Counter(A)
	max1 = max(A)
	min1 = min(A)
	sol = [0] * M
	for i in range(M):
		if Q[i] == 1:
			sol[i] = N
			continue
		for j in range(Q[i], max1 + 1, max(Q[i], 1)):
			if Q[i] != 0:
				if j % Q[i] == 0:
					if j in set1:
						sol[i] += set1[j]
	return sol


from collections import Counter

def getMaxandMinProduct(A, Q, N, M):
	(cnt, m) = (Counter(A), max(A))
	ans = [0] * len(Q)
	for (i, q) in enumerate(Q):
		if q != 0:
			for n in range(q, m + 1, q):
				ans[i] += cnt.get(n, 0)
	return ans


def getMaxandMinProduct(arr, Q, n, M):
	MAX = max(arr)
	global ans
	ans = [0] * (MAX + 1)
	cnt = [0] * (MAX + 1)
	for i in range(n):
		cnt[arr[i]] += 1
	for i in range(1, MAX + 1):
		for j in range(i, MAX + 1, i):
			ans[i] += cnt[j]
	ans2 = []
	for i in Q:
		if i > len(ans) - 1:
			ans2.append(0)
		else:
			ans2.append(ans[i])
	return ans2

def main():
	T = int(input())
	while T > 0:
		(n, m) = [int(x) for x in input().strip().split()]
		arr = [int(x) for x in input().strip().split()]
		brr = [int(x) for x in input().strip().split()]
		ans = getMaxandMinProduct(arr, brr, n, m)
		for i in ans:
			print(i, end=' ')
		print()
		T -= 1
if __name__ == '__main__':
	main()


from collections import Counter

def getMaxandMinProduct(A, Q, N, M):
	d = Counter(A)
	m = max(A)
	out = []
	for i in Q:
		if i == 0:
			out.append(0)
			continue
		if i == 1:
			out.append(N)
			continue
		c = 0
		for x in range(i, m + 1, i):
			c += d[x]
		out.append(c)
	return out

def main():
	T = int(input())
	while T > 0:
		(n, m) = [int(x) for x in input().strip().split()]
		arr = [int(x) for x in input().strip().split()]
		brr = [int(x) for x in input().strip().split()]
		ans = getMaxandMinProduct(arr, brr, n, m)
		for i in ans:
			print(i, end=' ')
		print()
		T -= 1
if __name__ == '__main__':
	main()


def getMaxandMinProduct(A, Q, N, M):
	ans = [0] * M
	mx = max(A)
	count = [0] * (mx + 1)
	tmp_ans = [0] * (mx + 1)
	for i in range(N):
		count[A[i]] = count[A[i]] + 1
	mxq = max(Q)
	for j in range(1, mxq + 1):
		for k in range(j, mx + 1, j):
			tmp_ans[j] = count[k] + tmp_ans[j]
	for l in range(M):
		if Q[l] > mx:
			ans[l] = 0
			continue
		ans[l] = tmp_ans[Q[l]]
	return ans


def getMaxandMinProduct(A, Q, N, M):
	answer = []
	ans = helper(A, N)
	max1 = max(A)
	for i in range(M):
		if Q[i] > max1:
			answer.append(0)
		else:
			answer.append(ans[Q[i]])
	return answer

def helper(arr, n):
	MAX = max(arr)
	ans = []
	ans = [0] * (MAX + 1)
	cnt = [0] * (MAX + 1)
	for i in range(n):
		cnt[arr[i]] += 1
	for i in range(1, MAX + 1):
		for j in range(i, MAX + 1, i):
			ans[i] += cnt[j]
	return ans


from collections import Counter

def getMaxandMinProduct(A, Q, N, M):
	m = max(max(A), max(Q))
	l = [0] * (m + 1)
	k = []
	c = [0] * (m + 1)
	for j in A:
		l[j] += 1
	for i in range(1, m + 1):
		for j in range(i, m + 1, i):
			if l[j] != 0:
				c[i] += l[j]
	for i in Q:
		k.append(c[i])
	return k


def getMaxandMinProduct(A, Q, N, M):
	maxi = max(A + Q)
	B = [0] * (maxi + 1)
	for i in A:
		B[i] += 1
	for i in range(1, maxi + 1):
		for j in range(i + i, maxi + 1, i):
			B[i] += B[j]
	L = []
	for i in Q:
		L.append(B[i])
	return L


def getMaxandMinProduct(A, Q, N, M):
	m = max(max(A), max(Q))
	l = [0] * (m + 1)
	k = []
	c = [0] * (m + 1)
	for j in A:
		l[j] += 1
	for i in range(1, m + 1):
		for j in range(i, m + 1, i):
			if l[j] != 0:
				c[i] += l[j]
	for i in Q:
		k.append(c[i])
	return k


from collections import Counter

def getMaxandMinProduct(A, Q, N, M):
	res = []
	mx = max(A)
	c = Counter(A)
	for i in Q:
		no = 0
		if not i:
			res.append(i)
			continue
		for j in range(i, mx + 1, i):
			if j in c:
				no += c[j]
		res.append(no)
	return res


import collections

def getMaxandMinProduct(a, q, N, M):
	ans = []
	mx = max(a)
	c = collections.Counter(a)
	for i in q:
		cnt = 0
		if not i:
			ans.append(0)
			continue
		if i == 1:
			ans.append(N)
			continue
		for j in range(i, mx + 1, i):
			if j in c:
				cnt += c[j]
		ans.append(cnt)
	return ans


import math

def getMaxandMinProduct(A, Q, N, M):
	MAX = max(A)
	ans = []
	ans = [0] * (MAX + 1)
	cnt = [0] * (MAX + 1)
	for i in range(N):
		cnt[A[i]] += 1
	for i in range(1, MAX + 1):
		for j in range(i, MAX + 1, i):
			ans[i] += cnt[j]
	res = []
	for i in range(M):
		if Q[i] <= MAX:
			res.append(ans[Q[i]])
		else:
			res.append(0)
	return res