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):
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
import numpy as np
from collections import deque, Counter, defaultdict
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
from functools import reduce
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
def lcm_base(a, b):
    return (a * b) // gcd(a, b)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


def main():
  n, m = map(int, readline().split())
  a = np.array(input().split(), np.int64)
  a //= 2
  b=np.copy(a)
  while True:
    c = b%2
    if c.sum() == 0:
      b //= 2
    elif c.sum() == n:
      break
    else:
      print(0)
      sys.exit()
  d = lcm_list(a)
  if d>10**9:
    ans = 0
  else:
    ans = (m//d) - (m//(d+d))
  print(ans)
  
  
  
if __name__ == '__main__':
  main()

Solution (Python):
import sys
import numpy as np
from fractions import gcd
from functools import reduce
import io
import math

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()

N, M = rl()
A = np.array(rl())
B = A // 2

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

x = reduce(merge, B)
if x == 0:
    answer = 0
else:
    answer = M // x - M // (2*x)

print(answer)

Solution (Python):
from fractions import gcd
n, m = map(int, input().split())
a = [i//2 for i in map(int, input().split())]
z = []
for i in a:
    n = 0
    while i%2==0:
        i //= 2
        n += 1
    z.append(n)
if all(z[0]==i for i in z):
    x = 1
    for i in a:
        x = (x*i)//gcd(x, i)
    result = -(-(m//x)//2)
    print(result)
else:
    print(0)

Solution (Python):
from fractions import gcd

N, M = map(int, input().split())
A = list(map(int, input().split()))
flag = False
n = 1


for i in range(N):
    A[i] //= 2

for i in range(N):
    n *= A[i]//gcd(n, A[i])
    
    if n>M:
        flag = True
        break

for i in range(N):
    if (n//A[i])%2==0:
        flag = True
        break

if flag==False and M>=n:
    ans = 1
    M -= n
    ans += M//(2*n)
    print(ans)
else:
    print(0)

Solution (Python):
from fractions import gcd

def main():
    N,M=map(int,input().split())
    a=[int(_) for _ in input().split()]
    flag=0
    n=1

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

    for i in range(N):
        n=n*a[i]//gcd(n,a[i])
        if n>M:
            flag=1
            break

    for i in range(N):
        if (n//a[i])%2==0:
            flag=1
            break

    if flag==0 and M>=n:
        ans=1
        M-=n
        ans+=M//(2*n)
        print(ans)
    else:
        print(0)

main()

Solution (Python):
n, m = map(int, input().split())
a_li = list(map(int, input().split()))

a_li = [a // 2 for a in a_li]

from fractions import gcd

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

def count_div_2(a):
    cnt = 0
    while a % 2 == 0:
        a = a // 2
        cnt += 1
    return cnt


a_lcm = 1
cnt_div = count_div_2(a_li[0])


flag = False
for a in a_li:
    a_lcm = lcm(a, a_lcm)
    
    if cnt_div != count_div_2(a) or a_lcm > m:
        flag = True
        break


if flag:
    ans = 0
else:
    ans = m // a_lcm
    ans = ans // 2 + ans % 2

print(ans)

Solution (Python):
import fractions
import math
from functools import reduce
import sys
sys.setrecursionlimit(10**8)


def lcm2(x, y):
    return (x * y) // fractions.gcd(x, y)


def lcm(numbers):
    return reduce(lcm2, numbers)


n, m = map(int, input().split())
a = list(map(int, input().split()))
count = 0
while all(x % 2 == 0 for x in a):
    count += 1
    a = list(map(lambda x: x//2, a))

if any(x % 2 == 0 for x in a):
    print(0)
    exit()

lcm = lcm(a)
print(m // (lcm * (2 ** (count - 1))) - m // (lcm * (2 ** count)))

Solution (Python):


import sys
import math










from fractions import gcd                    


def main():
    mod = 10000007                  
    inf = float('inf')
    input = sys.stdin.readline      
    sys.setrecursionlimit(10**6)    
    def ii():  return int(input())
    def mi():  return map(int, input().rstrip().split())
    def lmi(): return list(map(int, input().rstrip().split()))
    def li():  return list(input().rstrip())
    
    
    def my_divide(num, count=0):
        if num % 2 == 0:
            return my_divide(num//2, count+1)
        else:
            return count
    
    def calc_lcm(x, y):
        return (x * y) // gcd(x, y)
        

    n, m = mi()
    a = lmi()
    b = [elm//2 for elm in a]
    num_two = [None] * n
    divided_by_pow_two = [None] * n
    

    for i in range(n):
        num = my_divide(b[i])
        num_two[i] = num
        divided_by_pow_two[i] = b[i] // (2 ** num)
    
    

    if len(set(num_two)) != 1:
        print(0)
    else:
        lcm = divided_by_pow_two[0]
        for elm in divided_by_pow_two:
            lcm = calc_lcm(lcm, elm)
        lcm *= (2 ** num_two[0])
        
        print(math.ceil((m // lcm) / 2))
            

if __name__ == "__main__":
    main()

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

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

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

cur = a[0]
for x in a[1:]:
    g = gcd(cur, x)
    if (cur // 2) % g != (x // 2) % g:
        print(0)
        sys.exit(0)
    else:
        cur = cur // g * x
    if cur > m * 2:
        print(0)
        sys.exit(0)

print((m + cur // 2) // cur)

Solution (Python):
import sys
from fractions import gcd

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))


N, M = lr()
A = lr()
A = [x // 2 for x in A]
cnt = 0
while all(x%2 == 0 for x in A):
    cnt += 1
    A = [x // 2 for x in A]

if any(x%2 == 0 for x in A):
    print(0); exit()

lcm = 1
for a in A:
    lcm *= a // gcd(lcm, a)

answer = M // (2 ** cnt * lcm) - M // (2 ** (cnt+1) * lcm)
print(answer)

Solution (Python):


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

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

def f(x):
    res = 0
    while x % 2 == 0:
        x //= 2
        res += 1
    return res 

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

    t = f(a[0])
    for i in range(n):
        if f(a[i]) != t:
            print(0)
            return
        a[i] //= 2**t; 

    m //= 2**t
    l = 1
    for i in range(n):
        l = lcm(l, a[i])
        if l > m:
            print(0)
            return

    m //= l
    ans = (m+1)//2
    print(ans)
main()

Solution (Python):

a = [0] * int(1e5 + 100)

def _gcd(a, b):
    if a % b == 0 : return b
    if b % a == 0 : return a
    while a != 1 and b != 1:
        if a > b: a %= b
        else : b %= a
        if a % b == 0: return b
        if b % a == 0: return a


n, m = (int(s) for s in input().split())

inp = input().split()
for i in range(1, n + 1) :
    a[i] = int(inp[i - 1])

flag = False
lcm = a[1]

for i in range(2, n + 1) :
    gcd = _gcd(lcm, a[i])
    lcm = int(lcm * a[i] / gcd)
    if(lcm > 2 * m):
        flag = True
        break

for i in range (1, n + 1):
    if int(lcm / a[i]) % 2 == 0 : flag = True

if flag : print(0)
else : print(int( (m - int(lcm / 2)) / lcm ) + 1)

Solution (Python):
N,M = map(int, input().split())
As = list(map(int, input().split()))

Bs = [a//2 for a in As]

b = Bs[0]
beki2 = 0
while b % 2 == 0:
    b //= 2
    beki2 += 1

for b in Bs[1:]:
    n = 0
    while b % 2 == 0:
        b //= 2
        n += 1
    if beki2 != n : 
        print(0)
        exit()

def gcd(n, m):
    
    a = max(n,m)
    b = min(n,m)
    while b:
        a, b = b, a % b
    return a

lcd = 1
for b in Bs:
    lcd = (lcd * b) // gcd(lcd, b)

ans = M / (2*lcd) + 1/2
print(int(ans))

Solution (Python):
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=[]
for i in a:
    b.append(i//2)
import fractions
l=1
for i in b:
    d=fractions.gcd(i,l)
    l=i*l//d
    if l>m:
        print(0)
        sys.exit()
for i in b:
    if (l//i)%2==0:
        print(0)
        sys.exit()
x=m//l
if x%2==0:
    print(x//2)
else:
    print(x//2+1)

Solution (Python):
from fractions import gcd
from functools import reduce

n, m = map(int, input().split())
a = [int(i) for i in input().split()]
c = 1
while a[0] % 2 == 0:
    a[0] //= 2
    c *= 2
a[0] *= c
for ai in a[1:]:
    if ai % c or (ai // c) % 2 == 0:
        print(0)
        break
else:
    lcm = reduce(lambda x, y: x * y // gcd(x, y), a) // 2
    print(m // lcm - m // (2 * lcm))

Solution (Python):


def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    t = {times_divide_by_two(x) for x in a}
    if len(t) > 1:
        print(0)
        return
    l = lcm(a)
    print((m + l // 2) // l)

def times_divide_by_two(x):
    res = 0
    for i in range(200):
        if x % 2 > 0:
            return res
        res += 1
        x //= 2

def lcm(li):
    res = 1
    for x in li:
        res *= (x // gcd(res, x))
    return res

def gcd(x, y):
    if x < y:
        x, y = y, x  
    while y > 0:
        r = x % y
        x = y
        y = r
    return x

if __name__ == "__main__":
    main()

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


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


def count(x):
    x_ = x
    cnt = 0
    while x_ % 2 == 0:
        x_ = x_//2
        cnt += 1
    return cnt


N, M = map(int, input().split())
*A, = map(int, input().split())
if len(set([count(a) for a in A])) > 1:
    print(0)
else:
    A = [a//2 for a in A]
    while len(A) > 1:
        a = A.pop()
        b = A.pop()
        A.append(lcm(a, b))
    t = A.pop()
    q = M//t
    if q % 2 == 0:
        print(q//2)
    else:
        print((q+1)//2)

Solution (Python):
from functools import reduce
from fractions import gcd
from math import ceil

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

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

def bit(a):
    res = 0
    _a = a
    while _a % 2 == 0:
        _a /= 2
        res += 1
    return res

count = bit(A[0])
for i in range(1, len(A)):
    if bit(A[i]) != count:
        print(0)
        exit()
half_A = [ a // 2 for a in A]

min_X = half_A[0]
for a in half_A:
    min_X = lcm(a, min_X)
    if min_X > M:
        print(0)
        exit()

res = M // min_X

print(int((res+1)//2))

Solution (Python):
from fractions import gcd
n, m = map(int, input().split())
a = [int(i) // 2 for i in input().split()]

def pow2(n):
    cur, res = n, 0
    while cur:
        if cur % 2 == 0:
            cur //= 2
            res += 1
        else:
            return res

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

b = [pow2(i) for i in a]
if (min(b) != max(b)):
    print(0)
    exit(0)
l = 1
for i in range(n):
    l = lcm(l, a[i])
print(m // l - m // (2 * l))

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


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


def get_t(n):
    t = 0
    while n % 2 == 0:
        n //= 2
        t += 1
    return t


def main():
    n, m = map(int, input().split())
    a = [int(i) // 2 for i in input().split()]
    
    t = get_t(a[0])
    l = a[0] // 2**t
    m //= 2**t
    for i in range(1, len(a)):
        count = get_t(a[i])
        if count != t:
            return 0         

        l = lcm(a[i] // 2**t, l)
        if l > m:
            return 0
    
    m //= l
    ans = (m + 1) // 2
    
    return ans       
   

if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
from fractions import gcd
from math import ceil
def f(x):
  cnt=0
  while x%2==0:
    x//=2
    cnt+=1
  return cnt
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=[a[i]//2 for i in range(n)]
g=b[0]
for i in range(1,n):
  g=g*b[i]//gcd(g,b[i])
t=f(a[0])
for i in range(n):
  if t!=f(a[i]):
    print(0)
    exit()
else:
  print(int((m/g+1)//2))

Solution (Python):

def gcd(a,b):
 while b:
  a,b=b,a%b
 return a
def lcm(a,b):
 return a/gcd(a,b)*b
import sys
n,m=map(int,raw_input().split())
a=map(int,raw_input().split())
LCM=1
for i in range(n):
 LCM=lcm(LCM,a[i])
for i in range(n):
 if LCM/a[i]%2==0:
  print 0
  sys.exit()
res=(m/(LCM/2)+1)/2
print res

Solution (Python):
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)
cur = 0
if n != 1:
    t = A[0]
    while t%2 == 0:
        cur += 1
        t = t//2
        flag = True
    for i in range(1,n):
        temp = 0
        s = A[i]
        while s%2 == 0:
            temp += 1
            s = s//2
        if temp != cur:
            flag = False
            break
    if flag:
        g = A[0]*A[1]//(4*gcd(A[0]//2, A[1]//2))
        for i in range(2, n):
            u = g
            v = A[i]//2
            p = u*v//gcd(u,v)
            g = p
        if g <= m:
            print(int((m/g-1)/2)+1)
        else:
            print(0)
    else:
        print(0)
else:
    if A[0] <= 2*m:
        print(int(((2*m/A[0])-1)/2)+1)
    else:
        print(0)

Solution (Python):
import fractions
def LCM(X,Y):
  return X*(Y//fractions.gcd(X,Y))
N,M=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]

def Oddcheck(lst):
  for num in lst:
    if num%2==0:
      return False
      break
  else:
    return True
def Evencheck(lst):
  for num in lst:
    if num%2==1:
      return False
      break
  else:
    return True

c=1
while Oddcheck(ls)==False:
  if Evencheck(ls)==True:
    c*=2
    for i in range(N):
      ls[i]//=2
  else:
    print(0)
    break
else:
  g=1
  for num in ls:
    g=LCM(g,num)
  g*=c//2
  print((M+g)//(2*g))

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def gcd(a,b):
        if a == 0:
            return b
        return gcd(b%a,a)
    n,m = LI()
    a = LI()
    k = [i&-i for i in a]
    if len(set(k)) > 1 or all([i == 1 for i in k]):
        print(0)
        return
    a = [i>>1 for i in a]
    l = a[0]
    for i in a[1:]:
        g = gcd(l,i)
        l *= i//g
    print(m//l-m//(2*l))
    return


if __name__ == "__main__":
    solve()

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

a = [1]*n

a = [int(s) for s in input().split()]

a_half = [s//2 for s in a]


def check(x):
    while (all(c%2 == 0 for c in x)):
        x = [s//2 for s in x]
        if any(c%2 == 1 for c in x) and any(c%2 == 0 for c in x):
            return 0
        
    
    return 1

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


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

if(check(a)== 1):
    x = a_half[0]
    for i in range(1,n):
        y = a_half[i]
        x = lcm(x,y)
    if(x > m):
        print(0)
    else:
        res = int((m//x+1)//2)
        print(res)
else:
    print(0)

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)


def judge(A):
    B = [0] * len(A)
    for i, a in enumerate(A):
        b = 0
        while a % 2 == 0:
            b += 1
            a //= 2
        B[i] = b
    if len(set(B)) == 1:
        return True
    else:
        return False


N, M = map(int, input().split())
A = [int(i) // 2 for i in input().split()]
A = list(set(A))
m = A[0]

if judge(A):
    for a in A[1:]:
        m = lcm(m, a)

    M //= m
    ans = (M + 1) // 2
else:
    ans = 0
print(ans)

Solution (Python):

from fractions import gcd
from functools import reduce
def lcm(x, y):
    return x * y // gcd(x, y)
n, m = map(int, input().split())
a = list(map(int, input().split()))
flg = True
cnt0 = 0
while a[0] % 2 == 0:
    a[0] //= 2
    cnt0 += 1

for i in range(1, n):
    cnti = 0
    while a[i] % 2 == 0:
        a[i] //= 2
        cnti += 1
    
    if cnti != cnt0:
        flg = False
        break
        
lcm_a = reduce(lcm, a) * (2 ** (cnt0 - 1))
x = m // lcm_a
print(-(-x // 2) if flg else 0)

Solution (Python):
import fractions
from functools import reduce

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

div_num = [0 for _ in range(n)]
same = True
for i in range(n):
    tmp = a[i]
    while tmp%2 == 0:
        tmp //= 2
        div_num[i] += 1
if len(set(div_num)) != 1:
    same = False

if same:
    lcm = reduce(lambda x, y: (x*y)//fractions.gcd(x, y), a)
    print(int((m/lcm + 1)//2))
else:
    print(0)

Solution (Python):

from functools import lru_cache
import math


@lru_cache(maxsize=None)
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


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


def lcm_all(lst):
    curr = 1
    for l in lst:
        curr = lcm(curr, l)
    return curr


def divide_count(x):
    ans = 0
    while True:
        q, r = divmod(x, 2)
        if r == 0:
            ans += 1
            x = q
        else:
            break
    return ans



def submit():
    n, m = map(int, input().split())
    alist = list(map(int, input().split()))

    a_divide_count = [divide_count(a) for a in alist]
    for a in a_divide_count[1:]:
        if a != a_divide_count[0]:
            print(0)
            return

    l = lcm_all(alist)
    x = l // 2
    if x > m:
        print(0)
    else:
        print(math.ceil(m // x / 2))


if __name__ == "__main__":
    submit()

Solution (Python):



import fractions
from functools import reduce

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

lcm = 1
for A in a:
    A//=2
    lcm *=A//fractions.gcd(lcm, A)
    if lcm>M:
        print(0)
        exit()
for A in a:
    if lcm/A==int(lcm/A):
        print(0)
        exit()

cnt=M//lcm
print((cnt+1)//2)

Solution (Python):
from fractions import gcd
n, m = map(int, input().split())

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

ans = -1
b = [0] * n
for i in range(n):
    if a[i] % 2 != 0:
        ans = 0
        break

    else:
        b[i] = a[i] // 2


    if i == 0:
        num = format(a[i], 'b')[::-1].find('1')

    else:
        if format(a[i], 'b')[::-1].find('1') != num:
            ans = 0
            break
        else:
            num = format(a[i], 'b')[::-1].find('1')


if ans != 0:
    g = b[0]
    for i in range(1,n):

        g = (g*b[i]) // gcd(b[i],g)

    if g > m: ans = 0
    else:
        ans = (1 + (m-g)//(2*g))

print(ans)

Solution (Python):
from fractions import gcd
n, m = map(int, input().split())

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

ans = -1
b = [0] * n
for i in range(n):
    if a[i] % 2 != 0:
        ans = 0
        break

    else:
        b[i] = a[i] // 2


    if i == 0:
        num = format(a[i], 'b')[::-1].find('1')

    else:
        if format(a[i], 'b')[::-1].find('1') != num:
            ans = 0
            break
        else:
            num = format(a[i], 'b')[::-1].find('1')


if ans != 0:
    g = b[0]
    for i in range(1,n):

        g = (g*b[i]) // gcd(b[i],g)

    if g > m: ans = 0
    else:
        ans = (1 + (m-g)//(2*g))

print(ans)

Solution (Python):
import sys
import fractions

N, M = map(int, input().split())
a = list(map(int, sys.stdin.readline().split()))

a_max = max(a)

smallest_X = 0

lcm_N = a[0]

for i in range(1, N):
    lcm_N = lcm_N * a[i] // fractions.gcd(lcm_N, a[i])


for X in range(int(a_max * 0.5), min(lcm_N + 1, M + 1), a_max):
    flag = True
    for j in range(N):
        if (X - a[j] * 0.5) % a[j] != 0:
            flag = False
            break
    if flag:
        smallest_X = X
        break

if smallest_X == 0:
    print(0)
    
else:
    print(int((M - smallest_X) / lcm_N) + 1)

Solution (Python):
def count_power_of_2(x):
    cnt = 0
    while x % 2 == 0:
        x //= 2
        cnt += 1
    return cnt


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)


def main():
    N, M = map(int, input().split())
    a = map(int, input().split())
    *a, = map(lambda x: x >> 1, a)

    power = count_power_of_2(a[0])

    if any(count_power_of_2(x) != power for x in a):
        print(0)
        return

    common = 1 << power

    base = common
    for x in a:
        x //= common
        base = lcm(base, x)

    ret = (M // base) - (M // (base * 2))
    print(ret)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
import sys

def gcd(p, q):
    if p < q:
        p, q = q, p
    while q > 0:
        p, q = q, p%q
    return p

n, m = map(int, input().split())
a = np.array([int(x) for x in input().split()])

k = a[0]
for i in range(1, n):
    k = k*a[i]//gcd(k, a[i])

b = a//2
while True:
    p = b%2
    if all(p):
        break
    elif any(p):
        print(0)
        sys.exit()
    else:
        b //= 2
        continue

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

Solution (Python):

import math
import copy

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


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


n, m = map(int,input().split())
a = [int(i) for i in input().split()] 
b = copy.deepcopy(a)

count = [0 for _ in range(n)]
for i in range(n):
    while b[i] % 2 == 0:
        b[i] //= 2
        count[i] += 1

if len(set(count)) != 1:
    print(0)
    exit()

l = 1
for i in range(n):
    l = lcm(l, a[i])

ans = math.ceil((2 * m // l) / 2) 
print(ans)

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7


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

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

n, m = MAP()
a = LIST()
a0 = a[0]
aa = 0
while a0 % 2 == 0:
    a0 //= 2
    aa += 1
for i in range(1, n):
    ai = a[i]
    for _ in range(aa):
        if ai % 2 == 1:
            print(0)
            exit()
        ai //= 2
    if ai % 2 == 0:
        print(0)
        exit()

l = 1
for i in range(n):
    l = lcm(l, a[i])
ans = 2 * m // l
ans = ans // 2 + ans % 2
print(ans)

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7


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

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

n, m = MAP()
a = LIST()
a0 = a[0]
aa = 0
while a0 % 2 == 0:
    a0 //= 2
    aa += 1
for i in range(1, n):
    ai = a[i]
    for _ in range(aa):
        if ai % 2 == 1:
            print(0)
            exit()
        ai //= 2
    if ai % 2 == 0:
        print(0)
        exit()

b = [i // 2 for i in a]
l = 1
for i in range(n):
    l = lcm(l, b[i])
ans = m // l
ans = (ans + 1) // 2
print(ans)

Solution (Python):
'''
https://atcoder.jp/contests/abc150/tasks/abc150_d
'''
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate
    
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    

    
    

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

    if len(a) == 1:
        if m >= a[0]//2:
            print((m-a[0]//2) // a[0] + 1)
        else:
            print(0)
        exit()

    def gcd(a, b):
        if b == 0:
            return a
        else:
            return gcd(b, a % b)
    
    def gcd_group(arr):
        g = gcd(arr[0], arr[1])
        for i in range(2, len(arr)):
            g = gcd(g, arr[i])
        return g
    
    def lcm(a, b):
        g = gcd(a, b)
        return (a*b)//g
    
    def lcm_group(arr):
        l = lcm(arr[0], arr[1])
        for i in range(2, len(arr)):
            l = lcm(l, arr[i])
        return l
    g = gcd_group(a)
    for i in a:
        if (i//g)%2 == 0:
            print(0)
            exit()
    lcm = lcm_group(a)
    semi_lcm = lcm // 2
    if m >= semi_lcm:
        print((m-semi_lcm)//lcm + 1)
    else:
        print(0)


if __name__ == '__main__':
    main()

Solution (Python):
from fractions import gcd
 
N,M = map(int,input().split())
a = list(map(int,input().split()))
 
if len(set([i&-i for i in a])) != 1:
  print(0)
else:
  x = 1
  for i in range(N):
    x = x*(a[i]//2//gcd(x,a[i]//2))
 
  print(M//x-M//(2*x))

Solution (Python):
import sys
import math
import fractions

N, M = map(int, input().split())
a = list(map(lambda x: int(x) >> 1, input().split()))
set(a)

fdigit = 0
while True:
	c = 1 << fdigit
	if a[0] & c != 0:
		break
	fdigit += 1

alcm = 1
for i in range(N):
	digit = 0
	while True:
		c = 1 << digit
		if a[i] & c != 0:
			break
		digit += 1
	if digit != fdigit:
		print(0)
		sys.exit(0)

	alcm = (alcm * a[i]) // fractions.gcd(alcm, a[i])

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

Solution (Python):
import sys,queue,math,copy
from fractions import gcd
input = sys.stdin.readline
LI = lambda : [int(x) for x in input().split()]
LI_2 = lambda : [int(x) / 2 for x in input().split()]

N,M = LI()
A = LI_2()

lcm = 1
for a in A:
    c = gcd(lcm,a)
    if (lcm//c) % 2 == 0:
        print (0)
        exit (0)
    lcm *= (a//c)

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

Solution (Python):
from fractions import gcd

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

if len(set([i&-i for i in a])) != 1:
  print(0)
else:
  x = a[0]//2
  for i in range(1, len(a)):
      x = x*(a[i]//2//gcd(x,a[i]//2))

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

Solution (Python):


import fractions

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

have2=[0]*len(A)

for index,item in enumerate(A):
    while item%2==0:
        item/=2
        have2[index]+=1

if len(list(set(have2)))!=1:
    print(0)
    exit()

f=0
f2=1
for item in A:
    f=fractions.gcd(f2,item)
    f2=f2*item//f
if M>=f2//2:
    M-=f2//2
    print(max(M//f2+1,0))
else:
    print(0)

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

n,m = mi() 
alis = li()
for i in range(n):
    alis[i] //= 2

ima = alis[0] & -alis[0]
alis[0] //= ima
for i in range(1,n):
    tmp = alis[i] & -alis[i]
    if ima != tmp:
        print(0)
        exit()
    else:
        alis[i] //=ima

tmp = ima

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

def lcm(a,b):
    return a*b // gcd(a,b)
ima = 1
for i in range(n):
    ima = lcm(alis[i],ima)
    if ima*tmp > m:
        print(0)
        exit()
ans = 0

tmm = m//(ima*tmp)
if tmm % 2 ==0:
    print(tmm//2)
else:
    print(tmm//2 +1)

Solution (Python):
from functools import reduce

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

def lcm_list(list):
    return reduce(lcm_base, list)

N, M = map(int, input().split())
a = list(map(int, input().split()))
b = [x//2 for x in a]
T = lcm_list(b)
for n in b:
    if T//n%2 == 0:
        print (0)
        break
else:
    print ((M//T+1)//2)

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

from functools import reduce
import fractions
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)
def lcm(numbers):
    return reduce(lcm_base, numbers, 1)

def get2(num):
    cnt=0
    while num %2==0:
        cnt+=1
        num//=2
    return cnt

div2=get2(a[0])
for i in range(len(a)):
    if div2 != get2(a[i]):
        print(0)
        exit()

num = lcm(a)
thr = m - num//2

if thr < 0:
    print(0)
else:
    print(thr//num + 1)