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

Solution (Python):
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


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

base = B[0]

is_break = False
for b in B:
  if base % b == 0:
    if (base // b) % 2 == 0:
      is_break = True
      break
    
    continue
  
  new_base = lcm(base, b)
  if (new_base // base) % 2 == 0:
    is_break = True
    break
  
  base = new_base

if is_break:
  ans = 0
else:
  ans = M // base
  if ans%2 == 0:
    ans = ans // 2
  else:
    ans = (ans + 1) // 2


print(ans)

Solution (Python):
def a():
    N,M = map(int,input().split())
    B = list(map(lambda x: int(x)//2,input().split()))

    def gcd(n,m):
        while n:
            m,n = [n,m%n]
        return m

    su = 1
    for b in B:
        su *= b // gcd(su,b)
        if su > M:
            return 0

    for _ in filter(lambda x:(su//x)%2==0,B):
        return 0

    return M//su - M//(su*2)

print(a())

Solution (Python):
n,m = map(int,input().split())
a = list(map(int,input().split()))
cnt = 0
while True:
  if a[0] % 2 == 0:
    a[0] //= 2
    cnt += 1
  else:
    break
div = 2 ** cnt
if div != 1:
  m //= (div//2)
for i in range(1,n):
  if a[i] % div == 0:
    a[i] //= div
    if a[i] % 2 == 0:
      print(0)
      break
  else:
    print(0)
    break
  if cnt == 0:
    print(0)
    break
else:
  
  lcm = a[0]
  for i in range(1,n):
    big,sml = a[i],lcm
    while sml != 0:
      big,sml = sml,big%sml
    lcm *= a[i] // big
  
  ans = m // (2*lcm)
  
  if m % (2*lcm) >= lcm:
    ans += 1
  print(ans)

Solution (Python):

from functools import lru_cache
n, m = map(int, input().split())
aa = set(list(map(int, input().split())))

@lru_cache(maxsize=4095)
def gcd(a,b):
    if a < b:
        a, b = b, a
    while  a % b != 0:
        a, b = b, a % b
    return b
@lru_cache(maxsize=4095)
def lcm(c,d):
    return c*d // gcd(c,d)

A = set([a//2 for a in aa])

LCM = 1
for each in A:
    LCM = lcm(LCM, each)
    if LCM > m:
        print(0)
        break
else:
    for each in A:
        if (LCM // each) % 2 == 0:
            print(0)
            break
    else:
        print(m//LCM - m//(LCM*2))

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

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

a = sorted(list(set(a)))
b = [a[i]//2 for i in range(len(a))]

owa = 0
saiko = b[0]

for i in range(1,len(a)):
    t1 = b[i]
    koe = gcd(saiko,t1)
    saiko = (saiko*t1)//koe
    if (saiko//b[i])%2 == 0:
        break

for i in range(len(a)):
    check = saiko//(b[i])
    if check%2 == 0:
        owa = 1
        break

if owa == 1:
    print(0)
else:
    if (M//saiko)%2 == 0:
        print((M//saiko)//2 )
    else:
        print(((M//saiko)+1)//2)

Solution (Python):
N,M = map(int,input().split())
*A, = map(int,input().split())

def gcd(x,y):
    if y==0:return x
    return gcd(y,x%y)

def main():
    if sum([a%2 for a in A])>0:
        print(0)
        return
    n = 1
    a = A[0]
    while a%2==0:
        n*=2
        a//=2
    for a in A:
        if not(a%n==0 and a%(n*2)!=0):
            print(0)
            return
    B = [a//2 for a in A]
    lcm = B[0]
    for b in B[1:]:
        g = gcd(lcm,b)
        lcm = lcm*b//g
    ans = M//lcm
    if ans%2:
        ans = ans//2 + 1
    else:
        ans = ans//2
    print(ans)
main()

Solution (Python):
import sys
from collections import Counter
n, m = [int(i) for i in sys.stdin.readline().split()]
s_ls = [int(i) for i in sys.stdin.readline().split()]
a_ls = [i // 2 for i in s_ls]
ct = Counter(a_ls)
flg = False
for k in ct.keys():
    while k % 2 == 0 and k:
        if ct[k // 2] > 0:
            flg = True
            break
        k //= 2
if flg:
    print(0)
else:
    def gcd(a, b):
        while a and b:
            if a < b:
                b %= a
            else:
                a %= b
        return max(a, b)

    def scm(a, b):
        _gcd = gcd(a, b)
        return a * b // _gcd

    flg = True
    res = a_ls[0]
    for a in a_ls[1:]:
        res = scm(res, a)
        if res > m:
            flg = False
            break

    if flg:
        print((m - res) // (res * 2) + 1)
    else:
        print(0)

Solution (Python):
import math
import sys

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

def f(n):
    return int(n)//2

n,m=map(int,input().split())
a=list(map(f,input().split()))


tmp=1
for i in range(n):
    tmp=(tmp*a[i])//gcd(tmp,a[i])
    if tmp>m:
        print(0)
        sys.exit()


for i in range(n):
    if (tmp//a[i])%2==0:
        print(0)
        sys.exit()

ans=m//(tmp*2)
if m%(tmp*2)>=tmp: ans+=1
print(ans)

Solution (Python):
n,m=[int(j) for j in input().split()]
a=[int(j) for j in input().split()]
l=set()

for i in a:
    if i%2==0:
        l.add(i//2)
    else:
        print(0)
        exit()

c=1
l=list(l)
p=l[0]
while True:
    if p%2==0:
        c*=2
        p=p//2
    else:
        break

for i in l:
    if i%c!=0:
        print(0)
        exit()
    if (i//c)%2==0:
        print(0)
        exit()


def gcd(x,y):
    if y==0:
        return x
    else:
        return gcd(y,x%y)


def lcm(x,y):
    return x*y//gcd(x,y)

p=1
for i in l:
    p=lcm(p,i)


ans=m//p
import math
print(math.ceil(ans/2))

Solution (Python):
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
a = list(map(int,input().split()))


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

def lcm(a, b):
	return a * b // gcd (a, b)

tmp = a[0]//2
con = 0
while True:
    if tmp%2 == 0:
        tmp = tmp//2
        con += 1
    else:
        break


x = 1

for i in range(n):
    a[i] = a[i]//2

    x = lcm(a[i],x)

    tmp = a[i]
    cnt = 0
    while True:
        if tmp%2 == 0:
            tmp = tmp//2
            cnt += 1
        else:
            break
    if cnt != con:
        print(0)
        exit()

if m < x:
    print(0)
else:
    print((m-x)//(2*x)+1)

Solution (Python):
def calc_gcm(a, b):
	if a > b:
		r = a % b
		a = r
	
	while a > 0:
		r = b % a
		b = a
		a = r
	
	return b

def calc_lcm(a, b):
	gcm = calc_gcm(a, b)
	return a * b // gcm

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

lcm = 1
for a in a_list:
	lcm = calc_lcm(lcm, a)
	if lcm > 2 * M:
		lcm = 0
		break

def check():
	for a in a_list:
		if (lcm // a) % 2 == 0:
			return False
	return True

if lcm == 0:
	print(0)
elif check():
	lcm //= 2
	count = M // lcm + 1
	print(count // 2)
else:
	print(0)

Solution (Python):
import sys
def input():
	return sys.stdin.readline()[:-1]

from fractions import gcd
n, m = map(int, input().split())
a = list(map(int, input().split()))
m *= 2

if n == 1:
	print((m//a[0]+1)//2)
else:
	lcm = a[0]*a[1]//gcd(a[0], a[1])
	for i in range(2, n):
		lcm = lcm * a[i] // gcd(lcm, a[i])
		if lcm > m:
			print(0)
			sys.exit()

	divs = 0
	for x in a:
		divs += (lcm//x)%2
	if divs < n:
		print(0)
	else:
		print((m//lcm+1)//2)

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

K = []
for i, a in enumerate(A):
    k = 0
    while a%2==0:
        a//=2
        k+=1
    K.append(k)
    A[i] = a

if len(set(K))>1:
    print(0)
    exit()

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

def lcm(a,b):
    return a*b//gcd(a,b)

l = 1
for a in A:
    l = lcm(l,a)

l *= 2**K[0]
print((M+l)//(l*2))

Solution (Python):

from fractions import gcd
import math

from math import factorial as f

from math import ceil,floor,sqrt

import numpy as np

import bisect
import re
import heapq


from copy import deepcopy
import itertools


def lcm(x, y):
    return (x * y) // gcd(x, y)




from sys import exit

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))


def main():
    n,m = mi()
    a = li()
    atmp = deepcopy(a)
    cnt = [0 for i in range(n)]

    flag = True
    while flag:
        for i in range(n):
            if not a[i] % 2:
                a[i] //=2
                cnt[i]+=1
            else:
                flag = False
    cnttmp = cnt[0]
    for i in range(n):
        if not cnttmp == cnt[i]:
            print(0)
            exit()
    

    k = 1
    for i in range(n):
        atmp[i] //= 2
    for i in range(n):
        k = lcm(atmp[i],k)
        if m < k:
            print(0)
            exit()
    
    anstmp = m//k
    print(anstmp//2+anstmp%2)

    
main()

Solution (Python):
def examA():
    K, X = LI()
    if K*500>=X:
        ans = "Yes"
    else:
        ans = "No"
    print(ans)
    return

def examB():
    N = I()
    S = SI()
    ans = 0
    for i in range(N-2):
        if S[i:i+3]=="ABC":
            ans +=1
    print(ans)
    return

def examC():
    N = I()
    P = LI()
    Q = LI()
    Cp = [i for i in itertools.permutations(P,N)]; Cp.sort()
    Cq = [i for i in itertools.permutations(Q, N)]; Cq.sort()


    for k,i in enumerate(Cp):
        flag = True
        for j in range(N):
            if P[j]!=i[j]:
                flag = False
                break
        if flag:
            a = k
            break
    for k,i in enumerate(Cq):
        flag = True
        for j in range(N):
            if Q[j]!=i[j]:
                flag = False
                break
        if flag:
            b = k
            break
    ans = abs(a-b)
    print(ans)
    return

def gcd(x,y):
    if y==0:
        return x
    while(y!=0):
        x, y = y,x%y
    return x
def lcm(x, y):
    return x * y // gcd(x, y)
def examD():
    N, M = LI()
    A = LI()
    flag = 0
    for i in range(1,32):
        if A[0]%(2**i)==0:
            flag +=1
        else:
            break

    for a in A:
        cur = 0
        for i in range(1, 32):
            if a % (2 ** i) == 0:
                cur += 1
            else:
                break
        if cur!=flag:
            print(0)
            return
    cur = A[0]
    for i in range(1,N):
        cur = lcm(cur,A[i])
        if cur>2*M:
            print(0)
            return
    ans = 1 + (M-cur//2)//cur
    print(ans)
    return

def examE():
    N = I()
    C = LI()


    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

Solution (Python):
import sys
from fractions import gcd
input = sys.stdin.readline
N, M = map(int, input().split())
a = list(map(int, input().split()))
gh = 0
l = 1
dbl = [0] * N
for i in range(N):
  x = a[i]
  t = 0
  while x % 2 == 0:
    x //= 2
    t += 1
  dbl[i] = t
if max(dbl) != min(dbl):
  print(0)
  exit(0)
t = pow(2, dbl[0])
s = set()
for i in range(N):
  if a[i] in s: continue
  s.add(a[i])
  l *= a[i] // t // gcd(l, a[i])
  if l > M:
    print(0)
    exit(0)
l *= t // 2

print(M // l - M // (2 * l))

Solution (Python):
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
g = A[-1]
l = A[-1]
import fractions
for i in range(2,N+1):
    a = A[-i]
    g = fractions.gcd(l,a)
    l = l*a//g
    if l//2 > M:
        print(0)
        quit()
b = l//2
f = (M-b)//l + 1
for i in range(N):
    if b%A[i] == 0:
        f = 0
        break
if M < l//2:
    ans = 0
else:
    ans = f
print(ans)

Solution (Python):
n,m=map(int,input().split())
a=list(map(int,input().split()))
def gcd(a,b):
  while b:a,b=b,a%b
  return a
def lcm(a,b):return a*b//gcd(a,b)
l=a[0]//2
ll=a[0]
for i in range(1,n):
  if a[i]%2:odd=True
  else:even=True
  l=lcm(l,a[i]//2)
  ll=lcm(ll,a[i])
  if l>m:print(0);exit()
for i in range(n):
  if l%a[i]==0:print(0);exit()
print((m-l)//ll+1)

Solution (Python):
n,m=map(int,input().split())
a=list(map(int,input().split()))
def gcd(a,b):
  while b:a,b=b,a%b
  return a
def lcm(a,b):return a*b//gcd(a,b)
l=a[0]//2
ll=a[0]
for i in range(1,n):
  if a[i]%2:odd=True
  else:even=True
  l=lcm(l,a[i]//2)
  ll=lcm(ll,a[i])
  if l>m:print(0);exit()
for i in range(n):
  if l%a[i]==0:print(0);exit()
print((m-l)//ll+1)

Solution (Python):
n,m=map(int,input().split())
A=[int(i)//2 for i in input().split()]

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

def div2(x):
  ret=0
  while x%2==0:
    ret+=1
    x//=2
  return ret

s=div2(A[0])
chk=True

mul=A[0]
for i in range(1,n):
  if s!=div2(A[i]) or mul>m:
    chk=False
  else:
    mul=mul*A[i]//gcd(mul,A[i])
if not chk:
  print(0)
else:
  print(m//mul-m//(mul*2))

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from fractions import gcd
from functools import reduce

N,M,*A = map(int,read().split())


A = [x >> 1 for x in A]

def merge(a,b):
    g = gcd(a,b)
    a //= g; b //= g
    if a % 2 == 0:
        return 0
    if b % 2 == 0:
        return 0
    n = a * b * g
    if n > 10 ** 9:
        return 0
    return n

x = reduce(merge, A)
if x == 0:
    answer = 0
else:
    answer = (M//x) - (M//(x+x))

print(answer)

Solution (Python):
import sys
import itertools
import math
import fractions
def FRAC(a):
    ans = a[0]
    for i in range(1, len(a)):
        ans = ans * a[i] // fractions.gcd(ans, a[i])
    return ans

def main():

    N,M=list(map(int,sys.stdin.readline().split()))
    AL=list(map(int,sys.stdin.readline().split()))
    if any([a%2 for a in AL]):
        print(0)
        return

    HAL=[x//2 for x in AL]
    fr=FRAC(HAL)
    if not all([(fr//x)%2 for x in HAL]):
        print(0)
        return

    print(math.ceil((M//fr)/2))

main()

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

def lcm(a, b):
    g = gcd(a, b)
    g_a = a // g
    g_b = b // g
    return g_a * g_b * g

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



b = []
for i in range(n):
    b.append(a[i]//2)

num = 1
for i in range(n):
    num = lcm(num, b[i])
    if num > m:
        print(0)
        exit()

for i in range(n):
    if (num // b[i]) % 2 == 0:
        print(0)
        exit()


p = m // num
if p % 2 == 0:
    print(p//2)
else:
    print((p+1)//2)

Solution (Python):
from fractions import gcd
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
a = list(map(int,input().split()))
cnt = 0
while(True):
  flg = 0
  for i in range(n):
    if a[i]%2 == 0:
      if flg == 0:
        flg = 1
    if flg and a[i]%2:
      print(0)
      exit()
  if flg:
    a = [i//2 for i in a]
  else:
    break
  cnt += 1
lcm = a[0]
for i in range(n-1):
  lcm=a[i+1]*lcm//gcd(a[i+1],lcm)
  if lcm>m:
    print(0)
    exit()
print((m//(lcm*2**(cnt-1))+1)//2)

Solution (Python):
import fractions

N,M = map(int, input().split())
A = [int(a) for a in input().split()]

for i in range(N):
    A[i] //= 2
    
num = 1
f = 0
for i in range(N):
    num = num*A[i]//fractions.gcd(num, A[i])
    if num > M:
        f = 1
        break
    
for i in range(N):
    if (num//A[i])%2 == 0:
        f = 1
        break
        
if f == 0 and M >= num:
    ans = 1
    M -= num
    ans += M//(2*num)
    print(ans)
else:
    print(0)

Solution (Python):
from fractions import gcd


def solve(n, m, aaa):
    lcm = 1
    for a in aaa:
        a //= 2
        lcm *= a // gcd(lcm, a)
        if lcm > m:
            return 0
    for a in aaa:
        if int(lcm / a) == lcm / a:
            return 0
    return (m // lcm + 1) // 2


n, m = list(map(int, input().split()))
aaa = list(map(int, input().split()))

print(solve(n, m, aaa))

Solution (Python):
def GCD(a: int, b: int) -> int:
    return a if b == 0 else GCD(b, a % b)


def LCM(a: int, b: int) -> int:
    return a * b // GCD(a, b)


n, m = map(int, input().split())
a = list(map(lambda x: int(x) // 2, input().split()))

a_lcm = a[0]
for i in range(1, n):
    a_lcm = LCM(a_lcm, a[i])
    if a_lcm > m:
        break

if a_lcm <= m:
    flag = True
    for i in range(n):
        if (a_lcm // a[i]) % 2 == 0:
            flag = False
            break

    if flag:
        ans = ((m // a_lcm) + 1) // 2
    else:
        ans = 0
else:
    ans = 0
print(ans)

Solution (Python):
import fractions as f
n,m=map(int,input().split())
a=list(map(int,input().split()))
g=1
def check(n):
  cnt=0
  while n%2==0:
    n//=2
    cnt+=1
  return cnt
chk=check(a[0])
for i in a:
  if chk!=check(i):
    print(0)
    exit()
  else:
    chk=check(i)
for i in range(n):
  g=g*(a[i]//2)//(f.gcd(g,a[i]//2))
  if g>m:print(0);exit()
print(m//g-m//(2*g))

Solution (Python):


import sys
sys.setrecursionlimit(300000)


def solve(N: int, M: int, a: "List[int]"):
    def gcd(a, b):
        return a if b == 0 else gcd(b, a % b)
    g = a[0]
    for v in a:
        tmp = gcd(g, v)
        g = g * v // tmp
        if M < g // 2:
            print(0)
            return
    for v in a:
        if (g // v) % 2 == 0:
            print(0)
            return
    M -= g // 2
    ret = M // g + 1
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    a = [int(next(tokens)) for _ in range(N)]  
    solve(N, M, a)

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    from fractions import gcd
    input = sys.stdin.readline

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

    A_ = [a//2 for a in A]
    lcm = A_[0]
    t_num = 0
    a = A_[0]
    while a % 2 == 0:
        t_num += 1
        a //= 2
    for a in A_:
        lcm = (lcm * a) // gcd(a, lcm)
        t_n = 0
        while a % 2 == 0:
            t_n += 1
            a //= 2
        if t_n != t_num:
            print(0)
            exit()
    ans = K // lcm
    print((ans+1)//2)


if __name__ == '__main__':
    main()

Solution (Python):
import fractions

n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):
    a[i]//=2

max=[0]*n

for i in range(n):
    wari=a[i]
    for j in range(100):
        if(wari%2==0):
            max[i]+=1
            wari//=2
        else:
            break

kanou=True
for i in range(1,n):
    if(max[i]!=max[0]):
        kanou=False
        break

if(not kanou):
    print(0)
else:
    kobai=a[0]
    for i in range(1,n):
        kobai=kobai*a[i]//fractions.gcd(kobai,a[i])
        if(kobai>m):
            break
    ans=1+((m-kobai)//(kobai*2))
    print(ans)

Solution (Python):


import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read


n,m = [int(i) for i in readline().split()]
a = [int(i)//2 for i in read().split()]

from fractions import gcd

def num_of_2(x):
    c = 0
    while x%2 == 0:
        c += 1
        x//=2
    return c

a0 = num_of_2(a[0])
if any([num_of_2(i) != a0 for i in a]):
    print(0)
else:
    def lcm(x,y):
        return x//(gcd(x,y))*y
    
    c = 1
    INF = 10**18
    for i in a:
        c = lcm(c,i)
        if c >= INF: break
    
    
    ans = m//c    
    
    print((ans+1)//2)

Solution (Python):
from fractions import gcd

N,M=map(int,input().split())
b=[int(i)//2 for i in input().split()]
def v2(n):
    tmp=n
    res=0
    while(tmp>0):
        if tmp%2==0:
            tmp=tmp//2
            res+=1
        else:
            return res
def lcm(x,y):
    return x*(y//gcd(x,y))
c=[v2(i) for i in b]
if min(c)!=max(c):
    print(0)
    exit()
L=1
for i in range(N):
    L=lcm(L,b[i])
print(M//L-M//(2*L))