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:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from copy import deepcopy
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n, m = LI()
A = LI()

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

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

for i in range(n):
    A[i] //= 2
    if i == 0:
        ret = A[i]
        c0 = 0
        a0 = A[0]
        while a0 % 2 == 0:
            a0 //= 2
            c0 += 1
    else:
        ret = lcm(ret, A[i])
        if ret > m:
            print(0)
            exit()
        c = 0
        while A[i] % 2 == 0:
            A[i] //= 2
            c += 1
        if c != c0:
            print(0)
            exit()


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

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

N, M = map(int, input().split())
*a, = map(int, input().split())
lcm = reduce(lambda x,y:x*y//gcd(x,y), a)

for i in map(lambda x:lcm//x, a):
    if i%2==0:
        print(0)
        break
else:
    start = lcm//2
    print((M-start)//lcm+1)

Submission status: Accepted

Solution code:
from functools import reduce

def gcd(x,y):
    while y: x,y = y,x%y
    return x

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

def ex_euclid(x,y):
    c0,c1 = x,y
    a0,a1 = 1,0
    b0,b1 = 0,1
    while c1:
        a0,a1 = a1,a0-c0//c1*a1
        b0,b1 = b1,b0-c0//c1*b1
        c0,c1 = c1,c0%c1
    return c0,a0,b0

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

if N == 1:
    a = A[0]
    print((M-a//2%a)//a+1)

else:
    LCM = reduce(lcm,A)

    SCMs = []
    flag = True

    for i in range(N-1):
        c,a,b = ex_euclid(A[i],-A[i+1])
        if (A[i+1]-A[i])//2%c == 0:
            SCMs.append(A[i]*((A[i+1]-A[i])//2//c)*a+A[i]//2)
        else:
            flag = False
            break

    print((M-reduce(lcm,SCMs)%LCM)//LCM+1 if flag else 0)

Submission status: Accepted

Solution code:
import fractions
import itertools
import fractions
import heapq
import collections
import bisect
import sys
import functools

sys.setrecursionlimit(10**9)
mod = 998244353
inf = 10**20

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

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

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

n,m = LI()
a = [int(i)//2 for i in LI()]

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

a0 = num_of_2(a[0])
if any([num_of_2(i) != a0 for i in a]):
    print(0)
else:
    def lcm(x,y):
        return x//fractions.gcd(x,y)*y

    c = 1
    for i in a:
        c = lcm(c,i)
        if c>=inf:
            break
    
    ans = m//c
    print((ans+1)//2)

Submission status: Accepted

Solution code:
from functools import reduce
import fractions

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 = list(set(list(map(int, input().split()))))

lcm = 1

for a in a_list:
  lcm = lcm_base(lcm, a)

for a in a_list:
  if (lcm // a) % 2 == 0:
    lcm = 0
    break
if lcm == 0:
  print(0)
elif M == 1 and lcm == 2:
  print(1)
else:
  print(int(-(-M//(lcm//2))/2))

Submission status: Accepted

Solution code:
import sys

def gcd(x,y):
    while y:
        x,y = y , x % y 
    return x

n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
lcm = 1
for i in a:
    lcm = lcm * i // gcd(lcm,i)
for i in a:
    if (lcm//i)%2 == 0:
        print(0)
        sys.exit()
print((m+lcm//2)//lcm)

Submission status: Accepted

Solution code:
import sys

def gcd(x,y):
    while y:
        x,y = y , x % y 
    return x

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

lcm = 1
for i in a:
    lcm = lcm * i // gcd(lcm,i)
for i in a:
    if (lcm//i)%2 == 0:
        print(0)
        sys.exit()
print((m+lcm//2)//lcm)

Submission status: Accepted

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict
from fractions import gcd

con = 10 ** 9 + 7
#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, M = getlist()
	A = getlist()
	B = [int(A[i] // 2) for i in range(N)]
	LCM = B[0]
	for i in range(N - 1):
		GCD = gcd(LCM, B[i + 1])
		LCM = int(LCM * B[i + 1] / GCD)
		if LCM >= 10 ** 10:
			break

	if LCM > M:
		print(0)
	else:
		ans = (M - LCM) // (2 * LCM) + 1
		D = defaultdict(int)
		for i in range(N):
			x = B[i]
			val = 0
			while True:
				if x % 2 == 0:
					val += 1
					x = int(x // 2)
				else:
					break
			D[val] += 1

		if D[val] != N:
			ans = 0

		print(ans)


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import statistics
from fractions import *
import math

def cntTwo(n):
    i = 0
    while n % 2 == 0:
        i += 1
        n //= 2
    return i

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

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

l = set(map(int,input().split()))
l = list(l)
l = [i//2 for i in l]
lc = 1
gc =1
two = cntTwo(l[0])
for i in l:
    if cntTwo(i)!=two:
        print(0)
        exit()
    lc = lc*i//gcd(lc,i)
    

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

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def LOG(x):
    res = 0
    while x%2==0:
        res += 1
        x //= 2
    return res
def main():
    N,X = MI()
    A=sorted(LI())
    lcm = 1
    count_2 = LOG(A[0]//2)
    for a in A:
        a//=2
        lcm = a*lcm//gcd(a,lcm)
        if count_2!=LOG(a) or X<lcm:
            print(0)
            return
    print(ceil(X//lcm,2))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
N,M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
a = 1
MOD = 10**9+7
cnt = 10**9
l = 0
for i in A:
  i = i//2
  a = lcm(a,i)
for i in A:
  cnt1=0
  b=i//2
  if b%2==0:
    while b%2==0:
      b=b/2
      cnt1+=1
  if cnt==10**9:
    cnt=cnt1
  elif cnt!=cnt1:
    print(0)
    exit()
print((M//a+2-1)//2)

Submission status: Accepted

Solution code:
import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
N,M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
a = 1
MOD = 10**9+7
cnt = 0
l = 0
for i in A:
  i = i//2
  a = lcm(a,i)
for i in A:
  cnt1=0
  i=i//2
  b=a//i
  if b%2==0:
    while b%2==0:
      b=b/2
      cnt1+=1
  if cnt==0:
    cnt=cnt1
    l+=1
  else:
    if cnt!=cnt1:
      print(0)
      exit()
if l==N and cnt!=0:
  print(0)
  exit()
print((M//a+2-1)//2)

Submission status: Accepted

Solution code:
import sys, fractions
input = sys.stdin.readline
N,M = map(int,input().split())
aa = list(map(int, input().split()))

lcm = 1
i = 1

for a in aa:
    lcm = a*lcm//fractions.gcd(a,lcm)

ans = 0
ch = True
for a in aa:
	if(0 != ((lcm // 2) - a // 2) % a):
		ch = False
if(ch):
	ans += (M // lcm)
	if (M % lcm) >= (lcm//2):
		ans += 1
	print(ans)
else:
	print(0)

Submission status: Accepted

Solution code:
# Xは正の整数, pは非負整数, A[k]は偶数
# X == A[k] * (p + 0.5)
# X == A[k]//2 * (2*p + 1)
# X / (A[k]//2) == 2*p + 1
# X % (A[k]//2) == 0 and count_div_two(X) == count_div_two(A[k]//2)

# 全てのcount_div_twoが同じ
# M//最小公倍数 / 2 (切り上げ)

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

# c = 0
# for i in range(1, M+1):
#     print(i, [i/a for a in A])
#     if all(i/a-i//a == 0.5 for a in A):
#         c += 1

# print(c)

def gcd(a, b):
    if a > b:
        a, b = b, a
    if a == 0:
        return b
    return gcd(b%a, a)
def lcm(a, b):
    return (a*b) // gcd(a, b)
def count_div_two(x):
    c = 0
    while x%2 == 0:
        x //= 2
        c += 1
    return c

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

if len(set(count_div_two(b_i) for b_i in b)) > 1:
    print(0)
    exit()

b_lcm = 1
for b_i in b:
    b_lcm = lcm(b_lcm, b_i)

c = M//b_lcm
print(-(-c//2))

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
A = list(map(int,input().split()))
AA = max(A)
 
def how_two(n):
    a = 0
    while n %2 ==0:
        a+=1
        n//=2
    return a
 
log2 = how_two(A[0])
for i in A:
    tmplog2 = how_two(i)
    if log2!=tmplog2:
        log2 =0
        break
        
        
if log2==0:
    print(0)
else:
    from fractions import gcd
    l = 1
    dame = 0
    for i in A:
        l = (l*i)//gcd(l,i)
        if l//2 >= 10**9:
            dame = 1
            break
    l //= 2
    
    MAX = (M+l)//(2*l)
    MIN = max(1,-(-(AA+2*l)//(4*l)))
    ans = MAX-MIN +1
    #print(MIN)
    
    if dame==1:
        print(0)
    else:
        print(ans)

Submission status: Accepted

Solution code:
import sys
from fractions import gcd


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


input = sys.stdin.readline

N, M = map(int, input().split())
A = sorted(map(int, input().split()))
LCM = 1
count = -1
for a in A:
    if a % 2 == 1:
        print(0)
        exit()
    tmp_count = 0
    tmp = a
    while tmp % 2 == 0:
        tmp = tmp//2
        tmp_count += 1
    LCM = lcm_base(LCM, a//2)

    if count == -1:
        count = tmp_count
    if tmp_count != count:
        print(0)
        exit()
tmp = (M//LCM)
if tmp % 2 == 0:
    tmp = tmp//2
else:
    tmp = tmp//2+1
print(tmp)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
p = 0
for i in range(N):
  if A[i] % 2 == 0:
    A[i] //= 2
  else:
    p = 1
    break
L = A[0]
k = 0
while A[0] % 2 == 0:
  k += 1
  A[0] //= 2
for i in range(1, N):
  a, b = L, A[i]
  while b != 0:
    a, b = b, a % b
  b = A[i] // a
  L *= b
  cnt = 0
  while A[i] % 2 == 0:
    cnt += 1
    A[i] //= 2
  if cnt != k:
    p = 1
    break
if p == 1:
  S = 0
else:
  S = M // L - M // (2 * L)
print(S)

Submission status: Accepted

Solution code:
from fractions import gcd
n,m = map(int,input().split())
lis = list(map(int,input().split()))
devide = set()
for num in lis:
    cnt = 0
    b = num
    while b % 2 == 0:
        b /= 2
        cnt += 1
    devide.add(cnt)
if len(devide) != 1:
    print(0)
    exit()
ansnum = lis[0]//2
for i in range(1,n):
    lis[i] = lis[i]//2
    ansnum = (ansnum * lis[i])//gcd(ansnum,lis[i])
print(m//(ansnum)-m//(ansnum*2))

Submission status: Accepted

Solution code:
from fractions import gcd
import sys
input = sys.stdin.readline

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

def main():
    LCM=1

    for i in List:
        LCM*=i//gcd(LCM,i)

    for i in List:
        if LCM//i%2==0:
            print(0)
            exit()

    print(int(M//(LCM*2)+M%(LCM*2)//LCM))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions import gcd
import sys
input = sys.stdin.readline

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

def main():
    LCM=1

    for i in List:
        LCM*=i//gcd(LCM,i)

    for i in List:
        if LCM//i%2==0:
            print(0)
            exit()

    print(int(M//(LCM*2)+M%(LCM*2)//LCM))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from functools import reduce
from fractions import gcd
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False

def ddprint(x):
  if DBG:
    print(x)

def fac2(x):
    r = 0
    while x%2==0:
        x //= 2
        r += 1
    return r

n,m = inm()
a = inl()
b = [x//2 for x in a]
r = fac2(a[0])
for i in range(1,n):
    if fac2(a[i]) != r:
        print(0)
        exit()
lc = reduce(lambda x,y: (x*y)//gcd(x,y), b, 1)
print(m//lc - m//(2*lc))

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd

def lcm(l):
    if len(l) == 1:
        return l[0]

    t = l[0]
    for i in range(1, len(l)):
        t = (t * l[i]) // gcd(t, l[i])
    return t

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

# process
ans = 0
lc = lcm(A)

if lc <= M:
    f = True
    for a in A:
        if lc//a%2 == 0:
            f = False
            break

    if f:
        ans = int(M/lc-1)//2+1

# output
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys
import random
import itertools
import math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt


def LI(): return list(map(int, input().split()))


def LF(): return list(map(float, input().split()))


def LI_(): return list(map(lambda x: int(x)-1, input().split()))


def II(): return int(input())


def IF(): return float(input())


def LS(): return list(map(list, input().split()))


def S(): return list(input().rstrip())


def IR(n): return [II() for _ in range(n)]


def LIR(n): return [LI() for _ in range(n)]


def FR(n): return [IF() for _ in range(n)]


def LFR(n): return [LI() for _ in range(n)]


def LIR_(n): return [LI_() for _ in range(n)]


def SR(n): return [S() for _ in range(n)]


def LSR(n): return [LS() for _ in range(n)]


mod = 1000000007
inf = 1e10
#solve


def solve():
    n, m = LI()
    a = LI()
    a0 = a[0]
    bi = 0
    while not (a0 & 1):
        bi += 1
        a0 >>= 1
    if not bi:
        print(0)
        return
    for ai in a[1:]:
        tmp = 0
        while not (ai & 1):
            tmp += 1
            ai = ai >> 1
        if tmp == bi:
            continue
        print(0)
        return

    def lcm(a):
        from fractions import gcd
        x = a[0]
        for i in range(1, len(a)):
            x = (x * a[i]) // gcd(x, a[i])
        return x
    lc = lcm(list(map(lambda x: x >> 1, set(a))))
    print((m + lc) // lc // 2)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
if sys.version_info.major >= 3 and sys.version_info.minor >= 5:
    from math import gcd
else:
    from fractions import gcd


N, M = map(int, input().split())
A = sorted(set(int(x) for x in input().split()))
if any(a % 2 > 0 for a in A):
    print(0)
    quit()
div_2 = []
for a in A:
    cnt = 0
    while a % 2 == 0:
        a //= 2
        cnt += 1
    div_2.append(cnt)
if len(set(div_2)) > 1:
    print(0)
    quit()

g = A[0]
for a in A:
    g = gcd(g, a)
lcm = 1
too_big = False

for a in A:
    if not too_big:
        lcm = lcm * a // gcd(lcm, a)
        if lcm > M * 2:
            too_big = True

if too_big:
    print(0)
elif lcm > M:
    print(1)
else:
    K = M // lcm
    ans = K + 1
    if lcm * K + lcm // 2 > M:
        ans -= 1
    print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
import numpy as np

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

pre = a[0]
for v in a[1:]:
    pre = pre * v // gcd(pre, v)

for v in a:
    if (pre // 2 - (v // 2)) % v:
        print(0)
        break
else:
    print((m + pre//2) // pre)

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
import fractions
import functools

K, M = (int(x) for x in input().split())

A = [int(x) for x in input().split()]

A = [x for x in set(A)]
A.sort()

#print("A = " + str(A))#

# A[0]を素因数分解して2で割り切れる回数を数える
div = 0
a_0 = A[0]
while a_0 % 2 == 0:
	a_0 /= 2
	div += 1

#print("count = " + str(div))#

# Aのすべての整数がA[0]と同じ回数2で割り切れるか調べる
for i in range(1, len(A)):
	div2 = 0
	a = A[i]
	while a % 2 == 0:
		a /= 2
		div2 += 1
	#print("A[" + str(i) + "] count = " + str(div2))#
	if div2 != div:
		print("0")
		sys.exit()

# Aのすべての整数の最小公倍数を計算する
A = [a // 2 for a in A]
lcm = functools.reduce(lambda a, b: a * b // fractions.gcd(a, b), A, 1)
#print("lcm = " + str(lcm))#

# 1以上M以下の最小公倍数の奇数倍の整数の個数を数える
print(-(-(M // lcm) // 2))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from functools import reduce
import numpy as np
sys.setrecursionlimit(10000000)
INF = 1<<32


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

    def gcd_base(a: int, b: int):
        while b:
            a, b = b, a%b
        return a

    def gcd(*numbers):
        return reduce(gcd_base, numbers)
    
    def lcm_base(a: int, b:int):
        return a*b // gcd_base(a,b)

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

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

    x = lcm(*a)
    t = x // 2
    y = div_of_2(x)

    if t > M or any([y != div_of_2(i) for i in a]):
        print(0)
        exit()

    ans = 1
    ans += (M-t)//x
    
    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:
#!/usr/bin/env python3
import sys
from functools import reduce
import numpy as np
sys.setrecursionlimit(10000000)
INF = 1<<32


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

    def gcd_base(a: int, b: int):
        while b:
            a, b = b, a%b
        return a

    def gcd(*numbers):
        return reduce(gcd_base, numbers)
    
    def lcm_base(a: int, b:int):
        return a*b // gcd_base(a,b)

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

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

    x = lcm(*a)
    t = x // 2
    y = div_of_2(a[0])

    if t > M or any([y != div_of_2(i) for i in a]):
        print(0)
        exit()

    ans = 1
    ans += (M-t)//x
    
    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:
#!/usr/bin/env python3
import sys
from functools import reduce
import numpy as np
sys.setrecursionlimit(10000000)
INF = 1<<32


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

    def gcd_base(a: int, b: int):
        while b:
            a, b = b, a%b
        return a

    def gcd(*numbers):
        return reduce(gcd_base, numbers)
    
    def lcm_base(a: int, b:int):
        return a*b // gcd_base(a,b)

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

    def num_of_2(x):
        c = 0
        while x%2 == 0:
            c += 1
            x//=2
        return c
    
    a0 = num_of_2(a[0])
    if any([num_of_2(i) != a0 for i in a]):
        print(0)
        exit()


    x = lcm(*a)
    t = x // 2

    # def div_of_2(x: int):
    #     c = 0
    #     while x%2 == 0:
    #         c += 1
    #     return c
    
    # y = div_of_2(t)

    # if t > M or any([y != div_of_2(i) for i in a]):
    if t > M:
        print(0)
        exit()

    ans = 1
    ans += (M-t)//x
    
    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:
import fractions
import functools
N, M = map(int, input().split())
A = [int(i) for i in input().split()]


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


def lcm(nums):
    return functools.reduce(multiple, nums)


lcm = lcm(A)
hlcm = lcm//2
# print(lcm, hlcm)

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

if hlcm > M:
    print(0)
else:
    print((M+hlcm)//hlcm//2)

Submission status: Accepted

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


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)


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

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

    t = f(A[0])
    for i in range(len(A)):
        if f(A[i]) != t:
            print(0)
            return 0
        A[i] >>= t
    M >>= t

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

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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


def least_common_multiple(iter):
    '''
    最小公倍数を返す
    '''
    lcm = lambda x, y: x*y//gcd(x, y)
    return reduce(lcm, iter)


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

div_num = 0
num = A[0]
flag = False
while num % 2 == 0:
    num = num // 2
    div_num += 1
for a in A:
    cnt = 0
    while a % 2 == 0:
        a = a // 2
        cnt += 1
    if div_num != cnt:
        flag = True

baisuu = M // l
if flag:
    print(0)
elif baisuu & 1:
    print((baisuu + 1)//2)
else:
    print(baisuu//2)

Submission status: Accepted

Solution code:
import fractions
from functools import reduce
N,M= map(int,input().split())
A=[int(x) for x in input().split()]
def lcmpair(a,b):
    return (a*b)// fractions.gcd(a,b)
def lcm(List):
    return reduce(lcmpair,List,1)
lcmB = lcm(A) //2

crit = 0
pena = 0
num = A[0]
while num%2 == 0:
    crit +=1
    num = num//2
count = 0
for i in A:
    count = 0
    while i%2 == 0 :
        count +=1
        i = i//2
    if count != crit:
        pena = 1

if lcmB > M:
    print(0)
elif pena ==1:
    print(0)
else:
    print(((M//lcmB)+1)//2)

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 = (int(x) for x in input().split())
a = list(map(int, input().split()))
 
lc = int(lcm_list(a) // 2)
 
tmp = 0
bol = 0
num = a[0]
while num % 2 == 0:
        num = num // 2
        tmp += 1
cnt = 0
for num in a:
    cnt = 0
    while num % 2 == 0:
        num = num // 2
        cnt += 1
    if cnt != tmp:
        bol = 1
 
if lc > m: print(0)
elif bol == 1: print(0)
else: print(int(((m / lc) + 1) // 2))

Submission status: Accepted

Solution code:
from fractions import*
n,m,*a=map(int,open(0).read().split())
s=1
d=set()
for i in a:
  i//=2
  s*=i//gcd(s,i)
  t=0
  while i%2<1:
    t+=1
    i//=2
  d|={t}
print((0--(m//s)//2)*(len(d)<2))

Submission status: Accepted

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

k = 0
while True:
    if a[0] % 2:
        break
    a[0] = a[0] // 2
    k += 1
base = 2 ** k

f = 0
for i in range(1,n):
    if a[i] % base:
        f = 1
        break
    a[i] = a[i] // base
    if a[i] % 2 == 0:
        f = 1
        break
if f:
    print(0)
else:
    LCM = a[0]
    for ai in a:
        LCM = LCM * ai // fractions.gcd(LCM, ai)
    LCM *= base // 2
    print(((m // LCM) + 1) // 2)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math
INF = 500000
mod = 10**9+7

N, M = map(int, input().split())
a = [int(x)//2 for x in input().split()]
m = 1
while a[0] % (m<<1) == 0:
    m <<= 1
for x in a[1:]:
    if x % m != 0:
        print(0)
        exit()
    elif x % (m<<1) == 0:
        print(0)
        exit()
gcd = lambda a, b: a if b == 0 else gcd(b, a%b)
lcm = 1
for x in a:
    lcm = lcm * x // gcd(x, lcm)
l, r = 0, 10**9
while l+1 < r:
    m = (l+r)//2
    if m * lcm > M:
        r = m
    else:
        l = m
if l % 2 == 0:
    if (l+1) * lcm <= M:
        print((l+2)//2)
    else:
        print(l//2)
else:
    print((l+2)//2)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,m = LI()
    a = LI()
    g = 2
    s = set()
    for c in a:
        t = fractions.gcd(g, c)
        g *= c // t
        i = 0
        while c % 2 == 0:
            i += 1
            c //= 2
        s.add(i)

    if len(s) > 1:
        return 0

    g //= 2
    t = (m // g + 1) // 2

    return t


print(main())

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

def read_int_n():
    return list(map(int, input().split()))

def read_float_n():
    return list(map(float, input().split()))

NM=read_int_n()
A=read_float_n()
A=list(set(A)) ##重複した要素を削除し、新たなリストを生成

##2で何回割れるかをcountする
def power2(n): ##参考：https://note.nkmk.me/python-prime-factorization/
  m=0
  while n % 2 == 0:
    m+=1
    n //= 2
  return m

#####2で奇数回割り切れる場合のみのflag
flag=0

a=[]
a_2=power2(A[0])

for i in range(len(A)): ###len(A) ###### A[0]をa=[]にappendする
  if power2(A[i])==a_2:
    a.append(int(A[i]*0.5)) ########## floatをintに直す
  else:
    flag=1

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

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)  
  
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN

if flag==0:
  lcm=lcm_list(a)
  amari=NM[1]/lcm #50までは15,30,45の3つ
  amari=(amari+1)//2 #3つのうち奇数を切り上げ
  ########roundは偶数への丸め(0.5は1になる):https://note.nkmk.me/python-round-decimal-quantize/
  ########四捨五入するならdecimalモジュールのquantize('.01')
  #Decimal(i).quantize(Decimal('0.01'), rounding=ROUND_HALF_UP)
  print(int(amari)) 
else:
  print(0)
#print(flag,amari,NM[1],lcm,a,A)

Submission status: Accepted

Solution code:
import math
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 = (int(x) for x in input().split())
a = list(map(int, input().split()))

lc = int(lcm_list(a) // 2)

tmp = 0
bol = 0
num = a[0]
while num % 2 == 0:
        num = num // 2
        tmp += 1
cnt = 0
for num in a:
    cnt = 0
    while num % 2 == 0:
        num = num // 2
        cnt += 1
    if cnt != tmp:
        bol = 1

if lc > m: print(0)
elif bol == 1: print(0)
else: print(int(((m / lc) + 1) // 2))

Submission status: Accepted

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

def gcd(x, y):
    '''
    最大公約数の計算
    '''
    if y == 0:
        return x
    return gcd(y, x % y)

def lcm(x, y):
    '''
    最小公倍数の計算
    '''
    return (x * y) // gcd(x, y)

nlcm = 1
for a in A:
    nlcm = lcm(a, nlcm)
judge = True
for a in A:
    half = nlcm // 2
    if half % a != a // 2:
        judge = False
        break
if judge:
    # 存在するパターン
    print((M+nlcm//2)//nlcm)
else:
    print(0)