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:
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()))
l = a[0] // 2
for i in range(n):
    a[i] //= 2
    l = lcm(l, a[i])
c = 0
while True:
    for i in range(n):
        if a[i] % 2 == 1:
            c += 1
        else:
            a[i] //= 2
    if not c == 0:
        break
print(((m // l) + 1) // 2 if c == n else 0)

Submission status: Accepted

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

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

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

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

M = M - (M % k)
b = M // k


if b % 2 == 0:
    r = int(b/2)
else:
    r = int((b + 1) / 2)

for a in A[1:]:
    if k // a % 2 == 0:
        r = 0
        break

print(r)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
import sys, heapq, bisect, math, itertools, string, queue, copy, time
from fractions import gcd
import numpy as np
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
EPS = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

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

def lcm(a, b):
    return a*b//gcd(a,b)
n, m = map(int, input().split())
a_array = np.array(list(map(int, input().split())))
c_array = np.copy(a_array)
while True:
    c_array //= 2
    if 1 in c_array%2:
        is_valid = not (0 in c_array%2)
        break
b_array = a_array//2
if is_valid:
    k = b_array[0]
    for i in range(n):
        k = lcm(k, b_array[i])
    ans = (m//k + 1)//2 
    print(ans)    
else:
    ans = 0
    print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from fractions import gcd

n, m = map(int, readline().split())
a = list(map(int, readline().split()))
for i in range(n):
    a[i] //= 2
lcm_memo = 1
for i in range(n):
    lcm_memo *= a[i] // gcd(lcm_memo, a[i])
    if lcm_memo > m:
        print(0)
        exit()
for i in range(n):
    if (lcm_memo // a[i]) % 2 == 0:
        print(0)
        exit()
print(1 + (m - lcm_memo) // (lcm_memo * 2))

Submission status: Accepted

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


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


def two(val):
    ret = 0
    tmp = val
    while True:
        if tmp != 0 and tmp % 2 == 0:
            ret += 1
            tmp = tmp // 2
        else:
            break
    return ret


n, m = map(int, input().split())
a_list = list(map(int, input().split()))
b_list = []

for item in a_list:
    b_list.append(item // 2)

cnt = -1

for item in b_list:
    ret = two(item)
    if cnt == -1:
        cnt = ret
    elif cnt != ret:
        print(0)
        exit()

val = b_list[0]

for item in b_list:
    val = lcm(item, val)

ret = m // val

tmp1 = ret // 2
tmp2 = ret % 2

print(tmp1 + tmp2)

Submission status: Accepted

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

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

def _lcm(a,b):
    return (a*b) // _gcd(a,b)

lcm = A[0] 
for ai in A[1:]:
    lcm = _lcm(lcm, ai)

ret = (M//lcm + 1)//2

for ai in A[1:]:
    if (lcm // ai) % 2 == 0:
        ret = 0
        break
print(ret)

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)
nm=list(map(int, input().split()))
a=list(map(int, input().split()))
n=nm[0]
m=nm[1]
b=0
c=a[0]
dnum=0
while c%2==0:
    dnum+=1
    c=c//2
for i in range(len(a)):
    c=a[i]
    dnum1=0
    while c%2==0:
        dnum1+=1
        c=c//2
    #print(dnum)
    if dnum1!=dnum:
        b=1
        break

#print(a)
if b==1:
    print(0)
else:
    for i in range(len(a)):
        a[i]=a[i]//2
    #print(a)
    amc=lcm_list(a)
    #print(amc)
    # version3.5にてgcdがfractionsからmathに移動した
    print(int((m+amc)/(2*amc)))

Submission status: Accepted

Solution code:
def main():
    from functools import reduce

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

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

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

    p = -1
    b = []
    for x in a:
        cnt = 0
        while x % 2 == 0:
            x //= 2
            cnt += 1
        if ~p and p != cnt:
            print(0)
            return
        p = cnt
        b.append(x)

    if p == 0:
        print(0)
        return

    t = pow(2, p - 1) * reduce(lcm, b)
    ans = (M // t) - (M // (t * 2))

    print(ans)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc150/tasks/abc150_d
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
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 [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

# GCD -- START --
def gcd(x,y):
  while y:
    x,y=y,x%y
  return x
# GCD --- END ---

# LCM -- START --
def lcm(x,y):
  return x*y//gcd(x,y)
# LCM --- END ---

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

def main():
  n,m=LI()
  _l=LI()
  l=[x//2 for x in _l]

  t=f(l[0])
  for i in range(n):
    b=l[i]
    if t!=f(b):
      return 0
    l[i]>>=t
  m>>=t

  _lcm=1
  for x in l:
    _lcm=lcm(_lcm,x)
    if _lcm>m:
      return 0

  # print(m,_lcm)
  m//=_lcm
  return (m+1)//2

# main()
print(main())

Submission status: Accepted

Solution code:
import copy
n,m = map(int,input().split())
a = set(list(map(int,input().split())))
a = list(a)
a_div2 = [0]*len(a)
a2 = copy.deepcopy(a)
# for i in range(len(a)):
#     if a[i] % 2 == 1:
#         print(0)
#         exit()
for i in range(len(a)):
    while a2[i] % 2 == 0:
        a2[i] //= 2
        a_div2[i] += 1
if len(set(a_div2)) != 1:
    print(0)
    exit()


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


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


if len(a) == 1:
    if m < a[0]//2:
        print(0)
    else:
        print((m-a[0]//2)//a[0] + 1)
else:
    cnt = 1
    for i in range(len(a)):
        a[i] //= 2
        cnt = lcm(cnt,a[i])
    if m < cnt:
        print(0)
    else:
        print((m-cnt)//(cnt*2)+1)

Submission status: Accepted

Solution code:
import copy
n,m = map(int,input().split())
a = set(list(map(int,input().split())))
a = list(a)
a_div2 = [0]*len(a)
a2 = copy.deepcopy(a)
for i in range(len(a)):
    if a[i] % 2 == 1:
        print(0)
        exit()
for i in range(len(a)):
    while a2[i] % 2 == 0:
        a2[i] //= 2
        a_div2[i] += 1
if len(set(a_div2)) != 1:
    print(0)
    exit()


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


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


if len(a) == 1:
    if m < a[0]//2:
        print(0)
    else:
        print((m-a[0]//2)//a[0] + 1)
else:
    cnt = 1
    for i in range(len(a)):
        a[i] //= 2
        cnt = lcm(cnt,a[i])
    if m < cnt:
        print(0)
    else:
        print((m-cnt)//(cnt*2)+1)

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=[0]*n
for i in range(n):
    b[i]=a[i]//2
flag=False
f=0
keta=0
buf=b[0]
while(buf%2==0):
    buf/=2
    keta+=1
for i in range(n):
    buf=b[i]
    tmp=0
    while(buf%2==0):
        buf/=2
        tmp+=1
    if(keta!=tmp):
        flag=True
x=1
if(b[0]%2==0):
    f=1
for i in range(n):
    x=lcm(x,b[i])
res=m//x+1
res//=2
#print(x)
if(flag):
    print(0)
else:
    print(res)

Submission status: Accepted

Solution code:
import fractions
import functools
N, M = map(int, input().split())
A = {int(i) // 2 for i in input().split()} 
#------------------------------------------------
#リスト内の最小公倍数
def lcm(a, b):
    return a * b // fractions.gcd(a, b)
all_lcm = functools.reduce(lcm, A)  
#------------------------------------------------
# Aの最小値が2で割り切れる回数
cnt = 0
min_a = min(A)
while True:
    if min_a % 2 != 0:
        break
    min_a //= 2
    cnt += 1
# Aのすべての数が2でcnt回割り切れる
cond1 = all({i % (2**cnt) == 0 for i in A})
# cnt回割った後、さらに2で割り切れる数は存在しない
cond2 = all({(i // (2**cnt)) % 2 != 0 for i in A})

if cond1 and cond2:
    ans = -((-(M // all_lcm)) // 2)
    print(ans)
else:
    print(0)

Submission status: Accepted

Solution code:
import fractions
N, M = map(int, input().split())
a = list(map(int, input().split()))
lcm = 1
for x in a:
    lcm = (lcm*x) // fractions.gcd(lcm, x)
ans = (M // lcm)
if M % lcm >= (lcm//2):
    ans += 1
x = a[0]
k = 0
while(x % 2 == 0):
    x = x // 2
    k += 1

for x in a[1:]:
    count = 0
    while(x % 2 == 0):
        x = x // 2
        count += 1
    if k == count:
        continue
    else:
        ans = 0


print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

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

if not all(f(b[0]) == f(b[i]) for i in range(n)):
    print(0)
    exit(0)

cnt = f(b[0])
g = b[0] >> cnt
for i in b:
    g = lcm(g, i >> cnt)

gg = g << cnt
print((m + gg) // (2 * gg))

Submission status: Accepted

Solution code:
import fractions


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


n, m = map(int, input().split())
v = list(map(int, input().split()))
num = 0
# print(v[0])
while (v[0] % 2 == 0):
    v[0] //= 2
    num += 1
# print(v[0])
ans = v[0]
for i in range(n - 1):
    if (v[i + 1] % (2 ** num) != 0 or v[i + 1] % (2 ** (num + 1)) == 0):
        ans = 2
        break
    # print(v[i+1])
    v[i+1] //= 2**num
    # print(v[i+1])
    ans = lcm(ans, v[i + 1])
# print(ans)
if (ans % 2 == 0):
    print(0)
    exit(0)
ans *= 2**(num-1)
print(((m//ans)+1)//2)

Submission status: Accepted

Solution code:
import fractions
"""最小公倍数"""
def lcm(a,b):
    f = fractions.gcd(a,b)
    return a*b//f

n,m = map(int,input().split())
A = list(map(int,input().split()))
l = A[0]
for a in A[1:]:
    l = lcm(l, a)

if n==1:
    if l%2!=0:
        print(0)
    else:
        if l/2>m:
            print(0)
        else:
            print(1 + int((m-l//2)/l))

else:
    flg = True
    for a in A:
        if (l//a)%2==0:
            flg = False
    if not flg:
        print(0)
    else:
        minx = l//2
        if minx>m:
            print(0)
        else:
            print(1 + int((m-minx)//l))

Submission status: Accepted

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

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def gcd(a,b):
        if a == 0:
            return b
        return gcd(b%a,a)
    n,m = LI()
    a = LI()
    s = set()
    for i in a:
        k = 0
        while not i&1:
            i >>= 1
            k += 1
        if not k:
            print(0)
            return
        s.add(k)
    if len(s) != 1:
        print(0)
        return
    a = [i >> 1 for i in a]
    l = a[0]
    for i in a[1:]:
        g = gcd(l,i)
        l = l*i//g
    print((m//l)-(m//(2*l)))
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

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

B = set([a & (-a) for a in A])
if len(B) > 1:
    print(0)
    exit()

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

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

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

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

Submission status: Accepted

Solution code:
from itertools import permutations
import sys

sys.setrecursionlimit(10 ** 6)
from bisect import *
from collections import *
from heapq import *

def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def SI(): return sys.stdin.readline()[:-1]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
int1 = lambda x: int(x) - 1
def MI1(): return map(int1, sys.stdin.readline().split())
def LI1(): return list(map(int1, sys.stdin.readline().split()))
p2D = lambda x: print(*x, sep="\n")
dij = [(1, 0), (0, 1), (-1, 0), (0, -1)]

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

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

def main():
    n,k=MI()
    aa=LI()
    aa2=[a//2 for a in aa]
    l=1
    for a2 in aa2:l=lcm(l,a2)
    for a2 in aa2:
        if l//a2%2==0:
            print(0)
            exit()
    print((k//l+1)//2)

main()

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]
debugmode = False

n, m = MAP()
a = LIST()
l = 1
num2 = 0
for i in range(n):
    if i == 0:
        ibin = bin(a[i])[2:]
        for j in reversed(range(len(ibin))):
            if ibin[j] == '1':
                num2 = len(ibin) - j - 1
                break
        l = a[i]
    else:
        tmp = int(bin(a[i] >> num2)[2:], 2) #2で割る
        if tmp * (2 ** num2) != a[i] or tmp % 2 == 0:
            print(0)
            exit()
        l = lcm(l, tmp)
    debug(l, num2)
debug(l)
ans = (2 * m // l + 1) // 2
print(ans)

Submission status: Accepted

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

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


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

Submission status: Accepted

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

stdin = sys.stdin

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

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

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

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

print(answer)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from fractions import gcd

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

# 全てを2で割る
for i in range(N):
    A[i] //= 2

for i in range(N):
    n *= A[i]//gcd(n, A[i])
    # 最小公倍数がMより大きくなる場合
    if n>M:
        flag = True
        break

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

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

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

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

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

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

main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a_li = list(map(int, input().split()))
# すべてのaを2で割る
a_li = [a // 2 for a in a_li]

from fractions import gcd

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

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

# a_lcm: aの最小公倍数, parity: すべてのaの偶奇性, cnt_div: すべてのaの2で割れる回数
a_lcm = 1
cnt_div = count_div_2(a_li[0])

# a_lcmを求める
flag = False
for a in a_li:
    a_lcm = lcm(a, a_lcm)
    # 偶奇が不一致、またはa_lcmがm以上の場合答えなし
    if cnt_div != count_div_2(a) or a_lcm > m:
        flag = True
        break

# 先程弾いた場合以外で答えを出す
if flag:
    ans = 0
else:
    ans = m // a_lcm
    ans = ans // 2 + ans % 2

print(ans)

Submission status: Accepted

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


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


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


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

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
from fractions import gcd                    # for Python3.4.3


def main():
    mod = 10000007                  # 10^9+7
    inf = float('inf')
    input = sys.stdin.readline      # 改行文字が残ることに注意
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def ii():  return int(input())
    def mi():  return map(int, input().rstrip().split())
    def lmi(): return list(map(int, input().rstrip().split()))
    def li():  return list(input().rstrip())
    
    
    def my_divide(num, count=0):
        if num % 2 == 0:
            return my_divide(num//2, count+1)
        else:
            return count
    
    def calc_lcm(x, y):
        return (x * y) // gcd(x, y)
        

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

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

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
from fractions import gcd
from functools import reduce
 
N,M,*A = map(int,read().split())
 
# 「奇数倍」に帰着
A = [x >> 1 for x in A]
 
def merge(a,b):
    g = gcd(a,b)
    a //= g; b //= g
    if a % 2 == 0:
        return 0
    if b % 2 == 0:
        return 0
    n = a * b * g
    if n > 10 ** 9:
        return 0
    return n
 
x = reduce(merge, A)
if x == 0:
    answer = 0
else:
    answer = (M//x) - (M//(x+x))
 
print(answer)

Submission status: Accepted

Solution code:
import sys

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

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

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

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

Submission status: Accepted

Solution code:
import sys
from fractions import gcd

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

# A が2で何回割れるか
N, M = lr()
A = lr()
A = [x // 2 for x in A]
cnt = 0
while all(x%2 == 0 for x in A):
    cnt += 1
    A = [x // 2 for x in A]

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

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

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

Submission status: Accepted

Solution code:
#python3

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

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

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

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

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

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

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

Submission status: Accepted

Solution code:
# define
a = [0] * int(1e5 + 100)
# functions
def _gcd(a, b):
    if a % b == 0 : return b
    if b % a == 0 : return a
    while a != 1 and b != 1:
        if a > b: a %= b
        else : b %= a
        if a % b == 0: return b
        if b % a == 0: return a
# main

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

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

flag = False
lcm = a[1]

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

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

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

Submission status: Accepted

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

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

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

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

def gcd(n, m):
    # 最大公約数
    a = max(n,m)
    b = min(n,m)
    while b:
        a, b = b, a % b
    return a

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

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

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

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

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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


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


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


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

Submission status: Accepted

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

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

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

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

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

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

res = M // min_X

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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


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


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


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

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

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