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:
'''ika tako
小数が出てくるとややこしいが、 (A)bi=ai/2  として、 
X=bi*(2p+1)  としてしまえばいい。
これで、以下の2つを満たせばよいことがわかりやすくなる。
X  は全ての  bi  の公倍数
X  を  bi  で割った商は全て奇数
なので、とりあえず全ての  bi  の最小公倍数を求めて、
それが  bi  で割ると全て奇数となるか確認する。(B)
1つでも偶数となるものがあれば、達成不可能。
全て奇数なら、最小公倍数の奇数倍が全て条件を満たす。
2数  n,m  の最小公倍数は、最大公約数を  g  として  
n*m/g  で求められる。(D)
3数以上なら、これを繰り返し適用しつづければよい。
ただし  bi  が互いに素だと、最小公倍数は繰り返している内に
とてつもなく大きくなってしまう。途中で  M  以上になった時点で (C)
M  以下の半公倍数は不可能なので、0を出力して即終了する。
'''
from fractions import gcd#最大公約数を求める関数
 
def solve(n, m, aaa):
    lcm = 1
    for a in aaa:
        a //= 2#aは、上記biに相当する変数に変換(A)
        lcm *= a // gcd(lcm, a) 
        #最小公倍数を求める、上記n*m/g に相当(D)
        if lcm > m:#最小公倍数が上限mを上回ったら解なし (C)
            return 0
    for a in aaa:
        if int(lcm / a) == lcm / a:#割り切れたら等式成立
            return 0#上記bi  で割った時に、奇数にならないケース(B)
    return (m // lcm + 1) // 2

n, m = list(map(int, input().split()))
aaa = list(map(int, input().split()))
 
print(solve(n, m, aaa))

Submission status: Accepted

Solution code:
'''ika tako
小数が出てくるとややこしいが、 bi=ai/2  として、 
X=bi*(2p+1)  としてしまえばいい。
これで、以下の2つを満たせばよいことがわかりやすくなる。
X  は全ての  bi  の公倍数
X  を  bi  で割った商は全て奇数
なので、とりあえず全ての  bi  の最小公倍数を求めて、それが  
bi  で割ると全て奇数となるか確認する。
1つでも偶数となるものがあれば、達成不可能。
全て奇数なら、最小公倍数の奇数倍が全て条件を満たす。
2数  n,m  の最小公倍数は、最大公約数を  g  として  
n*m/g  で求められる。3数以上なら、これを繰り返し適用しつづければよい。
ただし  bi  が互いに素だと、最小公倍数は繰り返している内に
とてつもなく大きくなってしまう。途中で  M  以上になった時点で  
M  以下の半公倍数は不可能なので、0を出力して即終了する。
'''
from fractions import gcd
 
def solve(n, m, aaa):
    lcm = 1
    for a in aaa:
        a //= 2
        lcm *= a // gcd(lcm, a)
        if lcm > m:
            return 0
    for a in aaa:
        if int(lcm / a) == lcm / a:
            return 0
    return (m // lcm + 1) // 2

n, m = list(map(int, input().split()))
aaa = list(map(int, input().split()))
 
print(solve(n, m, aaa))

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()))
a = [x // 2 for x in a]

def solve(p, q):
    g = gcd(p, q)
    p //= g
    q //= g
    if (p - q) % 2 == 1:
        return 0
    return p * q * g

k = reduce(solve, a)
if k == 0:
    print(0)
else:
    print(M // k - M // (k * 2))

Submission status: Accepted

Solution code:
import fractions
def c2(a):
    ans = 0
    while True:
        q,r = divmod(a,2)
        if r==0:
             ans+=1
             a = q
        else:break
    return ans
gcd =  fractions.gcd
n,m= map(int,input().split())
A = list(map(lambda x:int(x)//2,input().split()))
A.sort()
ma = 0
cp = c2(A[0])
for i in range(n):
    if cp!=c2(A[i]):
        print(0)
        exit()
lcm = A[0]
for i in range(1,n):
    lcm = A[i]*lcm//gcd(A[i],lcm)

print((m//lcm +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 lcm(x, y):
    return x*y//gcd(x, y)


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

Submission status: Accepted

Solution code:
import fractions
N,M=map(int,input().split())
a=list(map(int,input().split()))
l=1
count=0
A=a[0]
ans=0
flag=1
while A%2==0:
    A=A//2
    count=count+1
for i in range(N):
    A=a[i]
    b=A//(2**count)
    if b==0 or b%2==0:
        flag=0
        break
    A=A//2
    l=l*A//fractions.gcd(l,A)
if flag==1:
    ans=M//l
    if ans%2==0:
        print(ans//2)
    else:
        print(ans//2+1)
else:
    print(0)

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 lcm(x,y):
  return x*y//gcd(x,y)
l=1
for i in a:
  l=lcm(l,i)
for i in a:
  if l//i%2==0:
    print(0)
    exit()
print((m//l+1)//2)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
a = [int(i) for i in input().split()]
a = sorted(list(set(a)))
from fractions import gcd
lc = a[0]
if n != 1:
  for num,i in enumerate(a[1:]):
    if lc == 0:
      break
    lc = lc * i // gcd(lc, i)
    if gcd(lc, i) == min(i,lc):
      for j in a[:num+1]:
        if (i/j)%2 == 0:
          lc = 0
          break 
if lc == 0:
  print(0)
else:
  print((m+lc//2)//lc)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
a = [int(i) for i in input().split()]
a = sorted(list(set(a)))
from fractions import gcd
lc = a[0]
if n != 1:
  for num,i in enumerate(a[1:]):
    if lc == 0:
      break
    lc = lc * i // gcd(lc, i)
    if gcd(lc, i) == min(i,lc):
      for j in a[:num+1]:
        if (i/j)%2 == 0:
          lc = 0
          break 
if lc == 0:
  print(0)
else:
  print((m+lc//2)//lc)

Submission status: Accepted

Solution code:
import numpy as np
from fractions import gcd
def lcm(a,b):
  return a*b//gcd(a,b)
N,M=map(int,input().split())
a=[i//2 for i in map(int,input().split())]
b=np.array(a)
cnt=0
while all(b%2==0):
  b//=2
if any(b%2==0):
  print(0)
  exit()
ans=1
for i in a:
  ans=lcm(ans,i)
print((M//ans-1)//2+1)

Submission status: Accepted

Solution code:
import numpy as np
from fractions import gcd
def lcm(a,b):
  return a*b//gcd(a,b)
N,M=map(int,input().split())
a=[i//2 for i in map(int,input().split())]
b=np.array(a)
cnt=0
while all(b%2==0):
  b//=2
if any(b%2==0):
  print(0)
  exit()
ans=1
for i in a:
  ans=lcm(ans,i)
print((M//ans+1)//2)

Submission status: Accepted

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

from fractions import gcd
def lcm(a,b):
    return a*b//gcd(a,b)
l=1

max2=0
min2=1000

for i in a:
    factor=(i^(i-1)).bit_length()
    max2=max(max2,factor)
    min2=min(min2,factor)
    l=l*i//2//gcd(l,i//2)
    if l>m:
        break

if l>m or min2!=max2:
    print(0)
else:
    ans=1 if l<=m else 0
    m-=l
    print(ans+max(0,m//(2*l)))

Submission status: Accepted

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

from fractions import gcd
def two(n):
    ans = 0
    while n%2==0:
        n //= 2
        ans += 1
    return ans

def multi_lcm(A):
    ans = A[0]
    for a in A:
        ans *= a//gcd(ans,a)
    return ans

def solve(N,M,A):
    ans = 0
    num_two = len(set(map(two,A)))
    if num_two != 1:
        return 0
    l = multi_lcm(A)
    ans = (M+l//2)//l
    return ans
print(solve(N,M,A))

Submission status: Accepted

Solution code:
def GCD(x, y):
    if y == 0:
        return x
    return GCD(y, x % y)


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

check = set()
for a in A:
    cnt = 0
    while a % 2 == 0:
        cnt += 1
        a //= 2
    check.add(cnt)

if len(check) > 1:
    print(0)
    exit()

LCM = 1
for a in A:
    gcd = GCD(LCM, a // 2)
    LCM = LCM * (a // 2) // gcd

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

Submission status: Accepted

Solution code:
import numpy as np
from fractions import gcd
def lcm(a,b):
  return a*b//gcd(a,b)
N,M=map(int,input().split())
a=[i//2 for i in map(int,input().split())]
b=np.array(a)
cnt=0
while all(b%2==0):
  b//=2
if any(b%2==0):
  print(0)
  exit()
ans=1
for i in a:
  ans=lcm(ans,i)
print((M//ans-1)//2+1)

Submission status: Accepted

Solution code:
def cnt_div2(n):
    cnt=0
    while n%2==0:
        n//=2
        cnt+=1
    return cnt
def gcd(a,b):
    a,b = max(a,b),min(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(lambda x:int(x)//2,input().split()))

if(all(cnt_div2(A[0]) == cnt_div2(a) for a in A)):
    if N==1:
        lcm_A = A[0]
    else:
        lcm_A = lcm(A[0],A[1])
        for a in A[2:]:
            lcm_A = lcm(lcm_A,a)
    print(int((M/lcm_A+1)//2))
else:
    print(0)

Submission status: Accepted

Solution code:
import fractions
import math

def divide_two(x):
    ans = 0
    while x > 0:
        if x % 2 == 0:
            ans += 1
            x = x // 2
        else:
            break
    return ans

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

if sum(flag) != flag[0] * n:
    ans = 0
else:
    # 最小公倍数求める
    lcm = a[0]
    for i in range(1, n):
        lcm = lcm * a[i] // fractions.gcd(lcm, a[i])

    ans = math.floor(m / lcm + 0.5)
print(ans)

Submission status: Accepted

Solution code:
from math import ceil
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()))

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

pre = None
for a in A:
  c = 0
  while a % 2 ==0:
    a //= 2 
    c += 1    
  if pre is None:    
    pre = c
  elif pre != c:
    print(0)
    exit()

if n == 1:
  ans = A[0]
else:
  ans = lcm(A[0],A[1])  
  for i in range(n-2):  
    if ans > m:
      print(0)
      exit()
    ans = lcm(ans,A[i+2])  

print(ceil((m//ans)/2))

Submission status: Accepted

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

l = 1
cnt = -1
for a in A:
    l = l*a//gcd(l,a)
    i = 0
    while a%2 == 0:
        a = a//2
        i += 1
    if cnt == -1:
        cnt = i
    elif cnt != i:
        print(0)
        exit(0)

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

Submission status: Accepted

Solution code:
import fractions


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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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

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

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

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

x = 1

for y in a:
    x = lcm(x, y//2)

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

max_n = (m-x)//(2*x)

print(max_n+1)

Submission status: Accepted

Solution code:
import fractions as f
n,m=map(int,input().split())
a=list(map(int,input().split()))
g=1
def check(n):
  cnt=0
  while n%2==0:
    n//=2
    cnt+=1
  return cnt
chk=check(a[0])
for i in a:
  if chk!=check(i):
    print(0)
    exit()
  else:
    chk=check(i)
for i in range(n):
  g=g*(a[i]//2)//(f.gcd(g,a[i]//2))
  if g>m:print(0);exit()
print(m//g-m//(2*g))

Submission status: Accepted

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

from math import floor
from fractions import gcd
from functools import reduce


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


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

lcm_b = reduce(lcm, b)

for n in b:
    if (lcm_b // n) % 2 == 0:
        print(0)
        exit()

n = floor((M / lcm_b - 1) / 2) + 1

print(n)

Submission status: Accepted

Solution code:
from functools import reduce
import sys

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


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

def gcd(a, b):
    import fractions
    return fractions.gcd(a, b)


def temp(a):
    return int(a * 0.5)

max_a = max(A)

i = 0
while True:
    num = int((i+0.5) * max_a)
    if num > M:
        print(0)
        sys.exit()

    found = True
    for a in A:
        if int(num - 0.5 * a) % a != 0:
            found = False
            break
    if found:
        ans = 1
        break
    i += 1

aa = reduce(lcm, A)

ans += (M - num) // aa

print(int(ans))

Submission status: Accepted

Solution code:
judge=0
N,M = map(int,input().split())
import fractions
a = list(map(int, input().split()))
ans = a[0]
for i in range(1, N):
    ans = ans * a[i] // fractions.gcd(ans, a[i])
for j in a:
    if (ans//j)%2==0:
        judge=1
        sss=0
        break
if judge==0 and M-ans//2 <0:
    sss=0
elif judge==0 and M-ans//2 >=0:
    sss=((M-ans//2)//ans)+1
print(sss)

Submission status: Accepted

Solution code:
import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt
from collections import deque
from collections import Counter
from math import ceil
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#######ここから天ぷら########
import fractions as math
from functools import reduce
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

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

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

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

B=[i//2 for i in A]
p=qq(B)
for i in A:
    i//=2
    if (p//i)%2==0:
        print(0)
        exit()
print(m//p - m//(p*2))

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

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

# リストを引数にして最小公倍数を表示
def lcm_of_list(a):
    return reduce(lcm, a)

def waruni(a):
    return a//2


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

L = lcm_of_list(b)

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

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

print(ans)

Submission status: Accepted

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

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

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

LCM=1
for i in A:
  i=i//2
  LCM=lcm(i,LCM)

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

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

Submission status: Accepted

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


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


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


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

lcm = 1
for i in a:
    i = i // 2
    lcm = LCM(i, lcm)

for i in a:
    i = i // 2
    if (lcm // i) % 2 == 0:
        print(0)
        sys.exit(0)

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

Submission status: Accepted

Solution code:
# 最大公約数
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a


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


N, M = map(int, input().split())
A = list(map(int, input().split()))
cnt = [0] * N
for i in range(N):
    a = A[i]
    while a % 2 == 0:
        a = a // 2
        cnt[i] += 1
if len(set(cnt)) != 1:
    print(0)
    exit()

x = A[0] // 2
for a in A[1:]:
    x = lcm(x, a // 2)
ans = M // x
print(ans - ans // 2)

Submission status: Accepted

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

num1 = a[0]
num2 = 0
while num1 % 2 == 0:
    num1 //= 2
    num2 += 1
gc = 2 ** num2

b = []
for i in a:
    if i % gc != 0 or (i // gc) % 2 == 0:
        print(0)
        exit()
    else:
        b.append(i // gc)

from fractions import gcd
lcm = 1
for i in b:
    lcm = (lcm * i) // gcd(lcm, i)

ans = m // (lcm * (gc // 2))
ans = (ans + 1) // 2
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
n,m = map(int,input().split())
a = list(map(lambda x: int(x)//2,input().split()))
def lcm(x,y):
    return x*y//gcd(x,y)
def f(x):
    cnt = 0
    while x%2 == 0:
        x //= 2
        cnt += 1
    return cnt
r = set([f(i) for i in a])
if len(r) != 1:
    print(0)
    exit()
T = 1
for i in range(n):
    T = lcm(T,a[i])
ans=-(-(m//T)//2)
c=T
print(ans)

Submission status: Accepted

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


lcm = 1
def p2(m):
    cnt = 0
    n = m
    while 1:
        if n%2 == 0:
            cnt += 1
            n = n//2
        else:
            break
    return cnt
pp = p2(aa[0])
for a in aa:
    lcm = a * lcm // gcd(a, lcm)
    if pp != p2(a):
        lcm = 10 **18
        break
tmp = lcm // 2
print((m // tmp + 1) // 2)

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd

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

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

def sub_by_2(n):
    cnt = 0
    while n % 2 == 0:
        n //= 2
        cnt += 1
    return cnt

lcm_2 = [sub_by_2(n // 2) for n in A]
if all(lcm_2[0] == v for v in lcm_2):
    num = reduce(lcm, [v // 2 for v in A])
    res = M // num
    print(res // 2 + res % 2)
else:
    print(0)

Submission status: Accepted

Solution code:
import fractions

# least common multiple
def lcm(a,b):
  f = fractions.gcd(a,b)
  return a*b // f

N,m = list(map(int, input().split()))
A = list(map(int,input().split()))
l = A[0]

# a -> a`
for i in range(N):
  if A[i]%2==1:
    print(0)
    exit(0)
  A[i] //= 2

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

  return res

t = F(A[0])
for i in range(N):
  if F(A[i]) != t:
    print(0)
    exit(0)
  A[i] >>= t # a[i] /= 2^t
m >>= t

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

m /= l
print(int((m+1) // 2))

Submission status: Accepted

Solution code:
from fractions import gcd

n, m = [int(x) for x in input().split()]
a_list = [int(x) for x in input().split()]
a_h_list = [a // 2 for a in a_list]

count = set()
for a_h in a_h_list:
    temp = bin(a_h)
    count.add(len(temp) - temp.rfind("1"))

if len(count) == 1:
    temp = 1
    for a_h in a_h_list:
        temp *= a_h // gcd(a_h, temp)
    ans = (m // temp + 1) // 2
else:
    ans = 0

print(ans)

Submission status: Accepted

Solution code:
import sys
from functools import reduce

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

n, m, *a = map(int, sys.stdin.read().split())

def main():
  for i in range(n):
    a[i] //= 2

  b = set()
  for x in a:
    cnt = 0
    while x % 2 == 0:
      x //= 2
      cnt += 1
    b.add(cnt)
  if len(b) == 2: print(0); return

  l = reduce(lcm, a, 1)
  res = (m // l + 1) // 2
  print(res)

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline

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

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

    N, M = (int(i) for i in input().split())
    A = [int(i)//2 for i in input().split()]
    cnt = [0]*(N)
    for i, a in enumerate(A):
        while a % 2 == 0:
            cnt[i] += 1
            a //= 2
    if any(cnt[0] != c for c in cnt):
        return print(0)
    L = 1
    for a in A:
        L = lcm(L, a)

    ans = 0
    mul = 1
    while L*mul <= M:
        ans += 1
        mul += 2
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,m = map(int, input().split())
    a = list(map(int, input().split()))
    if n == 1:
        b = a[0] // 2
        print((m-b)//(2*b) + 1)
        exit()
    def gcd(a, b):
        if b == 0:
            return a
        else:
            return gcd(b, a % b)
    
    def gcd_group(arr):
        g = gcd(arr[0], arr[1])
        for i in range(2, len(arr)):
            g = gcd(g, arr[i])
        return g
    
    def lcm(a, b):
        g = gcd(a, b)
        return (a*b)//g
    
    def lcm_group(arr):
        l = lcm(arr[0], arr[1])
        for i in range(2, len(arr)):
            l = lcm(l, arr[i])
        return l
    b = lcm_group(a)
    for i in a:
        if (b//i) % 2 == 0:
            print(0)
            exit()

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions import gcd

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

g = a[0]
    
x = a[0]
for i in range(1,nn):
    t = gcd(x,a[i])
    x *= a[i]
    x //= t
    
fl = 1
ff = x//2
for i in range(nn):
    if ff % a[i] != a[i] // 2:
        fl = 0
        
if fl == 1:
    xx = (m-ff) // x + 1
else:
    xx = 0
    
print(xx)

Submission status: Accepted

Solution code:
"""
import random
import functools
import copy
import bisect
import array
import re
import collections
import heapq
import fractions
import itertools
import string
import math
from operator import itemgetter as ig
from bisect import bisect_left, bisect_right, insort_left, insort_right
from itertools import permutations, combinations, product, accumulate, groupby
from heapq import heappush, heappop
from collections import deque, defaultdict, Counter
import sys
sys.setrecursionlimit(10 ** 7)
# import numpy as np

inf = 10 ** 20
INF = float("INF")
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]
ddn9 = ddn + [(0, 0)]
'''for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:'''
"""
from collections import Counter
import sys
sys.setrecursionlimit(10 ** 7)


def wi(): return list(map(int, sys.stdin.readline().split()))
# WideIntPoint


def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]


def ws(): return sys.stdin.readline().split()


def si(): return int(sys.stdin.readline())  # SingleInt


def ss(): return input()


def hi(n): return [si() for _ in range(n)]


def hs(n): return [ss() for _ in range(n)]  # HeightString


def s_list(): return list(input())


def mi(n): return [wi() for _ in range(n)]  # MatrixInt


def mip(n): return [wip() for _ in range(n)]


def ms(n): return [ws() for _ in range(n)]


def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[
    0]] for _ in range(n)]  # NumberGrid


def grid(n): return [s_list() for _ in range(n)]


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


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


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


def main():
    N, M = wi()
    a = wi()

    for i in range(len(a)):
        if a[i] % 2 != 0:
            print('0')
            sys.exit()
        else:
            a[i] //= 2

    t = f(a[0])
    for i in range(N):
        if f(a[i]) != t:
            print(0)
            sys.exit()
        else:
            a[i] //= 2**t
    M //= 2**t

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

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


if __name__ == '__main__':
    main()

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()))
h=list(map(lambda x:x//2,a))
l=1
for i in range(n):
    l=lcm(l,h[i])
for i in range(n):
    if (l//h[i])%2==0:
        print(0)
        exit()
print((m//l+1)//2)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from fractions import gcd

    n, m = list(map(int, readline().split()))
    a = list(map(int, readline().split()))
    cnt = [0] * n

    for i, elem in enumerate(a):
        x = elem
        c = 0
        while x % 2 == 0:
            x //= 2
            c += 1
        cnt[i] = c

    ans = 0

    if len(set(cnt)) == 1:
        lcm = a[0]
        for elem in a[1:]:
            lcm = (lcm * elem) // gcd(lcm, elem)
        ans = (m + (lcm // 2)) // lcm

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

b = list(map(lambda x: format(x, 'b')[::-1].find('1'), a))
if len(set(b)) != 1:
    print(0)
else:
    c = list(map(lambda x: x//2, a))
    t = reduce(lambda x, y: x*y//gcd(x, y), c)
    print(ceil((m//t)/2))

Submission status: Accepted

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

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

time = 0

def myfunc(x):
  cnt = 0
  while True:
    if x%2!=0:break
    x = x//2
    cnt += 1
  return cnt

f0 = myfunc(an[0])

for a in an[1:]:
  if myfunc(a) != f0:
    print(0)
    sys.exit()

lcm = reduce(lambda x, y: (x*y)//gcd(x,y),an)
if lcm > M:
  print(0)
  sys.exit()
print((M//lcm +1)//2)

Submission status: Accepted

Solution code:
from fractions import gcd

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

def solve(N, M, A):
    while A[0] % 2 == 0:
        for idx, a in enumerate(A):
            if a % 2 != 0:
                return 0
            A[idx] //= 2
        M //= 2

    for a in A:
        if a % 2 == 0:
            return 0

    cur_lcm = 1
    for a in A:
        cur_lcm = lcm(cur_lcm, a)
        if M < cur_lcm:
            return 0
    return (M // cur_lcm + 1) // 2

if __name__ == '__main__':
    N, M = map(int, input().split())
    A = list((map(int, input().split())))
    A = [a // 2 for a in A]
    print(solve(N, M, A))

Submission status: Accepted

Solution code:
import math
import collections
import sys

input = sys.stdin.readline
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]

n,m=MI()
A=LI()
def num2(x):
    ans=0
    while x%2==0:
        x=x//2
        ans+=1
    return ans
mod=2**(num2(A[0]))
for i in range(1,n):
    if A[i]%mod!=0:
        print(0)
        sys.exit()
    if A[i]%mod==0 and (A[i]//mod)%2==0:
        print(0)
        sys.exit()
#print(A)
for i in range(n):
    A[i]//=2
#print(A)

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

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

L=A[0]   
for i in range(1,n):
    L=lcm(L,A[i])
#print(L)
if L>m:
    an=0
else:
    an=int(((m/L)-1)/2)+1
print(an)

Submission status: Accepted

Solution code:
from sys import setrecursionlimit, exit
setrecursionlimit(1000000000)

from heapq import heapify, heappush, heappop, heappushpop, heapreplace
from bisect import bisect_left, bisect_right

from math import atan, degrees

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

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

for i in range(1, n):
    t2 = 0
    while a[i] % 2 == 0:
        a[i] //= 2
        t2 += 1
    if t2 != t:
        print(0)
        exit()

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

m >>= t
l = 1
for i in a:
    l = lcm(l, i)
    if l > m:
        print(0)
        exit()
print((m // l + 1) // 2)

Submission status: Accepted

Solution code:
from sys import setrecursionlimit, exit

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

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

for i in range(1, n):
    t2 = 0
    while a[i] % 2 == 0:
        a[i] //= 2
        t2 += 1
    if t2 != t:
        print(0)
        exit()

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

m >>= t
l = 1
for i in a:
    l = lcm(l, i)
    if l > m:
        print(0)
        exit()
print((m // l + 1) // 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())
L = list(map(int,input().split()))

# ループを回しながら最小公倍数を計算していく
# 与えられたN個の偶数はすべて２で割っていく
leastCommonMultiple = L[0] // 2
for i in range(N):
    L[i] //= 2
    leastCommonMultiple = lcm(leastCommonMultiple, L[i])

# フラグ
c = 0

# Lに格納されているＮ個の数に含まれる素因数２の数が同じかどうかチェックする
while True:

    for i in range(N):
        # ２で割り切れない場合
        # L[i]に含まれている数すべてが２で割り切れないならＯＫ
        if L[i] % 2 == 1:
            c += 1
        # ２で割り切れるなら、２で割った数で上書き
        else:
            L[i] //= 2

    if not c == 0:
        break


if c == N:
    print( ((M // leastCommonMultiple) + 1) // 2 )
else:
    print(0)

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 = [int(i) for i in input().split()]

a = 0
b = A[0]
while b % 2 == 0:
  a += 1
  b = b//2
  
for i in range(1,N):
  if A[i] % (2**a) != 0 or A[i] % (2**(a+1)) == 0:
    print(0)
    exit()

c = A[0]
for i in range(N-1):
  c = lcm(c,A[i+1])

print((M+c//2)//c)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc150/tasks/abc150_d
# 半公倍数Xとは、X=a_k (p_k + 0.5) for any k を満たす数字である(p_kは負はない整数)
# 2を掛ければ、2X=a_k P_k where P_k=2p_k+1 となる。2Xは数列Aの公倍数と解釈できる。
# よってこの問題は、a_k (k=1...N)の公倍数2X は 0<=X<=Mを満たす範囲にいくつ存在するか？という風に読み替えられる。
# 数列Aの最小公倍数を2lcmと定義すると、答えの候補はlcmの倍数であるところまで絞り込めた。
# これで答えの候補を最小公倍数の半分、lcmの倍数であるところまで絞り込めた。

# ところでP_kは必ず奇数でなければ行けないのだから,Xとa_kは同じ回数2で割り切れなければ行けない。
# これを満たすXは,lcmがP_kと同じ回数2で割り切れる かつ lcmの奇数倍の数である。

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from fractions import gcd


def lcm(a, b):
    # 最小公倍数 #単位元は1
    g = gcd(a, b)
    return a // g * b


N, M = read_ints()
A = read_ints()
X = 1
for a in A:
    X = lcm(X, a)
X = X // 2

# すべてのa//2 はX(lcmと同じ回数2で割り切れないければ行けない)
lcm = X
n_div = 0
while lcm & 1 == 0:
    lcm //= 2
    n_div += 1

for a in A:
    if n_div != 0 and (a // 2) % (pow(2, n_div)):
        print(0)  # 割り切れなかった時点でそのような半公倍数は存在しない
        exit()


print((M // X + 1) // 2)  # 奇数倍のlcmの個数 つまりすべて-偶数の分