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 sys
input = sys.stdin.readline

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

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

import fractions
from functools import reduce

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

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

cnt = f(a[0])
for i in range(1, len(a)):
    if cnt != f(a[i]):
        print(0)
        break
else:
    lcm = reduce(lambda x, y: getLCM(x, y), a)
    ans = (m-lcm) // (lcm*2) + 1 if m >= lcm else 0
    print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
def yaku2(a):
    count=0
    while a%2==0:
        a=a//2
        count+=1
    return(count)

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

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

yaku=yaku2(A[0])
for i in range(1,N):
    if yaku!=yaku2(A[i]):
        print(0)
        exit()



_lcm=A[0]
for i in range(1,N):
    A[0]=lcm(A[0],A[i])
#print(A[0])
print((M-(A[0]-A[0]//2-A[0]))//A[0])

Submission status: Accepted

Solution code:
"""
難しい :(
"""

import sys
input = sys.stdin.readline
from functools import reduce
from fractions import gcd
from math import ceil

def is_same(A:list):
    exp = 0
    for i in range(len(A)):
        now = 0
        while A[i] % 2 == 0:
            A[i] >>= 1
            now += 1

        if i == 0:
            exp = now
            continue

        if exp != now:
            return False, exp
    
    return True, exp

def lcm_base(x, y):
    return (x * y) // gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def main():
    _,M = map(int,input().split())
    A = [int(i)//2 for i in input().split()]

    flag, exp = is_same(A)
    if not flag:
        print(0)
        exit()

    power = 2 ** exp
    MINX = lcm_list(A)

    ans = (M+MINX*power) // (2*power*MINX)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
"""
難しい :(
"""

import sys
input = sys.stdin.readline
from functools import reduce
from fractions import gcd
from math import ceil

def is_same(A:list):
    exp = 0
    for i in range(len(A)):
        now = 0
        while A[i] % 2 == 0:
            A[i] >>= 1
            now += 1

        if i == 0:
            exp = now
            continue

        if exp != now:
            return False, exp
    
    return True, exp

def lcm_base(x, y):
    return (x * y) // gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

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

flag, exp = is_same(A)
if not flag:
    print(0)
    exit()

power = 2 ** exp
MINX = lcm_list(A)

ans = (M+MINX*power) // (2*power*MINX)
print(ans)

Submission status: Accepted

Solution code:
from functools import reduce

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


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


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


nth = [f(ai) for ai in a]
if len(set(nth)) == 1:
    half_a = [ai >> 1 for ai in a]
    L = reduce(lambda x, y: x * y // gcd(x, y), half_a)
    ans = (M - L) // (2 * L) + 1 if M >= L else 0
else:
    ans = 0
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

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

count = 0
tmp = A[0]
while tmp % 2 == 0:
    count += 1
    tmp //= 2
for a in A[1:]:
    tmp = a
    tmp_count = 0
    while tmp % 2 == 0:
        tmp_count += 1
        tmp //= 2
    if count != tmp_count:
        print (0)
        exit()

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

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

tmp = lcm(*A) // 2
# print (tmp)
ans = M // tmp

ans = (ans + 1) // 2

print (ans)

Submission status: Accepted

Solution code:
import sys
N,M=map(int,input().split())
A = list( map(int,input().split()) )
for i in range(N): A[i] = A[i]//2


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

# 全Aが2で割り切れる数が等しいか確認
cnt = 1
while A[0]%(1<<cnt) == 0 :
    cnt += 1
for i in range(1,N):
    if (A[i]%(1<<cnt) == 0) or (A[i]%(1<<(cnt-1)) != 0):
        print(0)
        sys.exit()

A.append(1)
a = A[0]
b = A[1]
lcm = a * b // GCD(a,b)
#print(lcm)
if lcm > M:
    print(0)
    sys.exit()
for i in range(2,N):
    a = lcm
    b = A[i]
    lcm = a * b // GCD(a,b)
    if lcm > M:
        print(0)
        sys.exit()
print( (M+lcm) // (lcm*2) )

Submission status: Accepted

Solution code:
import fractions
from functools import reduce
import math
import sys

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

def main():
  N,M=map(int,input().split())
  numList=list(map(int,input().split()))
  numList=list(map(num_double,numList))
  numList=list(set(numList))
  
  count=0
  flag=0
  finFlag=0
  evenCount=0
  
  while flag==0:
    evenCount=0
    for i in range(len(numList)):
      if(numList[i]%2==0):
        evenCount+=1
    if(evenCount==len(numList)):
      numList=list(map(num_double,numList))
      M=math.floor(M/2)
    elif(evenCount==0):
      flag=1
    else:
      flag=1
      finFlag=1
  
  if(finFlag==1):
    print(count)
    sys.exit()
  
  else:
    def lcm_base(x, y):
        return (x * y) // fractions.gcd(x, y)

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

    endFlag=0
    nowMagnification=1
    nowNum=0
    startNum=lcm_list(numList)

    while endFlag==0:
      nowNum=startNum*nowMagnification
      if(1<=nowNum)and(nowNum<=M):
        count+=1
        nowMagnification+=2
        continue
      else:
        endFlag=1

    print(count)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from _collections import deque
from _ast import Num


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

import numpy
from collections import deque
from math import sqrt
from math import floor
# https://atcoder.jp/contests/abc150/tasks/abc150_d
# D - Semi Common Multiple
"""

"""


def gcd(a, b):
    h = max(a, b)
    l = min(a, b)
    if h % l:
        return gcd(l, h % l)
    else:
        return l


N = gi()
M = gi()
A = [0] * N
g = 0
for i in range(N):
    A[i] = gi()
    if i:
        g = gcd(g, A[i])
    else:
        g = A[i]

lcm = g

for a in A:  #catch!!!
    lcm = (lcm * a) // gcd(lcm, a)

hl = lcm // 2
all_good = 1
for a in A:
    q = lcm // a
    if (q % 2 == 0 or lcm % a):
        all_good = 0
        break

if all_good:
    ans = M // hl - M // lcm  #cleaner
else:
    ans = 0
print(ans)

Submission status: Accepted

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


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


N, M = map(int, input().split())
a = list(map(int, input().split()))
cnt = TwoFactor(a[0])
for i in range(N):
    if cnt != TwoFactor(a[i]):
        print(0)
        exit()
lcm = a[0]
for i in range(1, N):
    g = gcd(lcm, a[i])
    lcm = lcm * a[i] // g
    if lcm / 2 > M:
        print(0)
        exit()
print(M // (lcm // 2) - M // lcm)

Submission status: Accepted

Solution code:
import fractions
from functools import reduce
 
def lcm_b(a, b):
        #print("base",a,b)
        return (a * b) // fractions.gcd(a, b)
 
def lcm_o():
        global n
        return reduce(lcm_b, n)
 
def chk(v):
        global n
        for i in range(1,30):
                if v%2 == 1:break
                v = v//2
        t=2**(i-1)
        for j in range(len(n)):
                s=int(n[j]/t)
                if n[j] % t == 0 and s % 2 == 1:
                        n[j] = s
 
                else: return 0
        return int(t//2)
 
def mp(v):
        if v%2==1:v+=1
        return int(v//2)
 
N,M= [int(i) for i in input().split()]
n = [int(i) for i in input().split()]
n=sorted(set(n),reverse = True)
bs = n[0]//2
 
if len(n) > 1:
        c = chk(n[-1])
        if  c != 0:
                v = lcm_o()*c
                if v > M: print(0) 
 
                else: print(mp(M//v))
                        
        
        else: print(0)
        
elif len(n)==1: print(mp(M//bs))

Submission status: Accepted

Solution code:
import fractions
from functools import reduce
 
def lcm_b(a, b):
        #print("base",a,b)
        return (a * b) // fractions.gcd(a, b)
 
def lcm_o():
        global n
        return reduce(lcm_b, n)
 
def chk(v):
        global n
        for i in range(1,30):
                if v%2 == 1:break
                v = v//2
        t=2**(i-1)
        for j in range(len(n)):
                s=int(n[j]/t)
                if n[j] % t == 0 and s % 2 == 1:
                        n[j] = s
 
                else: return 0
        return int(t//2)
 
def mp(v):
        if v%2==1:v+=1
        return int(v//2)
 
N,M= [int(i) for i in input().split()]
n = [int(i) for i in input().split()]
n=sorted(set(n),reverse = True)
bs = n[0]//2
 
if len(n) > 1:
        c = chk(n[-1])
        if  c != 0:
                v = lcm_o()*c
                if v > M: print(0) 
 
                else:
                        print(mp(M//v))
                        #v = M//v
                        #if v%2==1: v+=1
                        #print(int(v//2))
        
        else: print(0)
        
elif len(n)==1:
        print(mp(M//bs))
        #v = M//bs
        #if v%2==1: v+=1
        #print(int(v//2))

Submission status: Accepted

Solution code:
import fractions
from functools import reduce

def lcm_b(a, b):
        #print("base",a,b)
        return (a * b) // fractions.gcd(a, b)

def lcm_o():
        global n
        return reduce(lcm_b, n)

def chk(v):
        global n
        for i in range(1,30):
                if v%2 == 1:break
                v = v//2
        t=2**(i-1)
        for j in range(len(n)):
                s=int(n[j]/t)
                if n[j] % t == 0 and s % 2 == 1:
                        n[j] = s

                else: return 0
        return int(t//2)

def mp(v):
        if v%2==1:v+=1
        return int(v//2)

N,M= [int(i) for i in input().split()]
n = [int(i) for i in input().split()]
n=sorted(set(n),reverse = True)
bs = n[0]//2

if len(n) > 1:
        c = chk(n[-1])
        if  c != 0:
                v = lcm_o()*c
                if v > M: print(0) 

                else:
                        #print(mp(M//v))
                        v = M//v
                        if v%2==1: v+=1
                        print(int(v//2))
        
        else: print(0)
        
elif len(n)==1:
        #print(mp(M//bs))
        v = M//bs
        if v%2==1: v+=1
        print(int(v//2))

Submission status: Accepted

Solution code:
import fractions
from functools import reduce
 
 
 
def lcm_b(a, b):
        #print("base",a,b)
        return (a * b) // fractions.gcd(a, b)
 
def lcm_o():
        global n
        return reduce(lcm_b, n)
 
def chk(v):
        global n
        for i in range(1,30):
                if v%2 == 1:break
                v = v//2
        t=2**(i-1)
        for j in range(len(n)):
                if n[j] % t == 0 and (n[j] / t) % 2 == 1:
                        n[j] = int(n[j]/t)
                else: return 0
        return int(t//2)
N,M= [int(i) for i in input().split()]
n = [int(i) for i in input().split()]
n=sorted(set(n),reverse = True)
 
bs = n[0]//2
 
if len(n) > 1:
        
        c = chk(n[-1])
        
        if  c != 0:
                v = lcm_o()*c
                
                if v > M:
                        print(0) 
                else:
                        v = M//v
                        if v%2==1: v+=1
                        print(int(v//2))
        
        else: print(0)
elif len(n)==1:
        v = M//bs
        if v%2==1: v+=1
        print(int(v//2))

Submission status: Accepted

Solution code:
import fractions
from functools import reduce

 
 
def lcm_b(a, b):
        #print("base",a,b)
        return (a * b) // fractions.gcd(a, b)
 
def lcm_o():
        global n
        return reduce(lcm_b, n)
 
def chk(v):
        global n
        for i in range(1,30):
                if v%2 == 1:break
                v = v//2
        t=2**(i-1)
        for j in range(len(n)):
                if n[j] % t == 0 and (n[j] / t) % 2 == 1:
                        n[j] = int(n[j]/t)
                else: return 0
        return int(t//2)
N,M= [int(i) for i in input().split()]
n = [int(i) for i in input().split()]
n=sorted(set(n),reverse = True)

bs = n[0]

if len(n) > 1:
        
        c = chk(n[-1])
        
        if  c != 0:
                v = lcm_o()*c
                
                if v > M:
                        print(0) 
                else:
                        v = M//v
                        if v%2==1: v+=1
                        print(int(v//2))
        
        else: print(0)
elif len(n)==1:
        v = int(bs*0.5)
        v = M//v
        if v%2==1: v+=1
        print(int(v//2))

Submission status: Accepted

Solution code:
import fractions
from functools import reduce
N,M= [int(i) for i in input().split()]
n = [int(i) for i in input().split()]
#print(n)
n=sorted(set(n),reverse = True)
bs = n[0]
#print(n)
#c=len(n)
 
 
def lcm_b(a, b):
        #print("base",a,b)
        return (a * b) // fractions.gcd(a, b)
 
def lcm_o():
        global n
        return reduce(lcm_b, n)
 
def chk(v):
        global n
        for i in range(1,30):
                if v%2 == 1:break
                v = v//2
        t=2**(i-1)
        for j in range(len(n)):
                if n[j] % t == 0 and (n[j] / t) % 2 == 1:
                        n[j] = int(n[j]/t)
                else: return 0
        return int(t//2)
 
if len(n) > 1:
        
        c = chk(n[-1])
        
        if  c != 0:
                v = lcm_o()*c
                
                if v > M:
                        print(0) 
                else:
                        v = M//v
                        if v%2==1: v+=1
                        print(int(v//2))
        
        else: print(0)
elif len(n)==1:
        v = int(bs*0.5)
        v = M//v
        if v%2==1: v+=1
        print(int(v//2))

Submission status: Accepted

Solution code:
import fractions
from functools import reduce
N,M= [int(i) for i in input().split()]
n = [int(i) for i in input().split()]
#print(n)
n=sorted(set(n),reverse = True)
bs = n[0]
#print(n)
#c=len(n)
 
 
def lcm_b(a, b):
        #print("base",a,b)
        return (a * b) // fractions.gcd(a, b)
 
def lcm_o():
        global n
        return reduce(lcm_b, n)
 
def chk(v):
        global n
        for i in range(1,30):
                if v%2 == 1:break
                v = v//2
        t=2**(i-1)
        for j in range(len(n)):
                if n[j] % t == 0 and (n[j] / t) % 2 == 1:
                        n[j] = int(n[j]/t)
                else: return 0
        return i-1
 
if len(n) > 1:
        
        c = chk(n[-1])
        
        if  c != 0:
                v = lcm_o()*(2**(c-1))
                
                if v > M:
                        print(0) 
                else:
                        v = M//v
                        if v%2==1: v+=1
                        print(int(v//2))
        
        else: print(0)
elif len(n)==1:
        v = int(bs*0.5)
        v = M//v
        if v%2==1: v+=1
        print(int(v//2))

Submission status: Accepted

Solution code:
import fractions
def func(x, y):
  tmp=fractions.gcd(x, y)
  return x*y//tmp

N, M=map(int, input().split())
if N==1:
  a=int(input())
  c=a//2
  if c>M:
    print(0)
  else:
    print(int((M/c-1)/2)+1)
  exit()

a=list(map(int, input().split()))
b=[a[i]//2 for i in range(N)]

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

c=func(b[0], b[1])
for i in range(2, N):
  c=func(c, b[i])
  
p=[f(a[i]) for i in range(N)]
p.sort()
for i in range(N-1):
  if p[i]!=p[i+1]:
    print(0)
    exit()
    
if c>M:
  print(0)
else:
  print(int((M/c-1)/2)+1)

Submission status: Accepted

Solution code:
def lcm(a, b):
    return a * b // gcd(a, b)
    
    
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    if b == 0:
        return a
    return gcd(b, a%b)

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    base = 2
    while A[0] % (base*2) == 0:
        base *= 2
    minimum = 1
    for a in A:
        if a % base != 0 or (a // base) % 2 == 0:
            print(0)
            return
        minimum = lcm(minimum, a//base)
        if minimum > M:
            print(0)
            return
    minimum *= base // 2
    ans = (M // minimum + 1) // 2
    print(ans)
        

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# 問題文：長さNの偶数からなる正の整数列A=a1,a2,...,aNと、整数Mが与えられます。
#        任意のk(1≤k≤N)に対して以下の条件を満たす正の整数XをAの「半公倍数」と定義します。
#        X=ak×(p+0.5)を満たす負でない整数pが存在する。
#        1以上M以下の整数のうちのAの半公倍数の個数を求めてください。
# 入力 : 以下の形式で標準入力から与えられる。
#       N M
#       a1 a2 ... aN
# 出力 : 1 以上 M 以下の整数のうちの A の半公倍数の個数を出力せよ。

# 半公倍数の個数を求める
def n_hankobaisu(M, min_hankobaisu):
    q = M // min_hankobaisu
    if q % 2 == 1:
        q += 1
    return int(q/2)

# nが何回2で割り切れるかを求める
def nankai_2de_warikireruka(n):
    i = 0

    # nは最大10^9 処理速度を上げるため、2^10で割る
    for i in range(0,99999999999):
        if n >= 1024 and n % 1024 == 0:
            n = n / 1024
            i += 10
        else:
            break

    for i in range(0,9999999999999999999):
        if n > 1:
            n, mod = divmod(n, 2)
            if mod == 1:
                break
                i += 1
        else:
            break

    return i

# 最小半公倍数を求める
def min_hankobaisu(A, M):
    result = 1
    for i in range(9999999999999):
        result = A[0] * (0.5 + i)

        if len(A) == 1:
            return result

        if result > M:
            print(0)
            exit(0)

        for j in range(1, len(A)):
            q, mod = divmod(result, A[j]/2)
            if q % 2 == 1 and mod == 0:
                # 数列要素すべての半公倍数であるので、最小半公倍数として返却する
                if j == len(A)-1:
                    return int(result)
                continue
            else:
                break # 半公倍数としてふさわしくないので、次の半公倍数候補を求める
    return int(result)

# 正の整数列Aの長さN, 半公倍数の上限M
N, M = map(int, input().split())

# 正の整数列A
A = list(set(list(map(int, input().split()))))
A.sort(reverse=True)
# hankobaisu_list = []

# 2で割り切れる回数が異なる→半公倍数はない
# → その場で終了
p = nankai_2de_warikireruka(A[0])

if N == 1:
    print(n_hankobaisu(M, min_hankobaisu(A, M)))
    exit(0)

for i in range(1, len(A)):
    pi = nankai_2de_warikireruka(A[i])
    if pi != p:
        print(0)
        exit(0)

# 半公倍数の最小値を求める

# 範囲内にいくつの半公倍数があるか求める
#print('最小半公倍数：{}'.format(min_hankobaisu))
#print(int(M/min_hankobaisu)//2 + 1)
print(n_hankobaisu(M, min_hankobaisu(A, M)))

Submission status: Accepted

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

#print(lcm_list(l))

x = lcm_list(l)

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

ans = (m*2)//lcm_list(l)
if ans%2 == 1:
  print((ans+1)//2)
else:
  print(ans//2)

Submission status: Accepted

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

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

eg=dividable_with_2(a[0])

for q in a:
  if dividable_with_2(q) != eg:
    print(0)
    exit()

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

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

d=[i//2 for i in a]
L=d[0]
for i in range(n):
  L=lcm(L,d[i])

ans=(m//L+1)//2

print(ans)

Submission status: Accepted

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

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

eg=dividable_with_2(a[0])

for q in a:
  if dividable_with_2(q) != eg:
    print(0)
    exit()

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

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

d=[i//2 for i in a]
L=d[0]
for i in range(n):
  L=lcm(L,d[i])

ans=(m//L+1)//2

print(ans)

Submission status: Accepted

Solution code:
from functools import reduce
from math import ceil

n, m = map(int, input().split(' '))

alist = list(map(int,input().split(' ')))
# alist = [i // 2  for i in alist]


from fractions import gcd

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

def get_lcm_for(your_list):
    return reduce(lambda x, y: getLCM(x, y), your_list)

lcmr = get_lcm_for(alist)

for a in alist:
    if (lcmr//a)%2 == 0:
        if (lcmr != a):
            print(0)
            exit(0)

result = m//lcmr + 2*m//lcmr%2


print(result)

Submission status: Accepted

Solution code:
def gcd(a,b):
  a,b = min(a,b),max(a,b)
  if a != 0:
    return gcd(b%a,a)
  else:
    return b

n,m = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse=1)
g = a[0]
c = a[0]
mi = a[0]//2
for i in a[1:]:
  while mi <= m:
    if (mi-i//2) % i == 0:
      break
    else:
      mi += c
  if mi > m:
    print(0)
    exit()
  g = gcd(i,c)
  c *= i
  c = c // g
print((m-mi)//c+1)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce


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


def solve(string):
    n, m, *a = map(int, string.split())
    c = 2**len(bin(a[0]).split("1")[-1])
    l = reduce(lcm, (_a if not _a % c and _a // c % 2 else 2 * m + 2 for _a in a))
    return str((m - l // 2) // l + 1) if l <= 2 * m else "0"


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce


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


def solve(string):
    n, m, *a = map(int, string.split())
    c = 2**len(bin(a[0]).split("1")[-1])
    l = reduce(lcm, (0 if _a % c or not _a // c % 2 else _a for _a in a))
    return str((m - l // 2) // l + 1) if l else "0"


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce


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


def solve(string):
    n, m, *a = map(int, string.split())
    c = 2**len(bin(a[0]).split("1")[-1])
    l = reduce(lcm, (2 * m + 2 if _a % c or not _a // c % 2 else _a for _a in a))
    return str((m - l // 2) // l + 1) if l <= 2 * m else "0"


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce


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


def solve(string):
    n, m, *a = map(int, string.split())
    c = 2**len(bin(a[0]).split("1")[-1])
    l = reduce(lcm, (2 * m + 2 if _a % c or not _a // c % 2 else _a for _a in a))
    return str(max((m - l // 2) // l + 1, 0))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce


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


def solve(string):
    n, m, *a = map(int, string.split())
    c = 2**len(bin(a[0]).split("1")[-1])
    l = reduce(lcm, (2 * m + 1 if _a % c or not _a // c % 2 else _a for _a in a))
    return str(max((m - l // 2) // l + 1, 0))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce


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


def solve(string):
    n, m, *a = map(int, string.split())
    c = 2**len(bin(a[0]).split("1")[-1])
    l = reduce(lcm, (2 * m + 2 if _a % c or not _a // c % 2 else _a for _a in a))
    return str(max((m + l // 2) // l, 0))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce
from operator import floordiv


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


def solve(string):
    n, m, *a = map(int, string.split())
    *a, = map(floordiv, a, (2,) * n)
    c = 2**len(bin(a[0]).split("1")[-1])
    l = reduce(lcm, (m + 1 if _a % c or not _a // c % 2 else _a for _a in a))
    return str(max(((m // l + 1) // 2, 0)))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
from functools import reduce


def lcm(a, b):
    ab = a * b
    while b != 0:
        a, b = b, a % b
    return ab // a


def solve(string):
    n, m, *a = map(int, string.split())
    c = 2**len(bin(a[0]).split("1")[-1])
    l = reduce(lcm, (2 * m + 2 if _a % c or not _a // c % 2 else _a for _a in a))
    return str(max((m - l // 2) // l + 1, 0))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
from fractions import gcd


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


def solve(string):
    n, m, *a = map(int, string.split())
    c = 2**len(bin(a[0]).split("1")[-1])
    l = a[0]
    for _a in a:
        if _a % c or not _a // c % 2:
            return "0"
        l = lcm(l, _a)
    return str(max((m - l // 2) // l + 1, 0))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce


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


def count(n):
    c = 0
    while n % 2 == 0:
        c += 1
        n //= 2
    return c


def solve(string):
    n, m, *a = map(int, string.split())
    c = len(bin(a[0]).split("1")[-1])
    for _a in a:
        if count(_a) != c:
            return "0"
    l = reduce(lcm, a)
    return str(max((m - l // 2) // l + 1, 0))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce


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


def count(n):
    c = 0
    while n % 2 == 0:
        c += 1
        n //= 2
    return c


def solve(string):
    n, m, *a = map(int, string.split())
    c = 2**len(bin(a[0]).split("1")[-1])
    for _a in a:
        if _a % c or not _a // c % 2:
            return "0"
    l = reduce(lcm, a)
    return str(max((m - l // 2) // l + 1, 0))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

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


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


def solve(string):
    n, m, *a = map(int, string.split())
    c = 2**len(bin(a[0]).split("1")[-1])
    for _a in a:
        if _a % c or not _a // c % 2:
            return "0"
    l = reduce(lcm, a)
    return str(max((m - l // 2) // l + 1, 0))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce


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


def solve(string):
    n, m, *a = map(int, string.split())
    l = reduce(lcm, a)
    c = 2**len(bin(a[0]).split("1")[-1])
    for _a in a:
        if _a % c or not _a // c % 2:
            return "0"
    return str(max((m - l // 2) // l + 1, 0))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce


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


def solve(string):
    n, m, *a = map(int, string.split())
    l = reduce(lcm, a)
    c = 1
    while a[0] % (2 * c) == 0:
        c *= 2
    for _a in a:
        if _a % c or not _a // c % 2:
            return "0"
    return str(max((m - l // 2) // l + 1, 0))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce


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


def solve(string):
    n, m, *a = map(int, string.split())
    l = reduce(lcm, a)
    c = 1
    while a[0] % (2 * c) == 0:
        c *= 2
    for _a in a:
        if _a % c > 0 or not (_a // c) % 2:
            return "0"
    return str(max((m - l // 2) // l + 1, 0))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce


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


def solve(string):
    n, m, *a = map(int, string.split())
    l = reduce(lcm, a)
    c = 1
    while a[0] % (2 * c) == 0:
        c *= 2
    f = (a[0] // c) % 2
    for _a in a:
        if _a % c > 0 or (_a // c) % 2 != f:
            return "0"
    return str(max((m - l // 2) // l + 1, 0))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce


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


def solve(string):
    n, m, *a = map(int, string.split())
    l = reduce(lcm, a)
    c = 1
    while a[0] % (2 * c) == 0:
        c *= 2
    a = [_a // c if _a % c == 0 else 0 for _a in a]
    for _a in a:
        if not _a or _a % 2 != a[0] % 2:
            return "0"
    return str(max((m - l // 2) // l + 1, 0))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))