Problem:


Score : 400 points

Problem Statement

Given are a sequence A= {a_1,a_2,......a_N} of N positive even numbers, and an integer M.

Let a semi-common multiple of A be a positive integer X that satisfies the following condition for every k (1 \leq k \leq N):

There exists a non-negative integer p such that X= a_k \times (p+0.5).

Find the number of semi-common multiples of A among the integers between 1 and M (inclusive).

Constraints

1 \leq N \leq 10^5

1 \leq M \leq 10^9

2 \leq a_i \leq 10^9

a_i is an even number.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
a_1 a_2 ... a_N

Output

Print the number of semi-common multiples of A among the integers between 1 and M (inclusive).

Sample Input 1

2 50
6 10

Sample Output 1

2

15 = 6  \times 2.5 

15 = 10 \times 1.5 

45 = 6  \times 7.5 

45 = 10 \times 4.5 

Thus, 15 and 45 are semi-common multiples of A. There are no other semi-common multiples of A between 1 and 50, so the answer is 2.

Sample Input 2

3 100
14 22 40

Sample Output 2

0

The answer can be 0.

Sample Input 3

5 1000000000
6 6 2 6 2

Sample Output 3

166666667



Sample input:
2 50
6 10


Sample output:
2

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,M = inputMap()
	A = inputList()

	A_ = []
	for i in A:
		if i % 2 == 1:
			print(0)
			sys.exit()
		A_.append(int(i//2))

	t = inf
	for i in A_:
		tmp = iiiiii(i)
		if t == inf:
			t = tmp
		else:
			if t == tmp:
				pass
			else:
				print(0)
				sys.exit()

	tmp = pow(2, t)
	ansMax = int(M // tmp)

	A__ = []
	for i in A_:
		A__.append(int(i // tmp))

	ansMin = inf
	for i,val in enumerate(A__):
		if i == 0:
			continue
		if i == 1:
			ansMin = lcm(val, A__[i-1])
		else:
			ansMin = lcm(val, ansMin)

	if ansMin > ansMax:
		print(0)
		sys.exit()

	ansMax /= ansMin
	print(-(-ansMax // 2))



def iiiiii(k):
	ret = 0
	while True:
		if k % 2 == 1:
			return ret
		k = int(k // 2)
		ret += 1

def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

def gcd(a, b):
	if a > b:
		a, b = b, a

	while a > 0:
		a, b = b % a, a
	return b

# a と b の最小公倍数を求める。以下の公式を使用
# a x b == (a と b の最大公約数) x (a と b の最小公売数)
def lcm(a, b):
	g = gcd(a, b)
	return a // g * b

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# N 個のボールを K グループに分ける場合のパターン数
def sunuke(N, K, mod=10**9+7):
	if N < K or K-1 < 0:
		return 0
	else:
		return combination(N-1, K-1, mod)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,M = inputMap()
	A = inputList()

	A_ = []
	for i in A:
		if i % 2 == 1:
			print(0)
			sys.exit()
		A_.append(int(i//2))

	t = inf
	for i in A_:
		tmp = iiiiii(i)
		if t == inf:
			t = tmp
		else:
			if t == tmp:
				pass
			else:
				print(0)
				sys.exit()

	tmp = pow(2, t)
	ansMax = int(M // tmp)

	A__ = []
	for i in A_:
		A__.append(int(i // tmp))
	ansMin = inf
	for i,val in enumerate(A__):
		if i == 0:
			continue
		if i == 1:
			ansMin = lcm(val, A__[i-1])
		else:
			ansMin = lcm(val, ansMin)

	if ansMin > ansMax:
		print(0)
		sys.exit()

	print(-(-ansMax // (2*ansMin)))



def iiiiii(k):
	ret = 0
	while True:
		if k % 2 == 1:
			return ret
		k = int(k // 2)
		ret += 1

def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

def gcd(a, b):
	if a > b:
		a, b = b, a

	while a > 0:
		a, b = b % a, a
	return b

# a と b の最小公倍数を求める。以下の公式を使用
# a x b == (a と b の最大公約数) x (a と b の最小公売数)
def lcm(a, b):
	g = gcd(a, b)
	return a // g * b

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# N 個のボールを K グループに分ける場合のパターン数
def sunuke(N, K, mod=10**9+7):
	if N < K or K-1 < 0:
		return 0
	else:
		return combination(N-1, K-1, mod)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,M = inputMap()
	A = inputList()

	A_ = []
	for i in A:
		if i % 2 == 1:
			print(0)
			sys.exit()
		A_.append(int(i//2))

	t = inf
	for i in A_:
		tmp = iiiiii(i)
		if t == inf:
			t = tmp
		else:
			if t == tmp:
				pass
			else:
				print(0)
				sys.exit()

	tmp = pow(2, t)
	ansMax = int(M // tmp)
	A__ = []
	for i in A_:
		A__.append(int(i // tmp))
	ansMin = inf
	for i,val in enumerate(A__):
		if i == 0:
			continue
		if i == 1:
			ansMin = lcm(val, A__[i-1])
		else:
			ansMin = lcm(val, ansMin)

	print(-(-ansMax // (2*ansMin)))



def iiiiii(k):
	ret = 0
	while True:
		if k % 2 == 1:
			return ret
		k = int(k // 2)
		ret += 1

def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

def gcd(a, b):
	if a > b:
		a, b = b, a

	while a > 0:
		a, b = b % a, a
	return b

# a と b の最小公倍数を求める。以下の公式を使用
# a x b == (a と b の最大公約数) x (a と b の最小公売数)
def lcm(a, b):
	g = gcd(a, b)
	return a // g * b

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# N 個のボールを K グループに分ける場合のパターン数
def sunuke(N, K, mod=10**9+7):
	if N < K or K-1 < 0:
		return 0
	else:
		return combination(N-1, K-1, mod)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,M = inputMap()
	A = inputList()

	A_ = []
	for i in A:
		A_.append(int(i//2))

	t = inf
	for i in A_:
		tmp = iiiiii(i)
		if t == inf:
			t = tmp
		else:
			if t == tmp:
				pass
			else:
				print(0)
				sys.exit()

	tmp = pow(2, t)
	ansMax = int(M // tmp)
	A__ = []
	for i in A_:
		A__.append(int(i // tmp))
	ansMin = inf
	for i,val in enumerate(A__):
		if i == 0:
			continue
		if i == 1:
			ansMin = lcm(val, A__[i-1])
		else:
			ansMin = lcm(val, ansMin)

	print(-(-ansMax // (2*ansMin)))



def iiiiii(k):
	ret = 0
	while True:
		if k % 2 == 1:
			return ret
		k = int(k // 2)
		ret += 1

def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

def gcd(a, b):
	if a > b:
		a, b = b, a

	while a > 0:
		a, b = b % a, a
	return b

# a と b の最小公倍数を求める。以下の公式を使用
# a x b == (a と b の最大公約数) x (a と b の最小公売数)
def lcm(a, b):
	g = gcd(a, b)
	return a // g * b

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# N 個のボールを K グループに分ける場合のパターン数
def sunuke(N, K, mod=10**9+7):
	if N < K or K-1 < 0:
		return 0
	else:
		return combination(N-1, K-1, mod)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = list(set(map(int, input().split())))

#print(A)

while not any(a % 2 for a in A):
    A = [a // 2 for a in A]

#print(A)
#print(all(a % 2 for a in A))

if not all(a % 2 for a in A):
    print(0)
    exit()
    
#print(1)

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
    
def lcm(a, b):
    return a * b // gcd(a, b)
    
ans = 1
for i in A:
    ans = lcm(ans, i)

#print(ans)
print((M // ans + 1) // 2)

Submission status: Wrong Answer

Solution code:

N, M = map(int, input().split())
A = list(set(map(int, input().split())))

#print(A)

while not any(a % 2 for a in A):
    A = [a // 2 for a in A]

#print(A)
#print(all(a % 2 for a in A))

if not all(a % 2 for a in A):
    print(0)
    exit()
    
#print(1)

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
    
def lcm(a, b):
    return a * b // gcd(a, b)
    
ans = 1
for i in A:
    ans = lcm(ans, i)

print(ans)
print((M // ans + 1) // 2)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())

A = list(set(map(int, input().split())))

# 限界まで2で割り続ける
while not any(x % 2 for x in A):
    A = [i // 2 for i in A]
    
#print(A)
#print(all(x % 2 for x in A))
 
if not all(x % 2 for x in A):
    #print("p")
    print(0)
    exit(0)
    
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
    
def lcm(a, b):
    return a * b // gcd(a, b)
    
#print(A)
    
total = 1

for x in A:
    total = lcm(total, x)
    
#print(total)

print((M // total + 1) // 2)

Submission status: Wrong Answer

Solution code:
#import sys

N, M = map(int, input().split())
A = list(set(map(int, input().split())))

N = len(A)
A = [a // 2 for a in A]

# 最小公倍数
def lcm(x, y):
    xy = x * y
    while y != 0:
        x, y = y, x % y
    return xy // x

LCM = A[0]
for i in range(1, N): # 上でA[0]使ってるから1から
    LCM = lcm(LCM, A[i])
    #print(LCM)
    
if LCM > M:
    ans = 0
else:
    M //= LCM
    ans = (M + 1) // 2

print(ans)

Submission status: Wrong Answer

Solution code:
#import sys

N, M = map(int, input().split())
A = list(set(map(int, input().split())))

N = len(A)
A = [a // 2 for a in A]

# 最小公倍数
def lcm(x, y):
    xy = x * y
    while y != 0:
        x, y = y, x % y
    return xy // x

LCM = A[0]
for i in range(1, N): # 上でA[0]使ってるから1から
    LCM = lcm(LCM, A[i])
    print(LCM)
    
if LCM > M:
    ans = 0
else:
    M //= LCM
    ans = (M + 1) // 2

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def gcd(a, b):
    if a < b:
        a, b = b, a
    
    r = a % b

    while r != 0:
        a = b
        b = r
        r = a % b
    return b


if __name__ == "__main__":
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    l = a[0]

    for i in range(n):
        g = gcd(l, a[i])
        l = l // g
        l = l * a[i]
    p = (2 * m - l) // (2 * l)
    ans = max(0, p + 1)

    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def gcd(a, b):
    if a < b:
        a, b = b, a
    
    r = a % b

    while r != 0:
        a = b
        b = r
        r = a % b
    return b


if __name__ == "__main__":
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    l = a[0]

    for i in range(n):
        g = gcd(l, a[i])
        l = l // g
        l = l * a[i]
    
    base = a[0] // 2 * l // a[0]

    if m - base < 0:
        print(0)
        sys.exit(0)
    else:
        print((m - base) // l + 1)

Submission status: Wrong Answer

Solution code:
def gcd(a, b):
    if a < b:
        a, b = b, a
    
    r = a % b

    while r != 0:
        a = b
        b = r
        r = a % b
    return b


if __name__ == "__main__":
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    l = a[0]

    for i in range(n):
        g = gcd(l, a[i])
        l = l // g
        l = l * a[i]
    
    base = a[0] // 2 * l // a[0]

    print((m - base) // l + 1)

Submission status: Wrong Answer

Solution code:
import functools

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

def multiple(a, b):
  return a*b // euclid(a, b)

def lcm(nums):
  return functools.reduce(multiple, nums)

n,m=map(int,input().split())
a=list(map(int,input().split()))
cnt=0
while a[0]%2==1:
    a[0]*=1/2
    cnt+=1
x=0
p=0
for i in range(1,n):
    k=a[i]
    while k%2==1:
        k*=1/2
        x+=1
    if x!=cnt:
        break
        print(0)
    else:
        p+=1
if p==n-1:
    ans=lcm(a)//2
    if m-ans>0:
        print((m-ans)//(ans*2)+1)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
import functools

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

def multiple(a, b):
  return a*b // euclid(a, b)

def lcm(nums):
  return functools.reduce(multiple, nums)

n,m=map(int,input().split())
a=list(map(int,input().split()))
cnt=0
while a[0]%2==1:
    a[0]*=1/2
    cnt+=1
x=0
p=0
for i in range(1,n):
    k=a[i]
    while k%2==1:
        k*=1/2
        x+=1
    if x!=cnt:
        break
        print(0)
    else:
        p+=1
if p==n-1:
    ans=lcm(a)//2
    print((m-ans)//(ans*2)+1)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())

a=list(map(int,input().split()))

a.sort()

a_com=[int(a[0]*(i+0.5)) for i in range(m//a[0]) if a[0]*(i+0.5)<=m]

ans=1

for i in range(len(a)-1):
    a_i=[int(a[i+1]*(j+0.5)) for j in range(m//a[i+1]+1) if a[i+1]*(j+0.5)<=m]
    com=set(a_com)&set(a_i)
    a_com=list(com)
    
    
    if a_com==[]:
        print(0)
        ans=0
        break
        
if ans==1:
    print(len(a_com))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())

a=list(map(int,input().split()))

a.sort()

a_com=[int(a[0]*(i+0.5)) for i in range(m//a[0]) if a[0]*(i+0.5)<m]

ans=1

for i in range(len(a)-1):
    a_i=[int(a[i+1]*(j+0.5)) for j in range(m//a[i+1]+1) if a[i+1]*(j+0.5)<=m]
    com=set(a_com)&set(a_i)
    a_com=list(com)
    
    
    if a_com==[]:
        print(0)
        ans=0
        break
        
if ans==1:
    print(len(a_com))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())

a=list(map(int,input().split()))

a_com=[int(a[0]*(i+0.5)) for i in range(m//a[0]) if a[0]*(i+0.5)<m]

ans=1

for i in range(len(a)-1):
    a_i=[int(a[i+1]*(j+0.5)) for j in range(m//a[i+1]+1) if a[i+1]*(j+0.5)<=m]
    com=set(a_com)&set(a_i)
    a_com=list(com)
    
    
    if a_com==[]:
        print(0)
        ans=0
        break
        
if ans==1:
    print(len(a_com))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
from fractions import *
A = list(map(int, input().split()))
B = [a // 2 for a in A]
l = 1
for b in B:
    l = l * b // gcd(l, b)
ans = m // (2 * l)
m -= ans * 2 * l
ans += m >= l
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
from fractions import *
A = list(map(int, input().split()))
B = [a // 2 for a in A]
g = 1
for b in B:
    g = g * b // gcd(g, b)
else:
    print(m // (2 * g) + (m % (2 * g) >= g))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
from fractions import *
A = list(map(int, input().split()))
B = [a // 2 for a in A]
g = 1
for b in B:
    g = g * b // gcd(g, b)
else:
    print(m // g - m // (2 * g))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
from fractions import *
A = list(map(int, input().split()))
B = [a // 2 for a in A]
g = 1
for b in B:
    g = g * b // gcd(g, b)
def f(x):
    return m // x + (m % x != 0)

if g % 2 == 0:
    print(f(g))
else:
    print(f(g) - f(2 * g))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
from fractions import *
A = list(map(int, input().split()))
B = [a // 2 for a in A]
g = 1
for b in B:
    g = g * b // gcd(g, b)
def f(x):
    return m // x + (m % x != 0)
print(f(g) - f(2 * g))

Submission status: Wrong Answer

Solution code:
#from math import gcd
from fractions import gcd
from functools import reduce

def lcm(a,b):
    return a * b // gcd(a,b)
def ls_lcm(A):
    return reduce(lcm ,A)
def ls_gcd(A):
    return reduce (gcd, A)

def check_two(A):
    old = None
    for n in A:
        cnt = 0
        while(n & 1 == 0):
            cnt += 1
            n = n >> 1
        if old is not None:
            old = cnt
        else:
            if old!=cnt:
                return False
    return True

N, M = map(int, input().split())
A = list(map(int, input().split()))
if not check_two(A):
    print (0)
    exit()
A = [a//2 for a in A]
half = ls_lcm(A)
print ((M + half) // (2*half))

Submission status: Wrong Answer

Solution code:
import fractions
n, m = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
  a[i] = a[i] //2
ans = a[0]
for i in range(1, n):
    ans = ans * a[i] // fractions.gcd(ans, a[i])
print((m // ans +1)//2)

Submission status: Wrong Answer

Solution code:
#from math import gcd
from fractions import gcd
from functools import reduce

def lcm(a,b):
    return a * b // gcd(a,b)
def ls_lcm(A):
    return reduce(lcm ,A)
def ls_gcd(A):
    return reduce (gcd, A)

N, M = map(int, input().split())
A = list(map(int, input().split()))
A = [a//2 for a in A]
half = ls_lcm(A)

print ((M + half) // (2*half))