Given $\mbox{1}$ friendly number and $n$ unfriendly numbers, determine how many numbers are divisors of the friendly number but not the unfriendly numbers.

Input Format

The first line contains $2$ space-separated integers, $n$ (the number of unfriendly numbers) and $\mbox{f}$ (the friendly number), respectively. 
The second line contains $n$ space-separated unfriendly numbers.

Constraints

$1\leq n\leq10^{6}$
$1\leq f\leq10^{13}$
$1\leq\textit{unfriendly numbers}\leq10^{18}$

Output Format

Print the the number of unique divisors of $\mbox{f}$ (i.e.: divisors that are not shared with those of the unfriendly numbers) as a single integer.

Sample Input
8 16
2 5 7 4 3 8 3 18

Sample Output
1

Explanation

There are $n=8$ unfriendly numbers: $2,5,7,4,3,8,3,18$. 

Our friendly number, $\mbox{f}$, is $\mbox{16}$, and its even divisors are $1,2,4,8,16$. 

Let $\textit{count}$ be the number of friendly divisors that are not also unfriendly divisors. Let's determine which divisors of $\mbox{f}$ are not also divisors of the unfriendly numbers:

$\mbox{1}$ is a divisor of all unfriendly numbers, so we disregard it.   
$2$ is a divisor of unfriendly numbers $2$, $\begin{array}{c}4\end{array}$, and $8$, so we disregard it.
$\begin{array}{c}4\end{array}$ is a divisor of unfriendly numbers $\begin{array}{c}4\end{array}$ and $8$, so we disregard it.
$8$ is a divisor of unfriendly number $8$, so we disregard it. 
$\mbox{16}$ is not a divisor of any unfriendly number, so we increment $\textit{count}$ to $\mbox{1}$.

As there are no more friendly divisors to check, we print the value of $\textit{count}$ (which is $\mbox{1}$) on a new line.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Number theory


