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:
import functools
import fractions

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

# xが2で何回割れるか
def div2count(x):
    count=0
    while x%2==0:
        x=x//2
        count+=1
    return count

N,M=map(int,input().split())
A=list(map(int,input().split()))
if len(set(map(div2count,A)))!=1:
    print(0)
    exit()
LCM=functools.reduce(lcm,A)
HLCM=LCM//2
Y=M//HLCM
if Y%2==0:
    print(Y//2)
else:
    print((Y+1)//2)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
from fractions import gcd
for i in range(n):
	a[i]//=2
from copy import copy
b=copy(a)
c=[]

for i in range(n):
	cnt=0
	while b[i]%2==0:
		cnt+=1
		b[i]//=2
	c.append(cnt)
for i in range(n-1):
	if c[i]!=c[i+1]:
		print(0)
		exit()

a_gcd=a[0]
for i in range(1,n):
	a_gcd=a_gcd*a[i]//gcd(a_gcd,a[i])
print((m+a_gcd)//(a_gcd*2))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
l = list(map(int, 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)

k = 1

for i in l:
    i //= 2
    k = lcm(k, i)
    if (k // i) % 2 == 0 or k > m:
        print(0)
        break
else:
    print(m // k - m // (k * 2))

Submission status: Accepted

Solution code:
def p_d():
    from fractions import gcd
    n, m = map(int, input().split())
    *A, = map(lambda x: int(x) // 2, input().split())

    c = 0
    for a in A:
        if c == 0:
            while a & 1 == 0:
                c += 1
                a >>= 1
        else:
            ne = 0
            while a & 1 == 0:
                ne += 1
                a >>= 1
            if c != ne:
                print(0)
                exit()

    lcm = A[0]
    for i in range(1, n):
        lcm = lcm * A[i] // gcd(lcm, A[i])
    print((m // lcm + 1) // 2)
    
p_d()

Submission status: Accepted

Solution code:
import fractions
import functools

N, M = [int(i) for i in input().split()]
a = {int(i) // 2 for i in input().split()}  # 予め2で割っておく


def lcm(a, b):
    """a, bの最小公倍数を求める"""
    return a * b // fractions.gcd(a, b)


# aの中で一番小さい数が2で何回割れるか
n_2 = 0
min_a = min(a)
while True:
    if min_a % 2 != 0:
        break
    min_a //= 2
    n_2 += 1

# aのすべての数が2でn_2回割り切れる
cond1 = all({i % (2**n_2) == 0 for i in a})
# n_2回割った後、さらに2で割り切れる数は存在しない
cond2 = all({(i // (2**n_2)) % 2 != 0 for i in a})

if cond1 and cond2:
    all_lcm = functools.reduce(lcm, a)  # aの全要素の最小公倍数
    ans = -((-(M // all_lcm)) // 2)
    print(ans)
else:
    print(0)

Submission status: Accepted

Solution code:
from fractions import gcd
#X=b_k*(2p+1)
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))

Submission status: Accepted

Solution code:
# ABC150 D
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
from fractions import gcd
from math import ceil
def lcm(x, y):
    return (x * y) // gcd(x, y)
n,m=nm()
a=nl()
ans=0
a=[x//2 for x in a] 

lcm_v=a[0]
for i in range(n):
    lcm_v=lcm(lcm_v,a[i])
ok_flg=[(lcm_v//i)%2==1 for i in a]
if all(ok_flg):
    ans=((m//lcm_v)+1)//2
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
l = list(map(int,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)

k = 1
tf = True

for i in l:
    i //= 2
    k = lcm(k, i)
    if (k // i) % 2 == 0 or k > m:
        print(0)
        tf = False
        break

if tf == True:
    print(m // k - m // (k * 2))

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
l = list(map(int,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)

ans = 1
tf = True

for i in l:
    i //= 2
    ans = lcm(ans, i)
    if (ans // i) % 2 == 0 or ans > m:
        print(0)
        tf = False
        break

if tf == True:
    print(m // ans - m // (ans * 2))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
from fractions import gcd
from functools import reduce

n, m, *alst = list(map(int, read().split()))
mm = 2 * m


def lcm(x, y):
    g = gcd(x, y)
    if x // g % 2 == 0 or y // g % 2 == 0:
        print(0)
        quit()
    g = x * y // g
    if g > mm:
        print(0)
        quit()
    return g


g = reduce(lcm, alst)
res = (mm // g)
print(res // 2 + res % 2)

Submission status: Accepted

Solution code:
import fractions
import math
 
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
 
 
n, m = list(map(int, input().split()))
a = list(map(lambda x: int(x) // 2, input().split()))
lcm_all = 1
for e in a:
    lcm_all = lcm(lcm_all, e)
    if (lcm_all // e) % 2 == 0:
        print(0)
        exit()
print(math.ceil((m // lcm_all) / 2))

Submission status: Accepted

Solution code:
import fractions
from functools import reduce

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

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

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

a_2 = list(a[i] // 2 for i in range(n))
t = lcm_list(a_2)

if not all([(t // i) % 2 for i in a_2]):
    print(0)
    quit()

p = (m - t) // (2 * t) + 1
print(p)

Submission status: Accepted

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

from fractions import gcd

l = As[0]
for a in As:
    l = l * a // gcd(l, a)
    if l > M:
        break

if l <= M:
    i = 2
    while l & (i - 1) == 0:
        i <<= 1
    i = (i >> 1) - 1

    fg = False
    if i > 0:
        for a in As:
            if a & i > 0:
                fg = True
                break

    if fg:
        print(0)
    else:
        print(M // l - M // (l * 2))
else:
    print(0)

Submission status: Accepted

Solution code:
import fractions,sys

n,m=map(int,input().split())
a = list(map(int, input().split()))
# ans = a[0]
# for i in range(1,n):
#     ans = ans * a[i] // fractions.gcd(ans, a[i])
ff=[]
for j in  a:
    count=0
    for i in range(1,36):
        if j%(2**i)==0:
            count+=1
    ff.append(count)
ff=[i==ff[0] for i in ff]

 
b = [int(i/2) for i in a]
# b_list=[i%4==0 for i in b]
# bb=sum(b_list)
# if bb!=0 and bb!=n:
if all(ff)==False:
    print(0)
    exit()

ans2= b[0]
for i in range(1,n):
    ans2 = ans2 * b[i] // fractions.gcd(ans2, b[i])

# tf=[(ans2/i)%2==0 for i in b]
# and any(tf)
if ans2>m:
    print(0)
else:
    print((m-ans2)//(ans2*2)+1)

Submission status: Accepted

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

half = [i//2 for i in A]

def f(v):
    r = 0
    while v % 2 == 0:
        v /= 2
        r += 1
    return r

from fractions import gcd
def f2(x, y):
    return (x * y) // gcd(x, y)

d = f(A[0])
for ai in A:
    if d != f(ai):
        print(0)
        break
else:
    lcm = 1
    for ai in half:
        lcm = f2(lcm, ai)

    r = M // lcm
    ans = (r + 1) // 2
    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)

n,m = map(int, input().split())
a = list(map(int, input().split()))
lcm_a = a[0]
for i in a[1:]:
  lcm_a = lcm_a * i // fractions.gcd(lcm_a,i)
  if lcm_a > m * 2:
    print(0)
    exit()
if all([(lcm_a // i) % 2 for i in a]):
  ans = (m - lcm_a // 2) // lcm_a + 1
  print(ans)
else:
  print(0)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n, m = [int(x) for x in input().strip().split()]
a = list(set([int(x)//2 for x in input().strip().split()]))

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

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

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

cnt = div2cnt(a[0])

for i, aa in enumerate(a):
    if div2cnt(aa) != cnt:
        print(0)
        exit()
    a[i] >>= cnt
else:
    m >>= cnt

lcm_ = 1
for aa in a:
    lcm_ = lcm(lcm_, aa)
    if lcm_ > m:
        print(0)
        exit()

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

Submission status: Accepted

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 f(x):
    cnt=0
    while x%2==0:
        x//=2
        cnt+=1
    return cnt
C=f(A[0])
for a in A:
    if f(a)!=C:
        print(0)
        sys.exit()
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):
    LCM=lcm(LCM,A[i])
if LCM>M:
    ans=0
else:
    M//=LCM
    ans=(M+1)//2
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

lcm = lambda a, b: a * b // gcd(a, b)

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

Y = reduce(lcm, A)

if any((Y // a) % 2 == 0 for a in A):
    print(0)
    quit()

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

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 gcd(x,y):
    if y == 0: return x
    else: return gcd(y,x%y)

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

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

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

t = f(na[0])
for i in range(1,n):
    if t != f(na[i]):
        print(0)
        exit()

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

if m < l:
    ans = 0
else:
    ans = 1 + (m-l)//(2*l)

print(ans)

Submission status: Accepted

Solution code:
import fractions
import math
n,m = map(int,input().split())
l = list(map(int,input().split()))
count = 0
while True:
    if l[0] % 2 == 0:
        l[0] //= 2
        count += 1
    else:
        break

for i in range(1,n):
    l[i] //= 2**count
    if l[i] % 1 != 0 or l[i] % 2 == 0:
        print(0)
        exit()
    

ans = l[0]
for i in range(1,n):
    ans = ans * l[i] //fractions.gcd(ans,l[i])

ans1 = (m//2**(count-1))//ans


if ans1 % 2 == 0:
    print(ans1//2)
else:
    print(ans1//2+1)

Submission status: Accepted

Solution code:
from functools import reduce

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

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

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

lcmB = reduce(lcm, Bs)

for B in Bs:
    if lcmB // B % 2 == 0:
        print(0)
        break
else:
    num = M // lcmB
    print((num+1)//2)

Submission status: Accepted

Solution code:
import math
import fractions

#最小公倍数
def union_lcm(lists):
    if len(lists)==1:
        return lists[0]
    elif len(lists)>1:
        num=lists[0]
        for i in range(1,len(lists)):
            num=num*lists[i]//fractions.gcd(num,lists[i])
        return num


#最大公約数
def union_gcd(lists):
    if len(lists)==1:
        return lists[0]
    elif len(lists)>1:
        num=lists[0]
        for i in range(1,len(lists)):
            num=fractions.gcd(num,lists[i])
        return num
    
n,m=map(int,input().split())
lists=list(map(int,input().split()))

#受け取ったリスト内の要素を2で割る(uselistっていうlistに保管)
uselist=[0 for i in range(n)]
for i in range(n):
    uselist[i]=lists[i]//2
  
G=union_lcm(uselist)
flag=True
for some in uselist:
    if (G//some)%2==0:
        flag=False
        break
if flag:
    if (m//G)%2==0:
        print((m//G)//2)
    else:
        print((m//G+1)//2)
    
else:
    print(0)

Submission status: Accepted

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

a =  sorted([int(x)//2 for x in input().split()],reverse=True)

import fractions

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

import math

lcm1 = 1
for i in a:
    lcm1 = lcm(lcm1, i)
    if((lcm1//i)%2==0):
        print(0)
        exit()

print(math.ceil((m//lcm1)/2))

Submission status: Accepted

Solution code:
from fractions import gcd
N, M = map(int, input().split())
A = list(map(lambda x: int(x)//2, input().split()))


def num_of_2(x):  # xがもつ素因数2の個数を返す
    c = 0
    while x % 2 == 0:  # まだ2で割り切れるようなら続ける
        c += 1
        x //= 2
    return c


a0 = num_of_2(A[0])
if all([num_of_2(a) == a0 for a in A]):  # 素因数2の個数が全て等しいなら処理をする
    def lcm(x, y):
        return (x*y) // gcd(x, y)  # 2つの数字の積を2つの数字の最大公約数で割ると2つの数字の最小公倍数が分かる

    c = 1
    for a in A:
        c = lcm(a, c)
        if c >= 10**18:
            break

    ans = M // c
    print((ans+1)//2)  # 奇数倍のものだけ欲しいから？

else:  # 素因数2の個数が等しくないものがある場合は0を出力
    print(0)

Submission status: Accepted

Solution code:
import sys
import fractions

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

g = 0
mx_2 = 0
for i in a:
    tmp = 0
    while i % (2 ** tmp) == 0: tmp += 1
    mx_2 = max(mx_2, tmp - 1)
    g = fractions.gcd(g, i)

if g % (2 ** mx_2) != 0 or g % (2 ** (mx_2 + 1)) == 0:
    print(0)
else:
    prod = 1
    lcm = 1
    g = 0
    for i in a:
        lcm = lcm * i // 2 // fractions.gcd(lcm, i // 2)

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

Submission status: Accepted

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

a =  [int(x)//2 for x in input().split()]

import fractions

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

import math

lcm1 = 1
for i in a:
    lcm1 = lcm(lcm1, i)
    if((lcm1//i)%2==0):
        print(0)
        exit()

print(math.ceil((m//lcm1)/2))

Submission status: Accepted

Solution code:
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)  
  
B = [a for a in A]

while 1:
  cnt = 0
  for b in B:
    cnt += b % 2
  if cnt == 0:
    for i in range(N):
      B[i] //= 2
  else:
    if cnt == N:
      break
    else:
      print(0)
      exit()
#print("B:", B)

x = A[0]
for i in range(1, N):
  x = lcm(x, A[i])
  if x // 2 > M:
    print(0)
    exit()
#print("x:", x)

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

Submission status: Accepted

Solution code:
import fractions
from functools import reduce
import collections

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

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

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



n, m = map(int, input().split())
a = list(map(int, input().split()))
a=set(a)
b=list(a)
n1=len(b)
count=0
v=[]

x=lcm_list(b)

for i in range(n1):
    while b[i]%2==0:
        b[i]=b[i]//2
        count+=1
    v.append(count)
    count=0

for i in range(n1-1):
    if v[i]!=v[i+1]:
        print(0)
        exit()

print((m-x//2)//x+1)

Submission status: Accepted

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

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

def count_div2(value):
    count = 0
    while value % 2 == 0:
        count += 1
        value //= 2
    return count

min_value = lcm(A)
amount = M * 2 // min_value

div2 = count_div2(A[0])
if any([count_div2(a) != div2 for a in A]):
    print(0)
else:
    print((amount + 1) // 2)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

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

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

lh = list(map(lambda x:x//2, l))
lcm = reduce(lcm,lh)
res = 0
times = [(lcm//x)%2==1 for x in lh]

if all(times):
    res = ((m // lcm) +1) // 2

print(res)

Submission status: Accepted

Solution code:
import sys
from fractions import gcd
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,M=map(int,input().split())
    a=tuple(map(lambda x:int(x)//2,input().split()))
    t=a[0]
    c=0
    while True:
        if t%2==0:
            c+=1
            t//=2
        else:
            break
    l=a[0]
    for x in a[1:]:
        if x%(2**c)!=0 or x%(2**(c+1))==0:
            print(0)
            exit()
        l=l*x//gcd(l,x)
    print((M+l)//(l*2))

        

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import fractions
import math

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

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

def chk(i):
    cnt=0
    while True:
        if i%2==0:
            i/=2
            cnt+=1
        else:
            break
    return cnt

flag=0
number=chk(A[0])
for i in A:
    if chk(i)!=number:
        print(0)
        exit()

l = 1
for i in A:
    l = l * i//2 // fractions.gcd(l, i//2)
 
print((m // l + 1) // 2)

"""
num=A[0]//2
flag2=0
if flag==0:
    for i in range(1,len(A)):
        num=lcm(num,A[i]//2)
        if num>m:
            flag2=1
            break
    if flag2==1:
        print(0)
    else:
        print(math.ceil(m//num/2))
"""

Submission status: Accepted

Solution code:
import sys
import math
import functools
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
def lcm(a, b):
    return a * b // gcd (a, b)
def lcm_n(nums):
    return functools.reduce(lcm, nums)
def count_div2(x):
    c = 0
    while x%2 == 0:
        c += 1
        x //= 2
    return c
n, m = na()
a = na()
div2 = count_div2(a[0])
if any([count_div2(ai) != div2 for ai in a]):
    print(0)
else:
    r = lcm_n(a)//2
    b = m//r
    print((b+1)//2)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc150/submissions/9395610

def main():
    from functools import reduce

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

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

        return a * b // _gcd(a, b)

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

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

    e = len(set(map(count_two, a)))
    if e != 1:
        print(0)
        return

    # x=(ai/2)*(2p+1)と変形する
    # 2p+1は奇数だから、
    # すべてのiについて,xと(ai/2)は,2で割れる回数が等しい必要がある

    x = reduce(lcm, a)
    ret = (m // x) - (m // (x + x))
    print(ret)
    # xは(ai/2)の最小公倍数の奇数倍
    # (ai/2)の最小公倍数の倍数全体から
    # (ai/2)の最小公倍数の偶数倍を引いた残り


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
N, M = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
a_num = np.array(a)
x = a_num // 2
count_even = np.count_nonzero(x % 2 == 0)
if count_even != 0 and count_even != N:
    print(0)
    sys.exit()
c = []
from collections import Counter
if count_even == N:
    for i in x:
        cnt = 0
        cnt = format(i, 'b')[::-1].find('1')
        c.append(cnt)
    c = Counter(c)
    if len(c.keys()) != 1:
        print(0)
        sys.exit()
    
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)

minmulti = lcm(* x)
temp = M // minmulti
if temp % 2 == 0:
    print(temp // 2)
else:
    print(1 + temp // 2)

Submission status: Accepted

Solution code:
import sys
from fractions import gcd
import math

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

A = []
for a in AA:
    A.append(a//2)

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

a0 = f(A[0])
for a in A:
    if f(a) != a0:
        print(0)
        sys.exit()

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

l = A[0]
for a in A:
    l = lcm(l,a)

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

Submission status: Accepted

Solution code:
#%%
import fractions
def gcd_base(x, y):
    return fractions.gcd(x, y)

def gcd_list(l):
    tmp = l[0]
    for i in range(1, len(l)):
        tmp = gcd_base(tmp, l[i])
    return tmp

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

def lcm_list(l):
    tmp = l[0]
    for i in range(1, len(l)):
        tmp = lcm_base(tmp, l[i])
        if tmp > 10**9:
            tmp = -1
            break
    return tmp

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

lcm = lcm_list(a)
if lcm == -1:
    ans = 0
else:
    for i in range(n):
        if (lcm // a[i]) % 2 == 0:
            ans = 0 
            f1 = False
            break
    if f1:
        ans = (m + lcm) // (2 * lcm)
print(ans)





# %%

Submission status: Accepted

Solution code:
#%%
import fractions
def gcd_base(x, y):
    return fractions.gcd(x, y)

def gcd_list(l):
    tmp = l[0]
    for i in range(1, len(l)):
        tmp = gcd_base(tmp, l[i])
    return tmp

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

def lcm_list(l):
    tmp = l[0]
    for i in range(1, len(l)):
        tmp = lcm_base(tmp, l[i])
        if tmp > 10**9:
            tmp = -1
            break
    return tmp

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

lcm = lcm_list(a)
if lcm == -1:
    ans = 0
else:
    for i in range(n):
        if (lcm // a[i]) % 2 == 0:
            ans = 0 
            f1 = False
            break
    if f1:
        ans = (m + lcm) // (2 * lcm)
print(ans)

Submission status: Accepted

Solution code:
import math
import fractions


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


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


def f(x):  # 2で割れる回数
    c = 0
    while x % 2 == 0:
        x //= 2
        c += 1
    return c


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

    # a -> a'
    for i in range(len(a)):
        if a[i] % 2 == 1:
            print(0)
            return
        a[i] //= 2

    # a' -> a''
    t = f(a[0])
    for i in range(len(a)):
        if(f(a[i]) != t):
            print(0)
            return
        a[i] //= 2**t

    l = 1
    for i in range(len(a)):
        l = lcm_base(l, a[i])
        if l > m:
            print(0)
            return

    m //= 2**t
    m //= l
    ans = (m+1)//2
    print(ans)


main()

Submission status: Accepted

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

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

ma = 0
mod2count = -1
for i in range(n):
    if mod2count == -1:
        mod2count = bin(a[i])[2:][::-1].find('1')
    if mod2count != bin(a[i])[2:][::-1].find('1'):
        print(0)
        exit()
    a[i] = a[i] // 2
    if a[i] > ma:
        ma = a[i]

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

tmp = m // l
if tmp % 2 == 0:
    print(tmp // 2)
else:
    print(tmp // 2 + 1)

Submission status: Accepted

Solution code:
def cnt2(n):
    res=0
    while n%2==0:
        n//=2
        res+=1
    return res

def GCD(x,y):
    x,y=max(x,y),min(x,y)
    if x%y==0:
        return y
    else:
        return GCD(y,x%y)

def LCM(x,y):
    return x*y//GCD(x,y)

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

s={cnt2(ai) for ai in a}
if 0 in s or len(s)>1:
    ans=0
else:
    lcm=1 # 2で割るのは後にする
    for ai in a:
        lcm=LCM(lcm,ai)
    lcm//=2
    ans=(M//lcm+1)//2

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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 = [ai//2 for ai in a]
cnt = [0]*N

for i in range(N):
    tmp = b[i]
    
    while tmp%2==0:
        tmp //= 2
        cnt[i] += 1

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

for bi in b:
    L = lcm(L, bi)

L2 = 1

for ai in a:
    L2 = lcm(L2, ai)

if L>M:
    print(0)
else:
    print((M-L)//L2+1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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 = [ai//2 for ai in a]
    
L = 1

for bi in b:
    L = lcm(L, bi)

flag = True

for i in range(N):
    if (L-b[i])%a[i]!=0:
        flag = False
    
if not flag:
    print(0)
    exit()
    
L2 = 1

for ai in a:
    L2 = lcm(L2, ai)

if L>M:
    print(0)
else:
    print((M-L)//L2+1)

Submission status: Accepted

Solution code:
import fractions
from functools import reduce

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

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

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

for i in range(len(a)):
    if a[i] % 2 == 1:
        print(0)
        exit()
    a[i] //= 2

t = f(a[0])
for i in range(len(a)):
    if f(a[i]) != t:
        print(0)
        exit()
    a[i] >>= t #a[i] //= 2 ** t
M >>= t

l = 1
for i in range(N):
    l = lcm(l, a[i])
    if l > M:
        print(0)
        exit()

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

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N,M=map(int,input().split())
a = list(map(int, input().split()))
k=0
t=a[0]
while 1:
    if t%2==0:
        k+=1
        t//=2
    else:
        break
K=2**k
from fractions import gcd
l=t
for i in a:
    if i%K==0 and (i//K)%2==1:
        t=i//K
        l=l*t//gcd(l,t)
        if l>M:
            print(0)
            break
    else:
        print(0)
        break
else:
    print((M-l*K//2)//(K*l)+1)

Submission status: Accepted

Solution code:
from functools import reduce

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

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 cntTwo(n):
    cnt = 0
    while n % 2 == 0:
        cnt += 1
        n //= 2
    return cnt

if len(set(map(cntTwo, A))) != 1:
    print(0)
    exit()

def merge(a, b):
    l = lcm(a, b)
    if l > 10 ** 9:
        return 0
    return l

x = reduce(merge, A)
if x == 0:
    print(0)
else:
    print(m//x - m//(x*2))

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

H=[a//2 for a in A]
lcm_H=H[0] if N==1 else lcm(H[0],H[1])
for i in range(2,N):
    lcm_H=lcm(lcm_H,H[i])

def div2(a):
    ret=0
    while a:
        if a&1==0:
            a>>=1
            ret+=1
        else:
            break
    return ret

t=div2(A[0])
if t==0:
    print(0)
    exit()

for i in range(N):
    if div2(A[i])!=t:
        print(0)
        exit()
    A[i]>>=t

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

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

def div2(a):
    ret=0
    while a:
        if a&1==0:
            a>>=1
            ret+=1
        else:
            break
    return ret

t=div2(A[0])
if t==0:
    print(0)
    exit()

for i in range(N):
    if div2(A[i])!=t:
        print(0)
        exit()
    A[i]>>=t
M>>=(t-1)

l=1
for i in range(N):
    l=lcm(l,A[i])

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

Submission status: Accepted

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

from fractions import gcd

# 最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# ２で割れる回数
def div2count(num):
  return (num ^ (num - 1)).bit_length() - 1

cnt = div2count(ha[0])

if not all([div2count(i) == cnt for i in ha]):
  print(0)
else:
  l = 1
  for i in ha:
    l = lcm(l, i)
  ans = (m + l) // (2 * l)
  print(ans)

Submission status: Accepted

Solution code:
N,M = list(map(int,input().split()))
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
def twocount(n):
    c = 0
    while n%2 == 0:
        n //= 2
        c += 1
    return c
 
a2 = [int(i//2) for i in map(int,input().split())]
count2 = set()
for i in a2:
    tc = twocount(i)
    count2.add(tc)
if len(count2) == 1:
 
    if len(a2) == 1:
        div = M//a2[0]
        print((div+1)//2)
    else:
        gcda = a2[0]*a2[1]//gcd(a2[0],a2[1])
        for i in range(2,N):
            gcda = gcda*a2[i]//gcd(gcda,a2[i])
        div = M//gcda
        print((div+1)//2)
    
else:
    print(0)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

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

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

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

B = [a//2 for a in A]

L = 1
for b in B:
    L = lcm(L, b)

ans = 0
if all((L//b) & 1 for b in B):
    ok = 0
    ng = M*2
    while abs(ok-ng) > 1:
        med = (ok+ng)//2
        if (med*2-1)*L <= M:
            ok = med
        else:
            ng = med
    print(ok)
else:
    print(ans)

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 numberof2(n):
  ans = 0
  while n%2 == 0:
    n = n//2
    ans += 1
  return ans

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

for i in range(N):
  if A[i]%2 == 0:
    A[i] = A[i]//2
  else:
    cnt = 0
for i in range(N-1):
  if numberof2(A[i]) != numberof2(A[i+1]):
    cnt = 0
    
lcm = A[0]
for i in range(1, N):
  lcm = lcm*A[i]//gcd(lcm, A[i])

print(min(cnt, 1+(M-lcm)//(2*lcm)))