Sarthak has a set S of N distinct prime numbers. He grew very fond of that set, and now he only likes a positive integer X if all of its prime factors belong to S. Given the set and a positive integer M, can you find out how many integers he likes which are not more than M?

Note: Sarthak always like the number 1.

------ Input Format ------ 

- The first line of each input contains T - the number of test cases. The test cases then follow.
- The first line of each test case contains two space-separated integers N and M - the size of S and the limit defined in the statement.
- The second line of each test case contains N space-separated integers S_{1}, S_{2}, \dots, S_{N} - the elements of S.

------ Output Format ------ 

For each test case, output on a single line the number of positive integers Sarthak likes that is not more than M. 

------ Constraints ------ 

$1 ≤ T ≤ 2$
$1 ≤ N ≤ 20$
$1 ≤ M ≤ 10^{16}$
$2 ≤ S_{i} < 1000$
$S$ has $N$ distinct prime numbers

----- Sample Input 1 ------ 
1
2 10
3 5

----- Sample Output 1 ------ 
4
----- explanation 1 ------ 
- Test case $1$: Sarthak likes the numbers $1$, $3$, $5$ and $9$.

Source: codechef | Difficulty: VERY_HARD
Tags: Sorting

Mathematics

Complete search


Solutions:
def calculate(primeset, m):
	valueset = [1]
	for x in primeset:
		i = 0
		while i < len(valueset):
			if valueset[i] * x <= m:
				valueset.append(valueset[i] * x)
			i += 1
	return valueset

def solve(primes, n, m):
	primes.sort()
	primeset1 = [primes[i] for i in range(0, n, 2)]
	primeset2 = [primes[i] for i in range(1, n, 2)]
	(valueset1, valueset2) = (calculate(primeset1, m), calculate(primeset2, m))
	valueset1.sort()
	valueset2.sort()
	(ans, start, end) = (0, 0, len(valueset2) - 1)
	while start < len(valueset1) and end >= 0:
		if valueset1[start] * valueset2[end] <= m:
			ans += end + 1
			start += 1
		else:
			end -= 1
	print(ans)
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split(' '))
	primes = list(map(int, input().split(' ')))
	solve(primes, n, m)


def getAns(s):
	v = [1]
	for x in s:
		i = 0
		while i < len(v):
			if v[i] * x <= m:
				v.append(v[i] * x)
			i += 1
	return v
t = int(input())
for _ in range(t):
	(n, m) = [int(v) for v in input().split()]
	s = sorted([int(v) for v in input().split()])
	s1 = [v for v in s[::2]]
	s2 = [v for v in s[1::2]]
	v1 = sorted(getAns(s1))
	v2 = sorted(getAns(s2))
	(ans, start, end) = (0, 0, len(v2) - 1)
	while start < len(v1) and end >= 0:
		if v1[start] * v2[end] <= m:
			ans += end + 1
			start += 1
		else:
			end -= 1
	print(ans)


import sys
input = sys.stdin.readline

def calculate(lst, m):
	d = [1]
	for x in lst:
		i = 0
		while i < len(d):
			if x * d[i] <= m:
				d.append(x * d[i])
			i += 1
	return d
for t in range(int(input())):
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	count = 0
	lst1 = [arr[i] for i in range(0, n, 2)]
	lst2 = [arr[i] for i in range(1, n, 2)]
	val1 = calculate(lst1, m)
	val2 = calculate(lst2, m)
	val1.sort()
	val2.sort()
	s = 0
	e = len(val2) - 1
	while s < len(val1) and e >= 0:
		if val1[s] * val2[e] <= m:
			count += e + 1
			s += 1
		else:
			e -= 1
	print(count)


import math

def calculate(primeSet, m):
	valueSet = [1]
	for x in primeSet:
		i = 0
		while i < len(valueSet):
			if valueSet[i] * x <= m:
				valueSet.append(valueSet[i] * x)
			i += 1
	return valueSet
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = list(map(int, input().split()))
	s.sort()
	primeSet1 = [s[i] for i in range(0, n, 2)]
	primeSet2 = [s[i] for i in range(1, n, 2)]
	valueSet1 = calculate(primeSet1, m)
	valueSet2 = calculate(primeSet2, m)
	valueSet1.sort()
	valueSet2.sort()
	ans = 0
	start = 0
	end = len(valueSet2) - 1
	while start < len(valueSet1) and end >= 0:
		if valueSet1[start] * valueSet2[end] <= m:
			ans += end + 1
			start += 1
		else:
			end -= 1
	print(ans)