Solutions:
from fractions import gcd
(nU, F) = [int(i) for i in input().strip().split()]
Us = [int(i) for i in input().strip().split()]
divs = []
for i in range(1, int(F ** 0.5)):
	if F % i == 0:
		divs.append(i)
		divs.append(F // i)
if int(F ** 0.5) == F ** 0.5:
	divs.append(int(F ** 0.5))
ndivs = {}
for i in Us:
	ndivs[gcd(F, i)] = 1
ndivs = [i for i in ndivs]
rt = 0
for i in divs:
	for j in ndivs:
		if j % i == 0:
			break
	else:
		rt += 1
print(rt)


import math
import fractions

def factorset(x):
	factors = set([x])
	sqrtX = int(math.sqrt(x))
	for i in range(1, sqrtX + 1):
		if x % i == 0:
			factors.add(i)
			factors.add(x / i)
	return factors

def main():
	(numUnfriendlies, friendly) = [int(i) for i in input().split()]
	unfriendlies = [int(i) for i in input().split()]
	friendlyFactors = factorset(friendly)
	unfriendlyFactors = set()
	for unfriendly in unfriendlies:
		g = fractions.gcd(friendly, unfriendly)
		unfriendlyFactors.add(g)
		unfriendlyFactors.update(factorset(g))
	print(len(friendlyFactors - unfriendlyFactors))
main()


from math import sqrt, ceil
from fractions import gcd

def main():
	(n, k) = (int(i) for i in input().split())
	unfriendly = [int(i) for i in input().split()]
	friendlyFactors = factorize(k)
	unfriendlyFactors = set()
	for i in unfriendly:
		g = gcd(k, i)
		unfriendlyFactors.add(g)
		unfriendlyFactors.update(factorize(g))
	print(len(friendlyFactors.difference(unfriendlyFactors)))

def factorize(n):
	factors = set()
	for i in range(1, ceil(sqrt(n)) + 1):
		if n % i == 0:
			factors.add(i)
			factors.add(n // i)
	return factors
main()


from math import sqrt, floor

def GCD(a, b):
	return GCD(b % a, a) if a else b
(n, k) = list(map(int, input().split()))
lis = list(map(int, input().split()))
lis = list(map(lambda x: GCD(x, k), lis))
dk = 0
for x in range(1, floor(sqrt(k)) + 1):
	if k % x == 0:
		if x * x == k:
			dk += 1
		else:
			dk += 2
S = set([1])
for x in lis:
	for i in range(1, floor(sqrt(x)) + 1):
		if x % i == 0:
			S.add(i)
			S.add(x // i)
print(dk - len(S))


from math import ceil, sqrt

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

def unfriendlyNumbers(uf_nums, k):
	friendly_factors = set()
	for factor in range(1, ceil(sqrt(k))):
		if k % factor == 0:
			friendly_factors.add(factor)
			friendly_factors.add(k // factor)
	if sqrt(k) == int(sqrt(k)):
		friendly_factors.add(int(sqrt(k)))
	for uf_num in uf_nums:
		g = gcd(uf_num, k)
		for factor in range(1, ceil(sqrt(g))):
			if g % factor == 0:
				if factor in friendly_factors:
					friendly_factors.remove(factor)
				mate = g // factor
				if mate in friendly_factors:
					friendly_factors.remove(mate)
		if sqrt(g) == int(sqrt(g)) and int(sqrt(g)) in friendly_factors:
			friendly_factors.remove(int(sqrt(g)))
	return len(friendly_factors)
a = input().strip()
a = list(map(int, a.split(' ')))
_a_size = a[0]
_k = a[1]
b = input().strip()
b = list(map(int, b.split(' ')))
print(unfriendlyNumbers(b, _k))


def gcd(a, b):
	while b != 0:
		t = b
		b = a % b
		a = t
	return a
(n, friendly) = map(int, input().split())
unfriendlies = set(map(int, input().split()))
unfriendlies = set([gcd(u, friendly) for u in unfriendlies])
divisors = set([friendly])
for i in range(2, int(friendly ** 0.5) + 1):
	if friendly % i == 0:
		divisors.add(i)
		divisors.add(friendly // i)
divisors -= unfriendlies
count = 0
for d in divisors:
	if any((u % d == 0 for u in unfriendlies)):
		continue
	else:
		count += 1
print(count)


import math

def gdc(a, b):
	while b != 0:
		t = b
		b = a % b
		a = t
	return a

def unfriendlyNumbers(a, k):
	s = {k}
	for i in range(2, int(math.sqrt(k)) + 1):
		if k % i == 0:
			s.add(i)
			s.add(k // i)
	for i in a:
		gd = gdc(k, i)
		if gd > 1 and gd in s:
			s.remove(gd)
			sd = set()
			for si in s:
				if i % si == 0:
					sd.add(si)
			s.difference_update(sd)
			if len(s) == 0:
				break
	answer = len(s)
	return answer
a = input().strip()
a = list(map(int, a.split(' ')))
_a_size = a[0]
_k = a[1]
b = input().strip()
b = list(map(int, b.split(' ')))
print(unfriendlyNumbers(b, _k))


import math
(_, f) = input().strip().split(' ')
f = int(f)
unfriendlies = [int(v) for v in input().strip().split(' ')]

def divisors(n):
	divs = set()
	for i in range(1, round(math.sqrt(n)) + 2):
		if n % i == 0:
			divs.add(i)
			divs.add(int(n / i))
	return divs

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
unique_divisors_of_f = divisors(f)
gcds = set()
for n in unfriendlies:
	cd = gcd(f, n)
	if cd in gcds:
		continue
	gcds.add(cd)
	unique_divisors_of_f -= divisors(cd)
print(len(unique_divisors_of_f))


def factor(a):
	L = []
	if a > 1:
		p = 2
		lastPrime = 1
		count = 0
		while p * p <= a:
			if a % p == 0:
				if lastPrime == p:
					count += 1
				else:
					if lastPrime != 1:
						L.append((lastPrime, count))
					count = 1
					lastPrime = p
				a //= p
			elif p == 2:
				p = 3
			else:
				p += 2
		if lastPrime == a:
			L.append((lastPrime, count + 1))
		else:
			if lastPrime != 1:
				L.append((lastPrime, count))
			L.append((a, 1))
	return L

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

def countDivisors(factors):
	prod = 1
	for (p, exp) in factors:
		prod *= exp + 1
	return prod
tokens = input().split()
n = int(tokens[0])
friendly = int(tokens[1])
factors = factor(friendly)
tokens = input().split()
unfriendlies = list(map(int, tokens))
divisorSet = set([])
for unfriendly in unfriendlies:
	unfriendly = gcd(friendly, unfriendly)
	if unfriendly not in divisorSet:
		L = []
		lim = int(unfriendly ** 0.5) + 1
		for d in range(1, lim):
			if unfriendly % d == 0:
				L.append(d)
				L.append(unfriendly // d)
		divisorSet |= set(L)
print(countDivisors(factors) - len(divisorSet))


from math import sqrt
from fractions import gcd

def found_match(g, x):
	for i in g:
		if i % x == 0:
			return True
	return False

def factor(n):
	factors = set()
	for x in range(1, int(sqrt(n)) + 1):
		if n % x == 0:
			factors.add(x)
			factors.add(n // x)
	return sorted(factors)

def filter_factors(fac, g):
	ans = set()
	for v in fac:
		if not found_match(g, v):
			ans.add(v)
	return ans

def unfriendlyNumbers(a, k):
	g = set([gcd(k, x) for x in a])
	fac = factor(k)
	answer = filter_factors(fac, g)
	return len(answer)
a = input().strip()
a = list(map(int, a.split(' ')))
_a_size = a[0]
_k = a[1]
b = input().strip()
b = list(map(int, b.split(' ')))
print(unfriendlyNumbers(b, _k))


import math

def unfriendlyNumbers(a, n):

	def factor(x):
		factors = {x}
		for i in range(1, int(math.sqrt(x)) + 1):
			if not x % i:
				factors.add(i)
				factors.add(int(x / i))
		return factors

	def gcd(a, b):
		while b:
			(a, b) = (b, a % b)
		return a
	f = factor(n)
	s = set()
	for ufn in list(set(a)):
		x = gcd(n, ufn)
		fact = factor(x)
		s.add(x)
		s.update(fact)
	return len(f ^ s)
a = input().strip()
a = list(map(int, a.split(' ')))
_a_size = a[0]
_k = a[1]
b = input().strip()
b = list(map(int, b.split(' ')))
print(unfriendlyNumbers(b, _k))


def factor(a):
	L = []
	if a > 1:
		p = 2
		lastPrime = 1
		count = 0
		while p * p <= a:
			if a % p == 0:
				if lastPrime == p:
					count += 1
				else:
					if lastPrime != 1:
						L.append((lastPrime, count))
					count = 1
					lastPrime = p
				a //= p
			elif p == 2:
				p = 3
			else:
				p += 2
		if lastPrime == a:
			L.append((lastPrime, count + 1))
		else:
			if lastPrime != 1:
				L.append((lastPrime, count))
			L.append((a, 1))
	return L

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

def countDivisors(factors):
	prod = 1
	for (p, exp) in factors:
		prod *= exp + 1
	return prod
tokens = input().split()
n = int(tokens[0])
friendly = int(tokens[1])
factors = factor(friendly)
tokens = input().split()
unfriendlies = list(map(int, tokens))
divisorSet = set([])
for unfriendly in unfriendlies:
	unfriendly = gcd(friendly, unfriendly)
	if unfriendly not in divisorSet:
		L = []
		lim = int(unfriendly ** 0.5) + 1
		for d in range(1, lim):
			if unfriendly % d == 0:
				L.append(d)
				L.append(unfriendly // d)
		divisorSet |= set(L)
print(countDivisors(factors) - len(divisorSet))


from fractions import gcd
(nU, F) = [int(i) for i in input().strip().split()]
Us = [int(i) for i in input().strip().split()]
divs = []
for i in range(1, int(F ** 0.5)):
	if F % i == 0:
		divs.append(i)
		divs.append(F // i)
if int(F ** 0.5) == F ** 0.5:
	divs.append(int(F ** 0.5))
ndivs = {}
for i in Us:
	ndivs[gcd(F, i)] = 1
ndivs = [i for i in ndivs]
rt = 0
for i in divs:
	for j in ndivs:
		if j % i == 0:
			break
	else:
		rt += 1
print(rt)


import math

def factorsf(x):
	factors = set([x])
	sqrtX = int(math.sqrt(x))
	for i in range(1, sqrtX + 1):
		if x % i == 0:
			factors.add(i)
			factors.add(x // i)
	return factors
(n, f) = [int(i) for i in input().split()]
uf = [int(i) for i in input().split()]
ff = factorsf(f)
uff = set()
for x in uf:
	ab = math.gcd(x, f)
	uff.add(ab)
	uff.update(factorsf(ab))
print(len(ff - uff))


import math
nf = list(map(int, input().split()))
unf_list = set(map(int, input().split()))
f_num = nf[1]
n = f_num
divisors = set()
for i in range(1, int(math.sqrt(n)) + 1):
	if n % i == 0:
		divisors.add(i)
		divisors.add(n // i)
gcds = set((math.gcd(i, f_num) for i in unf_list))
factors = []
for div in divisors:
	for val in gcds:
		if val % div == 0:
			factors.append(div)
			break
print(len(divisors) - len(factors))


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
count = 0
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
(factors, gcds) = (list(factors), list(gcds))
ans = set()
gcds.sort()
factors.sort()
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans.add(i)
print(len(ans))


from math import *
(n, f) = map(int, input().split())
arr = list(map(int, input().split()))
c = set()
for i in range(1, int(f ** 0.5) + 1):
	if f % i == 0:
		c.add(i)
		c.add(int(f / i))
d = set()
for i in arr:
	res = gcd(i, f)
	if res != 1:
		d.add(res)
e = list(d)
for i in e:
	tot = i
	for j in range(2, int(tot ** 0.5) + 1):
		if i % j == 0:
			if j == i / j:
				d.add(j)
			else:
				d.add(j)
				d.add(i / j)
resm = c - d
print(len(resm) - 1)


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math

def Divisors(n):
	res = []
	i = 1
	while i <= math.ceil(math.sqrt(n)):
		if n % i == 0:
			if n // i == i:
				res.append(i)
			else:
				res.append(i)
				res.append(n // i)
		i = i + 1
	return res
(m, n) = map(int, input().split())
l = [int(x) for x in input().split()]
res = Divisors(n)
gcds = set()
f = 0
c = 0
for x in l:
	gcds.add(math.gcd(n, x))
for i in res:
	f = 0
	for j in gcds:
		if j % i == 0:
			f = -1
			break
	if f == 0:
		c += 1
print(c)


import math
from collections import Counter
is_prime = None

def sieve(n):
	global is_prime
	limit = math.ceil(math.sqrt(n))
	is_prime = [True for _ in range(limit + 1)]
	is_prime[0] = False
	is_prime[1] = False
	for i in range(math.ceil(math.sqrt(limit)) + 1):
		if is_prime[i]:
			for j in range(i * i, limit + 1, i):
				is_prime[j] = False

def sieve_iter(n):
	limit = math.ceil(math.sqrt(n))
	is_prime = [True for _ in range(limit + 1)]
	is_prime[0] = False
	is_prime[1] = False
	sqrt_limit = math.ceil(math.sqrt(limit)) + 1
	for i in range(sqrt_limit):
		if is_prime[i]:
			yield i
			for j in range(i * i, limit + 1, i):
				is_prime[j] = False
	remaining_primes = is_prime[sqrt_limit:]
	remaining_primes = enumerate(remaining_primes)
	remaining_primes = (pair[0] + sqrt_limit for pair in remaining_primes if pair[1])
	yield from remaining_primes

def get_complete_factorization(f):
	possible_primes = sieve_iter(f)
	prime_amounts = Counter()
	try:
		while f > 1:
			current_prime = next(possible_primes)
			while f % current_prime == 0:
				prime_amounts[current_prime] += 1
				f = f // current_prime
	except StopIteration:
		prime_amounts[f] += 1
	return prime_amounts

def get_partial_factorization(u, primes_to_use):
	prime_amounts = Counter()
	for current_prime in primes_to_use:
		while u % current_prime == 0:
			prime_amounts[current_prime] += 1
			u = u // current_prime
		if u == 1:
			break
	return prime_amounts

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

def generate_divisors(current_index, current_divisor, factors):
	if current_index == len(factors):
		yield current_divisor
	else:
		for i in range(factors[current_index][1] + 1):
			yield from generate_divisors(current_index + 1, current_divisor, factors)
			current_divisor *= factors[current_index][0]

def main(friendly, unfriendlies):
	friendly_factors = get_complete_factorization(friendly)
	unfriendlies = set((gcd(friendly, u) for u in unfriendlies))
	divisors_of_friendly = generate_divisors(0, 1, list(friendly_factors.items()))
	count = 0
	for divisor in divisors_of_friendly:
		divides_any = False
		for unfriendly in unfriendlies:
			if unfriendly % divisor == 0:
				divides_any = True
		if not divides_any:
			count += 1
	print(count)

def get_input():
	(n, friendly) = [int(num) for num in input().split()]
	unfriendlies = [int(num) for num in input().split()]
	main(friendly, unfriendlies)
get_input()

def test_get_complete_factorization(n):
	for i in range(1, n):
		factorization = get_complete_factorization(i).elements()
		product = 1
		for factor in factorization:
			product *= factor
		if product != i:
			print(f'{i} does not work')


import math
from collections import Counter
is_prime = None

def sieve(n):
	global is_prime
	limit = math.ceil(math.sqrt(n))
	is_prime = [True for _ in range(limit + 1)]
	is_prime[0] = False
	is_prime[1] = False
	for i in range(math.ceil(math.sqrt(limit)) + 1):
		if is_prime[i]:
			for j in range(i * i, limit + 1, i):
				is_prime[j] = False

def sieve_iter(n):
	limit = math.ceil(math.sqrt(n))
	is_prime = [True for _ in range(limit + 1)]
	is_prime[0] = False
	is_prime[1] = False
	sqrt_limit = math.ceil(math.sqrt(limit)) + 1
	for i in range(sqrt_limit):
		if is_prime[i]:
			yield i
			for j in range(i * i, limit + 1, i):
				is_prime[j] = False
	remaining_primes = is_prime[sqrt_limit:]
	remaining_primes = enumerate(remaining_primes)
	remaining_primes = (pair[0] + sqrt_limit for pair in remaining_primes if pair[1])
	yield from remaining_primes

def get_complete_factorization(f):
	possible_primes = sieve_iter(f)
	prime_amounts = Counter()
	try:
		while f > 1:
			current_prime = next(possible_primes)
			while f % current_prime == 0:
				prime_amounts[current_prime] += 1
				f = f // current_prime
	except StopIteration:
		prime_amounts[f] += 1
	return prime_amounts

def get_partial_factorization(u, primes_to_use):
	prime_amounts = Counter()
	for current_prime in primes_to_use:
		while u % current_prime == 0:
			prime_amounts[current_prime] += 1
			u = u // current_prime
		if u == 1:
			break
	return prime_amounts

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

def generate_divisors(current_index, current_divisor, factors):
	if current_index == len(factors):
		yield current_divisor
	else:
		for i in range(factors[current_index][1] + 1):
			yield from generate_divisors(current_index + 1, current_divisor, factors)
			current_divisor *= factors[current_index][0]

def main(friendly, unfriendlies):
	friendly_factors = get_complete_factorization(friendly)
	unfriendlies = set((gcd(friendly, u) for u in unfriendlies))
	divisors_of_friendly = generate_divisors(0, 1, list(friendly_factors.items()))
	count = 0
	for divisor in divisors_of_friendly:
		divides_any = False
		for unfriendly in unfriendlies:
			if unfriendly % divisor == 0:
				divides_any = True
		if not divides_any:
			count += 1
	print(count)

def get_input():
	(n, friendly) = [int(num) for num in input().split()]
	unfriendlies = [int(num) for num in input().split()]
	main(friendly, unfriendlies)
get_input()

def test_get_complete_factorization(n):
	for i in range(1, n):
		factorization = get_complete_factorization(i).elements()
		product = 1
		for factor in factorization:
			product *= factor
		if product != i:
			print(f'{i} does not work')


import math
from collections import Counter
is_prime = None

def sieve(n):
	global is_prime
	limit = math.ceil(math.sqrt(n))
	is_prime = [True for _ in range(limit + 1)]
	is_prime[0] = False
	is_prime[1] = False
	for i in range(math.ceil(math.sqrt(limit)) + 1):
		if is_prime[i]:
			for j in range(i * i, limit + 1, i):
				is_prime[j] = False

def sieve_iter(n):
	limit = math.ceil(math.sqrt(n))
	is_prime = [True for _ in range(limit + 1)]
	is_prime[0] = False
	is_prime[1] = False
	sqrt_limit = math.ceil(math.sqrt(limit)) + 1
	for i in range(sqrt_limit):
		if is_prime[i]:
			yield i
			for j in range(i * i, limit + 1, i):
				is_prime[j] = False
	remaining_primes = is_prime[sqrt_limit:]
	remaining_primes = enumerate(remaining_primes)
	remaining_primes = (pair[0] + sqrt_limit for pair in remaining_primes if pair[1])
	yield from remaining_primes

def get_complete_factorization(f):
	possible_primes = sieve_iter(f)
	prime_amounts = Counter()
	try:
		while f > 1:
			current_prime = next(possible_primes)
			while f % current_prime == 0:
				prime_amounts[current_prime] += 1
				f = f // current_prime
	except StopIteration:
		prime_amounts[f] += 1
	return prime_amounts

def get_partial_factorization(u, primes_to_use):
	prime_amounts = Counter()
	for current_prime in primes_to_use:
		while u % current_prime == 0:
			prime_amounts[current_prime] += 1
			u = u // current_prime
		if u == 1:
			break
	return prime_amounts

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

def generate_divisors(current_index, current_divisor, factors):
	if current_index == len(factors):
		yield current_divisor
	else:
		for i in range(factors[current_index][1] + 1):
			yield from generate_divisors(current_index + 1, current_divisor, factors)
			current_divisor *= factors[current_index][0]

def main(friendly, unfriendlies):
	friendly_factors = get_complete_factorization(friendly)
	unfriendlies = set((gcd(friendly, u) for u in unfriendlies))
	divisors_of_friendly = generate_divisors(0, 1, list(friendly_factors.items()))
	count = 0
	for divisor in divisors_of_friendly:
		divides_any = False
		for unfriendly in unfriendlies:
			if unfriendly % divisor == 0:
				divides_any = True
		if not divides_any:
			count += 1
	print(count)

def get_input():
	(n, friendly) = [int(num) for num in input().split()]
	unfriendlies = [int(num) for num in input().split()]
	main(friendly, unfriendlies)
get_input()

def test_get_complete_factorization(n):
	for i in range(1, n):
		factorization = get_complete_factorization(i).elements()
		product = 1
		for factor in factorization:
			product *= factor
		if product != i:
			print(f'{i} does not work')


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math
import os
import random
import re
import sys
import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)


import math
[n, f] = list(map(lambda x: int(x), input().split()))
l = list(map(lambda x: int(x), input().split()))
gcds = set()
factors = set()
for i in l:
	gcds.add(math.gcd(i, f))
for i in range(1, math.ceil(math.sqrt(f))):
	if f % i == 0:
		factors.add(i)
		factors.add(f // i)
ans = 0
for i in factors:
	for j in gcds:
		if j % i == 0:
			break
		else:
			continue
	else:
		ans += 1
print(ans)