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: Accepted

Solution code:
n, m = map(int, input().split())
a = [int(c) // 2 for c in input().split()]

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

t = f(a[0])
for ai in a:
    if f(ai) != t:
        print(0)
        exit()

m //= 2 ** t
a = [ai // 2 ** t for ai in a]

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

lcm = 1
for ai in a:
    d = gcd(lcm, ai)
    lcm = lcm * ai // d
    if lcm > m:
        print(0)
        exit()

print((m // lcm + 1) // 2)

Submission status: Accepted

Solution code:
import fractions
N,M = list(map(int,input().split()))
a = list(map(int,input().split()))

def func(a):
	if a%2 == 0:
		return func(a//2)+1
	else:
		return 0



n = 0
for i in range(1,N):
	if func(a[i]) != func(a[i-1]):
		print(0)
		exit()

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

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

m = M//semi_lcm
if m == 0:
	print(0)
else:
	if m%2 == 1:
		print((m+1)//2)
	else:
		print(m//2)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
from fractions import gcd
from functools import reduce
x=reduce(lambda x,y:x*y//gcd(x,y),A)
print(0 if any([x//a%2==0 for a in A]) else (M+x//2)//x)

Submission status: Accepted

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

import fractions
from functools import reduce

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

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

l=lcm_list(a)

for s,t in enumerate(a):
    if (l//t)%2==0:
      print("0")
      exit()

print((2*M//l+1)//2)

Submission status: Accepted

Solution code:
def culuc(a):
    cnt = 0
    while a%2==0:
        a//=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)
n,m = map(int,input().split())
a = list(map(int,input().split()))
cnt = culuc(a[0])
for i in a:
    if culuc(i)!=cnt:
        print(0)
        exit()
res = a[0]//2
for i in a:
    res = lcm(res,i//2)
    if res>m:
        print(0)
        exit()
print((m//res+1)//2)

Submission status: Accepted

Solution code:
import sys
inputs = sys.stdin.readlines()
from fractions import gcd
from operator import mul
from functools import reduce
lcm = lambda x, y: x*y // gcd(x, y)

n, m = map(int, inputs[0].split())
A = list(map(int, inputs[1].split()))
g = reduce(gcd, A)
if all((a // g) % 2 for a in A):
    print(round((m+1) / reduce(lcm, A)))
else:
    print(0)

Submission status: Accepted

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

def mygcd(a, b):
    if a < b:
        return mygcd(b, a)
    elif b == 0:
        return a
    else:
        return mygcd(b, a % b)

lcm = 1
for i, ai in enumerate(a):
    gcd = mygcd(lcm, ai)
    lcm = (lcm * ai) // gcd

possible = False
for i, ai in enumerate(a):
    if (lcm // ai) % 2 == 0: break
    else: continue
else:
    possible = True

if possible:
    print((((2 * M) // lcm) + 1) // 2)
else:
    print(0)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce
import copy
import sys

N, M, *a_n = map(int, open(0).read().split())
a_n = list(set(a_n))
a_n = [a // 2 for a in a_n]
N = len(a_n)

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

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

a_n_half = [0] * N
a_n_copy = copy.copy(a_n)
for i in range(N):
    while a_n_copy[i] % 2 == 0:
        a_n_copy[i] //= 2
        a_n_half[i] += 1
        
for i in range(N-1):
    if a_n_half[i] != a_n_half[i+1]:
        print(0)
        sys.exit()
        
print(-(-(M // lcm_list(a_n)) // 2))

Submission status: Accepted

Solution code:
def gcd(n,m):#n,mは正の整数、最大公約数　許容は？
    if n==0:
        return m
    elif m==0:
        return n
    elif n>m:
        n=n%m
        return gcd(n,m)
    else:
        m=m%n
        return gcd(n,m)

N,M=map(int,input().split())
A=list(map(int,input().split()))
realA=[A[i]//2 for i in range(0,N)]
lcm=realA[0]
flag=0
if N==1:
    print((M//lcm+1)//2)
else:
    for i in range(0,N-1):
        x=lcm
        lcm=lcm*realA[i+1]//(gcd(lcm,realA[i+1]))
        if (lcm**2//(realA[i+1]*x))%2==0:
            flag=1
            break
    if flag==0:
        print((M//lcm+1)//2)
    else:
        print(0)

Submission status: Accepted

Solution code:
import sys
import math
import fractions
import bisect
import queue
import heapq
from collections import deque
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint
N, K = map(int, input().split())

1行のstring
S, T = input().split()

1行の整数配列
P = list(map(int,input().split()))

改行あり
x = []
y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)

N行M列の初期化
dp = [[INF] * M for i in range(N)]

'''

"""""""""""""""""""""""""""""""""
 最大公約数 O()
"""""""""""""""""""""""""""""""""
# fractions.gcd(a,b)
def gcd(a, b):
    return fractions.gcd(a, b)

"""""""""""""""""""""""""""""""""
 最小公倍数 O()
"""""""""""""""""""""""""""""""""
def lcm(a,b):
    return (a*b) // fractions.gcd(a,b)


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


twice = 1
while True:
    if A[0] % (twice*2) == 0:
        twice*=2
    else:
        break

for a in A:
    if a%twice != 0:
        print(0)
        sys.exit()
    elif a%(twice*2) == 0:
        print(0)
        sys.exit()

               

koubais = [] # 隣り合った２つの最小公倍数のリスト
for i in range(0, N, 2):
    if i == N-1:
        koubais.append(A[i]//2)
        break

    A[i] //= 2
    A[i+1] //= 2
    koubais.append(lcm(A[i+1], A[i]))

half = 1
for i in range(len(koubais)):
    half = lcm(half, koubais[i])

ans = (M//half + 1) // 2
print(int(ans))

Submission status: Accepted

Solution code:
import sys
import math
import fractions
import bisect
import queue
import heapq
from collections import deque
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint
N, K = map(int, input().split())

1行のstring
S, T = input().split()

1行の整数配列
P = list(map(int,input().split()))

改行あり
x = []
y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)

N行M列の初期化
dp = [[INF] * M for i in range(N)]

'''

"""""""""""""""""""""""""""""""""
 最大公約数 O()
"""""""""""""""""""""""""""""""""
# fractions.gcd(a,b)
def gcd(a, b):
    return fractions.gcd(a, b)

"""""""""""""""""""""""""""""""""
 最小公倍数 O()
"""""""""""""""""""""""""""""""""
def lcm(a,b):
    return (a*b) // fractions.gcd(a,b)


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


twice = 1
while True:
    if A[0] % (twice*2) == 0:
        twice*=2
    else:
        break

for a in A:
    if a%twice != 0:
        print(0)
        sys.exit()
    elif a%(twice*2) == 0:
        print(0)
        sys.exit()


half = 1
for a in A:
    half = lcm(half, a//2)

ans = (M//half + 1) // 2
print(int(ans))

Submission status: Accepted

Solution code:
import sys
import math
import fractions
import bisect
import queue
import heapq
from collections import deque
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint
N, K = map(int, input().split())

1行のstring
S, T = input().split()

1行の整数配列
P = list(map(int,input().split()))

改行あり
x = []
y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)

N行M列の初期化
dp = [[INF] * M for i in range(N)]

'''

"""""""""""""""""""""""""""""""""
 最大公約数 O()
"""""""""""""""""""""""""""""""""
# fractions.gcd(a,b)
def gcd(a, b):
    return fractions.gcd(a, b)

"""""""""""""""""""""""""""""""""
 最小公倍数 O()
"""""""""""""""""""""""""""""""""
def lcm(a,b):
    return (a*b) // fractions.gcd(a,b)


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


twice = 1
while True:
    if A[0] % (twice*2) == 0:
        twice*=2
    else:
        break

for a in A:
    if a%twice != 0:
        print(0)
        sys.exit()
    elif a%(twice*2) == 0:
        print(0)
        sys.exit()


half = 1 # 最小公倍数の二分の一
for i in range(N):
    A[i] //= 2
    half = lcm(half, A[i])

ans = (M//half) // 2 + int((M//half)%2 == 1)
print(int(ans))





"""
ATTENTION: Pythonで間に合うか？？

            <目安>
 文字列結合、再帰関数を含む→Python
 上を含まず時間が不安→PyPy3

"""

Submission status: Accepted

Solution code:
import fractions
n, m = map(int, input().split())
a = [i//2 for i in list(map(int, input().split()))]
tmp = a[0]
count = 0
while tmp % 2 == 0:
    tmp /= 2
    count += 1
for i in range(n):
    tmp = a[i]
    div = 0
    while tmp % 2 == 0:
        tmp /= 2
        div += 1
    if div != count:
        print(0)
        exit()
ans = 0
k = a[0]
for i in range(n):
    k = (k * a[i]) // (fractions.gcd(k, a[i]))
ans = m // k
ans = (ans + 1) // 2
print(ans)

Submission status: Accepted

Solution code:
import fractions

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

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

def lcm(X):
    ret = X[0]
    for i in range(1,len(X)):
        ret = ret * X[i] //fractions.gcd(ret,X[i])
        if ret > M:
            ret = M+1
            break
    return ret




count = 0
a = A[0]
while a % 2 == 0:
    a //= 2
    count += 1

det = 0
for i in range(1,N):
    x = A[i] / (2**count)
    if x % 2 == 0 or int(x) != x:
        det = -1
        break
#print(det)
if det == -1:
    print(0)
else:
    for i in range(N):
        A[i] //= 2**count
    min_l = lcm(A) * (2**(count-1))
    #print(min_l)
    t = M // min_l
    if t % 2 == 0:
        print(t//2)
    else:
        print((t+1)//2)

Submission status: Accepted

Solution code:
#D
from fractions import gcd

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

ans = 0
#if some element in a is odd, it cannot be divided by 2
for v in a:
    if v%2 != 0:
        break
else:
    a = [i//2 for i in a]
    
    #check whether each element has the same power of 2
    elem = 0
    v = a[0]
    while(v%2==0):
        v //= 2
        elem += 1
    for v in a[1:]:
        now=0
        while(v%2==0):
            v //= 2
            now += 1
        if(elem != now):
            ans = 0
            break
    else:
        #calculate its lcm by using gcd
        lcm = 1
        for v in a:
            lcm = (lcm * v)//gcd(lcm, v)
        
        q = m //lcm
        ans = (q+1)//2

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
Y = reduce(lambda a, b: a * b // gcd(a, b), A)
print(M // (Y // 2) - (M // Y) if all((Y // a) % 2 for a in A) else 0)

Submission status: Accepted

Solution code:
import fractions
import sys
n, m = map(int, input().split())
a = list(map(int, input().split()))
lcm = a[0]
for i in range(1, len(a)):
    lcm = lcm*a[i]//fractions.gcd(lcm,a[i])
for i in a:
    if(lcm//i)%2 == 0:
        print(0)
        sys.exit()
lcm //= 2
print(m//lcm-(m//(lcm*2)))

Submission status: Accepted

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

Submission status: Accepted

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

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

def exp2(k):
    p = 0
    while k % 2 == 0:
        k //= 2
        p += 1
    return p

N, M = map(int, input().split())
A = [int(a)//2 for a in input().split()]
l = 1
flg = 0
already = set()
for a in A:
    already.add(exp2(a))
    if len(already) > 1:
        flg = 1
        break
    l = lcm(l, a)
if flg == 1:
    ans = 0
else:
    ans = (M // l + 1)//2
print(ans)

Submission status: Accepted

Solution code:
def count(x):
    count = 0
    while x % 2 == 0:
        x //= 2
        count += 1
    return count


def lcm(l):
    from fractions import gcd
    x = l[0]
    for i in range(1, len(l)):
        x = (x * l[i]) // gcd(x, l[i])
    return x


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

if len(set(map(count, A))) == 1:
    T = lcm(list(map(lambda x: x // 2, A)))
    ans = -(-(M // T) // 2)

print(ans)

Submission status: Accepted

Solution code:
import itertools
import functools

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

A = list(map(lambda x: x // 2, A))

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

    return a

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

def ok(A):
    def f(x, y):
        return x % 2 == y % 2
    return functools.reduce(f, A, A[0])

pow2 = functools.reduce(gcd, A, A[0])
while pow2 % 2 == 0:
    A = list(map(lambda x: x // 2, A))
    pow2 //= 2
    M //= 2

x = functools.reduce(lcm, A, 1)

if x % 2  == 0:
    print(0)
else:
    print(M // x - M // (2 * x))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
list_a = [int(x) for x in input().split()]

import fractions

def insu2(a) :
    insu = 0
    while a%2 == 0 :
        insu += 1
        a /= 2
    return insu

check = True

for i in list_a :
    if insu2(i) != insu2(list_a[0]) :
        print(0)
        exit()

ans_0 = list_a[0]
for i in range(1,N) :
    ans_0 = ans_0 * list_a[i] // fractions.gcd(ans_0, list_a[i])

ans_0 //= 2
ans = M//ans_0 - M//(ans_0*2)

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
N, M = map(int, input().split())
A = list(map(int, input().split()))
lcm = 1

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

t = f(A[0])
for a in A:
  if t != f(a):
    print(0)
    exit()
  a //= 2
  lcm *= a // gcd(lcm, a)

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

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
A = [ int(a) // 2 for a in input().split()]
from math import ceil
from fractions import gcd
def main():
    x = 1
    check = set()
    for a in A:
        tmp = 0
        if a%2 == 0:
            tmpa = a
            while tmpa%2 ==0 :
                tmpa //= 2
                tmp += 1
        check.add(tmp)
        if len(check) > 1:
            print(0)
            return
        if x%a != 0:
            x *= a // gcd(a,x)
    print(ceil((M // x)/2))
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
import math
from fractions import gcd
n,m = map(int,input().split())
a = np.array(input().split(),dtype=int)
a /= 2

def t_per2(k):
    return format(k,'b')[::-1].find('1')

f = False
dcm = a[0]
t_2 = t_per2(a[0])
for i in a:
    dcm = (dcm*i)//gcd(dcm,i)
    if dcm > m or not t_per2(i) == t_2:
        f = True
        break

count = 0
if not f:
    count = math.ceil(int(m/dcm)/2)

print(count)

Submission status: Accepted

Solution code:
from fractions import gcd

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

a=list(map(lambda x: x//2, a))

def lcm(q):
  x = q[0]
  for i in range(1, len(q)):
    x = (x * q[i]) // gcd(x, q[i])
  return x

lcma=lcm(a)

if (lcma//a[0])%2==0:
  print(0)
else:
  flg=0
  for i in range(1,len(a)):
    if (lcma//a[i])%2==0:
      print(0)
      flg=1
      break
  if flg==0:
    temp=m//lcma
    print(temp//2 if temp%2==0 else temp//2+1)

Submission status: Accepted

Solution code:
def count(k):
    ret=0
    while k%2==0:
        k//=2
        ret+=1
    return ret
def gcd(x,y):
    if x<y:
        x,y=y,x
    if y==0:
        return x
    return gcd(y,x%y)
def lcm(x,y):
    return x*y//gcd(x,y)

def main():
    n,m=map(int,input().split())
    A=tuple(map(int,input().split()))
    cnt=count(A[0])
    for a in A:
        if cnt!=count(a):
            return 0
    l=A[0]//2
    for a in A:
        l=lcm(l,a//2)
    if m<l:
        return 0
    return (m-l)//(l*2)+1
    
if __name__=='__main__':
    print(main())

Submission status: Accepted

Solution code:
import math
import fractions
from functools import reduce

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

t = 0
while all([i%(2**(t+1))==0 for i in a]):t+=1
a = [i//(2**t) for i in a]

if any([i%2==0 for i in a]):
  print(0)
else:
  b = reduce(lambda x,y:x*(y//fractions.gcd(x,y)),a) * (2**t)
  print((m//b+1)//2)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

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

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


def main():
  n, m = map(int, input().strip().split())
  As = list(map(int, input().strip().split()))
  x = 1
  for i in range(len(As)):
    x = lcm(x, As[i])
    if m/x < 0.5:
      print(0)
      return
  if sum([(x//A)%2 == 1 for A in As]) == len(As):
    print(int(m/x-0.5+1))
  else:
    print(0)

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
from fractions import gcd
from functools import reduce

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

N, M = lr()
A = np.array(lr())
B = A // 2
# Bの要素が全て2の同じ冪乗
# Bの最小公倍数を求める
def merge(a, b):
    g = gcd(a, b)
    a, b = a // g, b // g
    if a%2 == 0 or b%2 == 0:
        return 0
    ret = a * b * g
    if ret > 10 ** 9:
        return 0
    return ret

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

print(answer)
# 56

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import math
from functools import reduce
import operator
INF = float("inf")


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


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


def solve(N: int, M: int, a: "List[int]"):

    # 各aを2で割れる回数(の２べき)
    K = set()
    for i, av in enumerate(a):
        K.add(av & -av)
    if len(K) != 1:
        print(0)
        return

    lcm = a[0]//2
    for av in a:
        lcm = LCM(lcm, av//2)

    ans = int(M/lcm)
    if ans > 0 and ans % 2 == 0:
        ans -= 1
    ans = (ans+1)//2

    print(ans)
    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))  # type: int
    M = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, a)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


MOD = 998244353
INF = int(1e15)


def main():
    # sys.stdin = open("sample.txt")
    N, M = Scanner.map_int()
    A = Scanner.map_int()
    L = 1
    for i in range(N):
        L = Math.lcm(L, A[i] // 2)
    for a in A:
        if L % a != a // 2:
            print(0)
            return
    print(Math.roundUp(M // L, 2))
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import fractions
from functools import reduce


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

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


def main():
    N,M=[int(x) for x in input().split()]
    a = [int(x) for x in input().split()]
    b = [x//2 for x in a]

    # l = np.lcm.reduce(b)
    l = lcm(b)
    for x in b:
        if l // x % 2 == 0:
            print(0)
            return

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
import fractions
n, m = map(int, input().split())
a = list(map(int, input().split()))
num = 1
cnt = []
for x in a:
    c = 0
    for i in range(int(math.log(x,2))):
        if x>>c&1:
            break
        else:
            c+=1
    cnt.append(c)
if max(cnt) != min(cnt):
    print(0)
else:
    for x in a:
        num = num * (x//2) // fractions.gcd(num, x//2)
    print(m//num-(m//num)//2)

Submission status: Accepted

Solution code:
from fractions import gcd

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

a = A[0]
n = 1
while a % 2 == 0:
    n *= 2
    a //= 2

lcm = 1
for a in A:
    if a % n != 0 or a % (2 * n) == 0:
        print(0)
        exit()
    lcm = lcm * a // gcd(lcm, a)
    if lcm // 2 > M:
        print(0)
        exit()

print((M - lcm // 2) // lcm + 1)

Submission status: Accepted

Solution code:
def main():
    from fractions import gcd

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

    a = A[0]
    n = 1
    while a & 1 == 0:
        n <<= 1
        a >>= 1

    lcm = 1
    for a in A:
        if a % n != 0 or a % (2 * n) == 0:
            print(0)
            return
        lcm = lcm * a // gcd(lcm, a)
        if lcm > M * 2:
            print(0)
            return

    print((M - lcm // 2) // lcm + 1)


main()

Submission status: Accepted

Solution code:
from sys import exit
from fractions import gcd

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

a = A[0]
n = 1
while a % 2 == 0:
    n *= 2
    a //= 2

lcm = 1
for a in A:
    if a % n != 0 or a % (2 * n) == 0:
        print(0)
        exit()
    lcm = lcm * a // gcd(lcm, a)
    if lcm // 2 > M:
        print(0)
        exit()

print((M - lcm // 2) // lcm + 1)

Submission status: Accepted

Solution code:
def main():
    from fractions import gcd

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

    t = A[0]
    n = 1
    while t % 2 == 0:
        n *= 2
        t //= 2

    for a in A:
        if a % n != 0 or (a // n) % 2 == 0:
            print(0)
            return

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

    print((M - lcm // 2) // lcm + 1)


main()

Submission status: Accepted

Solution code:
import fractions
from functools import reduce


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


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

N, M = map(int, input().split())
a = list(map(int, input().split()))
aa = list(map(lambda x: x // 2, a))

lcm = lcm_list(aa)

for b in a:
    if (lcm - (b // 2)) % b != 0:
        print(0)
        exit(0)

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

Submission status: Accepted

Solution code:
def solve():
    from sys import stdin
    f_i = stdin
    
    N, M = map(int, f_i.readline().split())
    A = tuple(map(int, f_i.readline().split()))
    
    from fractions import gcd
    def lcm(a, b):
        return a * b // gcd(a, b)
    
    import functools
    def mul_lcm(nums):
        return functools.reduce(lcm, nums)
    
    half_A = tuple((a // 2 for a in A))
    l = mul_lcm(half_A)
    
    for a in half_A:
        if (l // a) % 2 == 0:
            return 0
    
    return (M // l + 1) // 2

print(solve())

Submission status: Accepted

Solution code:
def solve():
    from sys import stdin
    f_i = stdin
    
    N, M = map(int, f_i.readline().split())
    A = tuple(map(int, f_i.readline().split()))
    """
    def fact2(num):
        cnt = 0
        while num % 2 == 0:
            num //= 2
            cnt += 1
    
    f = fact2(A[0])
    for a in A[1:]:
        if f != fact2(a):
            return 0
    """
    from fractions import gcd
    def lcm(a, b):
        return a * b // gcd(a, b)
    
    import functools
    def mul_lcm(nums):
        return functools.reduce(lcm, nums)
    
    half_A = tuple((a // 2 for a in A))
    l = mul_lcm(half_A)
    
    for a in half_A:
        if (l // a) % 2 == 0:
            return 0
    
    return (M // l + 1) // 2

print(solve())

Submission status: Accepted

Solution code:
from functools import reduce
def f(n):
    res = 0
    while(n%2 == 0):
        res += 1
        n //= 2
    return res

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

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

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

l = reduce(lcm, A, 1)
for a in A:
    if((l // a) % 2 == 0):
        print(0)
        break

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

Submission status: Accepted

Solution code:
import math

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

def gcd(m, n):
    r = m % n
    return n if r == 0 else gcd(n, r)

def lcm(m, n):
    return m * n // gcd(m, n)


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

F = set()
for a in A:
    F.add(f(a))
if len(F) != 1:
    print(0)
    exit()

LCM = [a // 2 for a in A]
for i in range(1, n):
    LCM[i] = lcm(LCM[i - 1], LCM[i])

answer = math.ceil(m // LCM[-1] / 2)
print(answer)

Submission status: Accepted

Solution code:
import fractions
from functools import reduce

N,M = map(int,input().split())
A = list(set((map(lambda x : int(x) // 2,input().split()))))

def lcm(a,b):
  return (a * b) // fractions.gcd(a, b)
def gcd_list(numbers):
  return reduce(fractions.gcd, numbers)
def lcm_list(numbers):
  return reduce(lcm, numbers, 1)

LCM = lcm_list(A)
ans = (M // LCM + 1) // 2

for a in A[1:]:
  if (LCM // a) % 2 == 0:
    ans = 0
    break
    
print(ans)

Submission status: Accepted

Solution code:
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)

n,m=map(int,input().split())
arr=list(map(int,input().split()))
if n==1:
  l=arr[0]
else:
  l=lcm(arr[0],arr[1])
for i in range(2,n):
  l=lcm(l,arr[i])
  if l//2>m:
    print(0)
    exit()
for i in range(n):
  if (l//arr[i])%2==0:
    print(0)
    exit()
ans=(m-l//2)//l+1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = list(set(map(lambda x : int(x)//2, input().split())))
def gcd(x, y):
  return x if y == 0 else gcd(y, x % y)
def lcm(x, y):
  return (x * y) // gcd(x, y)
l = A[0]
for a in A[1:]:
  l = lcm(l, a)
ans = (M // l + 1) // 2
for a in A[1:]:
  if (l // a) % 2 == 0:
    ans = 0
    break
print(ans)

Submission status: Accepted

Solution code:
def eveCheck(a):
    k = 0
    while a%2==0:
        a = a//2
        k += 1
    return k
def gcd(x,y):
    while y>0:
        x,y = y,x%y
    return x
N,M = map(int,input().split())
A = list(map(int,input().split()))
k = eveCheck(A[0])
flag = 0
for i in range(1,N):
    if k!=eveCheck(A[i]):
        flag = 1
        break
if flag==1:
    print(0)
else:
    m = A[0]
    for i in range(1,N):
        m = m*(A[i]//gcd(m,A[i]))
    a = m//2
    print((M-a)//m+1)

Submission status: Accepted

Solution code:
from fractions import gcd


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


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

# a1が2で何回割れるか
ii = 0
while A[0] % 2 == 0:
  ii += 1
  A[0] //= 2


# 全ての要素について、素因数2の数が等しくなければ不適
for i, a in enumerate(A[1:], 1):
  if a % (2**ii) == 0 and a % (2**(ii+1)) != 0:
    A[i] //= 2**ii
  else:
    print(0)
    quit()


# (ak//2) (k=1, 2, ...)の最小公倍数を求める
l = 2**(ii-1)
for b in A:
  l = lcm(l, b)

# xは最小公倍数の奇数倍
print(-(-(M//l) // 2))