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:
N, M = map(int, input().split())
a = list(map(int, input().split()))
for k in range(N):
  a[k] //= 2

foo = 1
while a[0]%2 == 0:
  foo *= 2
  a[0] //= 2
for k in range(1, N):
  if a[k] % foo == 0 and a[k]%(2*foo) !=0:
    a[k] //= foo
    continue
  else:
    print(0)
    exit()
ans = 0

for odd in [3, 5, 7, 11]:
  flag = False
  for k in range(N):
    if a[k]%odd == 0:
      a[k] //= odd
      flag = True
  if flag:
    foo *= odd
 
 
import math

lcm = a.pop()
for k in range(1, N):
  b = a.pop()
  lcm = lcm * b // math.gcd(lcm, b)
  if lcm* foo > M:
    print(0)
    exit()
lcm *= foo
ans = int((M / lcm -1)//2 + 1)
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a = list(map(int, input().split()))
for k in range(N):
  a[k] //= 2

foo = 1
while a[0]%2 == 0:
  foo *= 2
  a[0] //= 2
for k in range(1, N):
  if a[k] % foo == 0 and a[k]%(2*foo) !=0:
    a[k] //= foo
    continue
  else:
    print(0)
    exit()
ans = 0

for odd in [3, 5, 7, 11]:
  flag = False
  for k in range(N):
    if a[k]%odd == 0:
      a[k] //= odd
      flag = True
  if flag:
    foo *= odd
 
 
def euclid(a, b):
  while b:
    a, b = b, a%b
  return a

lcm = a.pop()
for k in range(1, N):
  b = a.pop()
  lcm = lcm * b // euclid(lcm, b)
  if lcm* foo > M:
    print(0)
    exit()
lcm *= foo
ans = int((M / lcm -1)//2 + 1)
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a = list(map(int, input().split()))
for k in range(N):
  a[k] //= 2

foo = 1
while a[0]%2 == 0:
  foo *= 2
  a[0] //= 2
for k in range(1, N):
  if a[k] % foo == 0 and a[k]%(2*foo) !=0:
    a[k] //= foo
    continue
  else:
    print(0)
    exit()
ans = 0

import math
lcm = a.pop()
for k in range(1, N):
  b = a.pop()
  lcm = lcm * b // math.gcd(lcm, b)
  if lcm* foo > M:
    print(0)
    exit()
lcm *= foo
ans = int((M / lcm -1)//2 + 1)
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from functools import reduce


def num_of_zeros(num):
    return (num ^ (num - 1)).bit_length() - 1


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


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


def main():
    input = sys.stdin.buffer.readline
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    if len(set(map(num_of_zeros, a))) != 1:
        print(0)
    else:
        lcm = lcm_list(list(map(lambda x: x // 2, a)))
        ub = 10 ** 9
        lb = 0
        while ub - lb > 1:
            mid = (ub + lb) // 2
            if lcm * (2 * mid + 1) <= m:
                lb = mid
            else:
                ub = mid
        if lcm <= m:
            lb += 1
        print(lb)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
A = list(map(int,input().split()))
for i,a in enumerate(A):
    A[i] //=2
from math import gcd,ceil
def lcm(a, b):
    return a*b//gcd(a,b)
b = 1

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

for i in range(n):
    a = A[i]
    b = lcm(a,b)


print(ceil((m//b)/2))

Submission status: Accepted

Solution code:
from math import gcd, ceil


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


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

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

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

ok = True
for aa in a:
    if (lcm_v//aa) % 2 != 1:
        ok = False
        break
ans = 0
if ok:
    ans = ((m//lcm_v)+1)//2
print(ans)

Submission status: Accepted

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

import math
def lcm(x, y):
    return (x * y) // math.gcd(x, y)
x=1
for i in range(n):
  x=lcm(x,a[i]//2)

power=[0]*n
for i in range(n):
  while a[i]%2==0:
    a[i]//=2
    power[i]+=1
    
if power.count(power[0])==n:  
  print((m+x)//(2*x))
else:
  print(0)

Submission status: Accepted

Solution code:
import math
from functools import reduce
n, m = map(int, input().split())
A = list(map(int, input().split()))

a0 = A[0]
cnt = 0
while a0%2 == 0:
    a0 //= 2
    cnt += 1

a = []
for aa in A:
    if cnt == 1:
        if aa%4 == 0:
            print(0)
            exit()
    else:
        if aa%(2**(cnt-1)) != 0 or aa%(2**cnt) != 0 or aa%(2**(cnt+1)) == 0:
            print(0)
            exit()
    a.append(aa//2)


def lcm_base(p, q):
    return (p * q) // math.gcd(p, q)


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


lcm = lcm_list(a)
print(m//lcm - m//(lcm*2))

Submission status: Accepted

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

def gcd(x, y):
  while(x % y != 0 and y % x != 0):
    if(x > y):
      x = x % y
    else:
      y = y % x
  if(x > y):
    return y
  else:
    return x
      
def lcm(x, y):
  return x * y // gcd(x, y)

def divide2(p):
  if(p % 2 == 1):
    return 0
  else:
    return divide2(p//2)+1

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

for i in range(1, N):
  if(divide2(A[0]) != divide2(A[i])):
    print(0)
    exit()
    
print((M-X)//(2*X) + 1)

Submission status: Accepted

Solution code:
from math import gcd
def lcm(a, b):
    return a * b // gcd(a, b)

def lcm_g(A):
    ret = 1
    for a in A:
        ret = lcm(ret, a)
    return ret

def is_hcm(x, A):
    for i in range(N):
        if x % A[i] != A[i] // 2:
            return False
    return True

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

l = lcm_g(A)
if is_hcm(l // 2, A):
    ans = (2 * M + l) // (2 * l)
else:
    ans = 0

print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc150/tasks/abc150_d
import math


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


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

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

tmp = A[0]
for i in range(1, n):
    tmp = lcm(tmp, A[i])

# print(tmp)
print(((m // tmp) + 1)//2)

Submission status: Accepted

Solution code:
from math import gcd
N, M = map(int, input().split())
A = [a//2 for a in map(int, input().split())]

lcm = 1
for a in A:
    lcm = lcm*a//gcd(lcm, a)
    if lcm > M:
        print(0)
        exit()

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

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

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:
# 参考 : https://at274.hatenablog.com/entry/2020/01/15/060000
from functools import reduce
import math


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


def lcm_list(numbers):  # リストを投げると全要素のlcmが返ってくる
    return reduce(lcm, numbers, 1)


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

# 最初、Aの要素は全て偶数。2で割ったものに置き換え
A = [a // 2 for a in A]

# 全ての要素について、２で割れる回数が同じでないと題意は満たせない
count_div_2 = None
for a in A:
    cnt = 0
    while a % 2 == 0:
        a //= 2
        cnt += 1
    # 1個目は無条件で保存
    if count_div_2 is None:
        count_div_2 = cnt
    # 2個目からチェック
    elif cnt != count_div_2:
        print(0)
        exit()

# my_lcm = Aの全要素の最小公倍数。　この奇数倍が題意を満たす。
# my_lcmがMを超えていたら1つも作れない
my_lcm = lcm_list(A)
if my_lcm > M:
    print(0)
    exit()

tmp = M // my_lcm
# my_lcmの1,2,...tmp倍まで使えるが、偶数は使えない
# tmp=1or2なら1個, 3or4なら2個, 5or6なら3個,...
ans = (tmp + 1) // 2
print(ans)

Submission status: Accepted

Solution code:
# 参考 : https://at274.hatenablog.com/entry/2020/01/15/060000
from functools import reduce
import math


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


def lcm_list(numbers):  # リストを投げると全要素のlcmが返ってくる
    return reduce(lcm, numbers, 1)


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

# 最初、Aの要素は全て偶数。2で割ったものに置き換え
A = [a // 2 for a in A]

# 全ての要素について、２で割れる回数が同じでないと題意は満たせない
count_div_2 = None
for a in A:
    cnt = 0
    while a % 2 == 0:
        a //= 2
        cnt += 1
    # 1個目は無条件で保存
    if count_div_2 is None:
        count_div_2 = cnt
    # 2個目からチェック
    elif cnt != count_div_2:
        print(0)
        exit()

# my_lcm = Aの全要素の最小公倍数。　この奇数倍が題意を満たす。
# my_lcmがMを超えていたら1つも作れない
my_lcm = lcm_list(A)
if my_lcm > M:
    print(0)
    exit()

tmp = M // my_lcm
# my_lcmの1,2,...M倍まで使えるが、偶数は使えない
# tmp=1or2なら1個, 3or4なら2個, 5or6なら3個,...
ans = (tmp + 1) // 2
print(ans)

Submission status: Accepted

Solution code:
# https://at274.hatenablog.com/entry/2020/01/15/060000
from functools import reduce
import math


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


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


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

# 最初、Aの要素は全て偶数
# 2で割ったものに置き換え
A = [a // 2 for a in A]

# 各要素について、2で割り切れる回数が等しいかチェック
# 全ての要素について、２で割れる回数が同じでないと題意は満たせない
count_div_2 = None
for a in A:
    cnt = 0
    while a % 2 == 0:
        a //= 2
        cnt += 1
    # 1個目は無条件で保存
    if count_div_2 is None:
        count_div_2 = cnt
    # 2個目からチェック
    elif cnt != count_div_2:
        print(0)
        exit()

# Aの全要素の最小公倍数
# my_lcmの既数倍が題意を満たす
# my_lcmがMを超えていたら一つも作れない
my_lcm = lcm_list(A)
if my_lcm > M:
    print(0)
    exit()

tmp = M // my_lcm
# tmp=1or2なら1個, 3or4なら2個, 5or6なら3個,...(偶数は使えない)
ans = (tmp + 1) // 2
print(ans)

Submission status: Accepted

Solution code:
import math
N, M = map(int, input().split())
B = tuple(int(a) // 2 for a in input().split())

x = B[0]
for i in range(1, N):
    x = (x * B[i]) // math.gcd(x, B[i])

for b in B:
    if (x // b) % 2 == 0:
        print(0)
        break
else:
    ans = (M // x) - (M // (2 * x))
    print(ans)

Submission status: Accepted

Solution code:
from math import gcd
N, M = map(int, input().split())
A = list(map(int, input().split()))
lcm = 1
for a in A:
    lcm = lcm * a // gcd(lcm, a)
    if lcm > M*2:
        print(0)
        exit()
for a in A:
    if lcm // a % 2 == 0:
        print(0)
        exit()
ans = M // (lcm//2) - M // lcm
print(ans)

Submission status: Accepted

Solution code:
import math
def LCM(a, b):
    g = math.gcd(a, b)
    return a * b // g

N, M = map(int, input().split())
A = list(map(int, input().split()))
A = list(set(A))
N = len(A)
a0 = A[0]
div = 1
while a0 % 2 == 0:
    div *= 2
    a0 //= 2

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

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

if N > 1:
    lcm = LCM(A[0], A[1])
    for i in range(2, N):
        lcm = LCM(lcm, A[i])

if N == 1:
    lcm = A[0]

ans = M // lcm
if ans % 2 == 1:
    print(ans // 2 + 1)
else:
    print(ans // 2)

Submission status: Accepted

Solution code:
from fractions import gcd

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

a = As[0]
k = 0
while a % 2 == 0:
  a //= 2
  k += 1
lst = [As[0]//2]

for i in range(1,N):
  j = 0
  a = As[i]
  while a % 2 == 0:
    a //= 2
    j += 1
  if k != j:
    print(0)
    exit()
  lst.append(As[i]//2)
  
lcm = lst[0]
for i in range(1,N):
  t = gcd(lcm, lst[i])
  lcm *= lst[i]//t
  if lcm > M:
    print(0)
    exit()
  
rlt = M //lcm
if rlt % 2 == 0:
  print(rlt//2)
else:
  print(rlt//2+1)

Submission status: Accepted

Solution code:
import 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 lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


def my_round(val, digit=0):
    p = 10 ** digit
    return (val * p * 2 + 1) // 2 / p


n, m = list(map(int, input().split()))
a_pr = [i // 2 for i in list(map(int, input().split()))]
lcm_ = lcm_list(a_pr)
res, div2 = 0, None
for ai in a_pr:
    cnt = 0
    while ai % 2 == 0:
        ai //= 2
        cnt += 1
    if div2 is None:
        div2 = cnt
    elif cnt != div2:
        print(0)
        exit()

print(int(my_round(m // lcm_ / 2)))

Submission status: Accepted

Solution code:
from math import gcd
def readinput():
    n,m=map(int,input().split())
    a=list(map(int,input().split()))
    return n,m,a

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

def main(n,m,a):
    #s=set(a)
    #print(s)
    x=a[0]//2
    for i in range(1,n):
        x=lcm(x,a[i]//2)
    #print(x)
    gusubai=False
    kisubai=False
    for i in range(n):
        if x%a[i]!=0:
            gusubai=True
        else:
            kisubai=True
    
    y=m//x
    #print(y,x,m)
    if gusubai and not kisubai:
        ans=y//2+y%2
    elif gusubai and kisubai:
        ans=0
    else:
        ans=y
    return ans

if __name__=='__main__':
    n,m,a=readinput()
    ans=main(n,m,a)
    print(ans)

Submission status: Accepted

Solution code:
from math import gcd
import sys

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

def count(x):
    res=0
    while True:
        if x%2==0:
            res+=1
            x//=2
        else:
            break
    return res

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

A.sort(reverse=True)

temp=A[0]
for i in range(1,n):
    if count(A[i])!=count(temp):
        print(0)
        sys.exit()
    else:
        temp=lcm(temp,A[i])

ans=m//(temp//2)-m//temp
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect

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

# """nを素因数分解"""
# """2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""
# def factorization(n):
#     arr = []
#     temp = n
#     for i in range(2, int(-(-n**0.5//1))+1):
#         if temp%i==0:
#             cnt=0
#             while temp%i==0:
#                 cnt+=1
#                 temp //= i
#             arr.append([i, cnt])
#
#     if temp!=1:
#         arr.append([temp, 1])
#
#     if arr==[]:
#         arr.append([n, 1])
#
#     return arr
#
# # 素因数分解に基づくlcm
# def fact_lcm(numbers):
#     d = defaultdict(int)
#     for a in numbers:
#         b = factorization(a)
#         for bb in b:
#             d[bb[0]] = max(d[bb[0]],bb[1])
#     return(dict(d))
#
# d = fact_lcm(a)
# c = 1
#
# for dd in d.items():
#     c *= dd[0]**dd[1]

# リストのlcm
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

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

c = lcm_list(a)

cc = c // 2

for aa in a:
    if cc % aa == 0:
        print(0)
        sys.exit()

print((M-cc) // c + 1)

Submission status: Accepted

Solution code:
import math
def lcm(a,b):
  return (a*b)//math.gcd(a,b)
def co(num):
  return format(num, 'b')[::-1].find('1')
N,M=map(int,input().split())
L=list(map(int,input().split()))
L2=[co(i) for i in L]
if len(set(L2))!=1:
  print(0)
  exit()
L=[i//2 for i in L]
s=L[0]
for i in range(N):
  s=lcm(s,L[i])
c=M//s
print((c+1)//2)

Submission status: Accepted

Solution code:
import sys
from math import gcd
from functools import reduce
import numpy as np
    
read = sys.stdin.read
readline = sys.stdin.buffer.readline
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:
from math import gcd
N, M = map(int, input().split())
A = list(map(int, input().split()))
A = [i // 2 for i in A]
lcd = 1
for a in A:
    lcd *= a // gcd(lcd, a)
for a in A:
    if lcd // a % 2 == 0:
        print(0)
        exit()
print((M//lcd+1)//2)

Submission status: Accepted

Solution code:

from math import gcd
from functools import reduce


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


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


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

p2_cnt = [count_2p(n) for n in X]
if all(p2_cnt[0] == p2_cnt[i] for i in range(N)):
    a = reduce(lcm, X)
    cnt = M // (a // 2)
    print(-(-cnt // 2))
else:
    print(0)

Submission status: Accepted

Solution code:
def solve():
    import math
    N,M = [int(i) for i in input().split()]
    A = list(map(int, input().split()))

    lcm = A[0]
    for i in range(1, N):
        lcm = lcm * A[i] // math.gcd(lcm, A[i])
    first = lcm // 2

    ans_exists = True
    for i in range(N):
        if first % A[i] == 0:
            ans_exists = False

    if ans_exists:
        ans = int((M-first) // lcm + 1)
        print(ans)
    else:
        print('0')

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

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

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

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

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

c2=count2(L[0])
LCM = 1

for i in L:
    if count2(i)!=c2:
        print(0)
        sys.exit()
    LCM = lcm(i//2,LCM)
    if LCM>m:
        print(0)
        sys.exit()
print(max(0,(m-LCM)//(2*LCM)+1))

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect
n,m=map(int,input().split())
a=list(map(int,input().split()))

def lcm(a,b):
    g=math.gcd(a,b)
    return b*(a//g)
l=a[0]//2
for i in range(n):
    r=a[i]//2
    l=lcm(l,r)
for i in range(n):
    if (l//(a[i]//2))%2==0:
        print(0)
        exit()
res=m//l
print((res+1)//2)

Submission status: Accepted

Solution code:
import math
from functools import reduce
n, m = input().split()
a = list(map(int, input().split()))
b =[0]*int(n)
for i in range(len(a)):
  b[i] = a[i]//2

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

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
c = 0

x = lcm_list(b)
for i in range(int(n)):
  if (x // b[i]) % 2 == 0:
    c = -1
    break
  else:
    continue
    
if c == -1:
  print(0)
else:
  print(math.floor(((int(m)/x)+1)/2))

Submission status: Accepted

Solution code:
from math import gcd
from functools import reduce

n,m=map(int,input().split())
lst=list(map(lambda x : int(x)//2,input().split()))
divi=0
x=lst[0]
while x%2==0:
    x//=2
    divi+=1

for i in range(1,n):
    divi2=0
    x=lst[i]
    while x%2==0:
        x//=2
        divi2+=1
    if divi!=divi2 :
        print(0)
        exit()

work=reduce(lambda x,y: x*y//gcd(x,y),lst)
print((m//work+1)//2)

Submission status: Accepted

Solution code:
from math import gcd

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

for i in range(n):
    lcm = lcm * A[i] // gcd(lcm, A[i])
    if lcm > m:
        print(0)
        exit()
        
for a in A:
    if lcm // a % 2 == 0:
        print(0)
        exit()

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

Submission status: Accepted

Solution code:
from math import gcd
from functools import reduce
import sys
input = sys.stdin.readline


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


def count_factor_2(num):
    count = 0
    while num % 2 == 0:
        num //= 2
        count += 1
    return count


def main():
    n, m = map(int, input().split())
    A = list(map(lambda x: x//2, set(map(int, input().split()))))

    check = len(set(map(count_factor_2, A)))
    if check != 1:
        print(0)
        return

    lcm_a = reduce(lcm, A)
    step = lcm_a * 2
    ans = (m + lcm_a) // step
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from math import gcd
from functools import reduce
import sys
input = sys.stdin.readline


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


def count_factor_2(num):
    count = 0
    while num % 2 == 0:
        num //= 2
        count += 1
    return count


def main():
    n, m = map(int, input().split())
    A = list(map(lambda x: int(x)//2, input().split()))

    check = len(set(map(count_factor_2, A)))
    if check != 1:
        print(0)
        return

    lcm_a = reduce(lcm, A)
    step = lcm_a * 2
    ans = (m + lcm_a) // step
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from math import gcd
def lcm(x,y):
    return x*y//gcd(x,y)
def cnt(x):
    i = 0
    while x%2 == 0:
        x = x//2
        i += 1
    return i 
n,m = map(int,input().split())
a = list(map(int,input().split()))
memo = cnt(a[0])
for i in range(n):
    if cnt(a[i]) != memo:
        print(0)
        quit()
    a[i] = a[i]//2

t = 1
for i in range(n):
    t = lcm(t,a[i])
print(m//t-m//(2*t))

Submission status: Accepted

Solution code:
from math import gcd

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

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

d = 1
a = A[0]
while a % 2 == 0:
    d *= 2
    a //= 2

if not all((a//d)%2 != 0 and a%d == 0 for a in A):
    print(0)
    exit()

A = [a//d for a in A]
g = 1
for a in A:
    g = g*a//gcd(g,a)

g *= d//2

x = M//g

print((x+1)//2)

Submission status: Accepted

Solution code:
import math
from functools import reduce

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

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

def lcm(target_list):
  return reduce(lcm_base, target_list)

A_gcd = reduce(math.gcd, A)
flg = True

for a in A:
  if a//A_gcd%2==0:
    flg = False
    break
    
if flg:
  min_x = int(lcm(A))//2
  ans = m//min_x - m//(2*min_x)
  print(ans)
else:
  print(0)

Submission status: Accepted

Solution code:
from math import gcd

n, m = (int(x) for x in input().split())
A = list(int(x) for x in input().split())
B = [a // 2 for a in set(A)]

lcm = 1
div2_count = -1
for b in B:
    lcm = lcm * b // gcd(lcm, b)
    if lcm > m:
        print(0)
        exit()
    count = 0
    while b % 2 == 0:
        b //= 2
        count += 1
    if div2_count == -1 or div2_count == count:
        div2_count = count
    else:
        print(0)
        exit()

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

Submission status: Accepted

Solution code:
from math import *

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

def lcm2(array):
    temp = 1
    for a in array:
        temp = lcm(temp, a)
    return temp

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

b = []
for a in A:
    cnt = 0
    while a:
        if not a%2:
            cnt += 1
            a = a // 2
        else:
            break
    b.append(cnt)

if b.count(cnt) != N:
    print(0)
    exit()

res = lcm2(A)

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

Submission status: Accepted

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

cnt = [0 for _ in range(N)]
for i in range(N):
  a = A[i]
  while a%2 == 0:
    a = a // 2
    cnt[i] += 1

if max(cnt) > min(cnt):
  print(0)
  exit(0)
C = max(cnt)

A = list(map(lambda x: x // pow(2,C), A))
def gcd(a,b):
  if a<b:
    a,b = b,a
  while a%b > 0:
    a,b = b,a%b
  return b

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

x = A[0]
for a in A[1:]:
  x = lcm(x,a)
x = x * pow(2,C-1)

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

Submission status: Accepted

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

cnt = [0 for _ in range(N)]
for i in range(N):
  a = A[i]
  while a%2 == 0:
    a = a // 2
    cnt[i] += 1

if max(cnt) > min(cnt):
  print(0)
  exit(0)
C = max(cnt)

A = list(map(lambda x: x // pow(2,C), A))
def gcd(a,b):
  if a<b:
    a,b = b,a
  while a%b > 0:
    a,b = b,a%b
  return b

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

x = A[0]
for a in A[1:]:
  x = lcm(x,a)
x = x * pow(2,C-1)

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

Submission status: Accepted

Solution code:
from collections import deque,defaultdict
def gcd(a,b):
    return b if not a%b else gcd(b,a%b)
def lcm(a,b):
    return (a*b)//gcd(a,b)
n,m=map(int, input().split())
A=[int(i) for i in input().split()]
tmp = A[0]
for i in range(1,n):
    tmp = lcm(tmp,A[i])
ans = m//tmp
lis = set()
for i in A:
    r = i
    k=0
    while(r%2==0):
        k+=1
        r//=2
    lis.add(k)
if(m//(tmp)*tmp+tmp//2<=m):
    ans += 1
if(len(lis)!=1):
    ans=0

print(ans)

Submission status: Accepted

Solution code:
import math
N,M= map(int, input().split())
a = list(map(int, input().split()))
A=[0]*N
#２で何回割れるか
for i in range(N):
    num=0
    while a[i]%2==0:
        num+=1
        a[i]=int(a[i]/2)
    A[i]=num

for i in range(N):
    if A[0]==A[i]:
        s=True
    else:
        s=False
        break
if s:
    M=M/(2**(A[i]-1))
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    def lcm(a, b):
        return a * b // gcd (a, b)
    ak=a[0]
    for i in range(N):
        ak=lcm(ak,a[i])
    #print(ak)
    if ak>M:
        print(0)
    else:
        print(math.ceil(int(M/ak)/2))
else:
    print(0)

Submission status: Accepted

Solution code:
import math

def lcm(a, b):
    return (a * b) // math.gcd(a, b)
def div2(n):
    return bin(n)[::-1].find("1")

n, m = map(int, input().split())
a = list(map(int, input().split()))
ans = a[0]
count = div2(a[0])
for i in range(1, len(a)):
    if count != div2(a[i]):
        print(0)
        exit()
    ans = lcm(ans, a[i])
ans //= 2
print((m // ans + 1) // 2)

Submission status: Accepted

Solution code:
import 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 div2_n(x):
    n = 0
    while x % 2 == 0:
      if x % 2 == 0:
          n += 1
          x >>= 1
    return n
  
n, m = map(int, input().split())
a = list(map(int, input().split()))

a2 = [i//2 for i in a]
n0 = div2_n(a2[0])
for i in range(1,n):
    if div2_n(a2[i]) != n0:
        print(0)
        exit()

a2_l = lcm(*a2)
print(m//a2_l - m//(a2_l*2))

Submission status: Accepted

Solution code:
import numpy as np
import sys

def main():
    N,M=map(int,input().split())
    A=list(map(int,input().split()))
    A_double=list(map(lambda x:x//2,A))

    mini_multi=int(np.lcm.reduce(A_double))

    res=M//mini_multi
    
    for i in A_double:
        if (mini_multi//i)%2==0:
            print(0)
            sys.exit()

    if res%2!=0:
        res+=1


    print(res//2)





if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
from math import gcd

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

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

rightmostbit = As[0] & -As[0]
for A in As[1:]:
    if rightmostbit != A & -A:
        print(0)
        exit() 


lcm_of_half_As = 1
for A in As:
    lcm_of_half_As = lcm(lcm_of_half_As, A //  2)
    if lcm_of_half_As > M:
        break

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

Submission status: Accepted

Solution code:
import sys
import numpy as np
def input(): return sys.stdin.readline().rstrip()

def kosuu(x):
    re = [0,0]
    while x % 2 == 0:
        x = x//2
        re[1]+=1
    re[0]=x
    return re

        
 
def main():
    n,m=map(int, input().split())
    a=list(map(int, input().split()))
    li = [kosuu(a[0])[0]]
    hantei = kosuu(a[0])[1]
    for i in a[1:]:
        hantei2 = kosuu(i)
        if hantei2[1] != hantei:
            print(0)
            break
        else:
            li.append(hantei2[0])
    else:
        lc = np.lcm.reduce(li)
        print(((m//(lc*2**(hantei-1)))+1)//2)
            


if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import math
n,m=map(int,input().split())
a=list(map(int,input().split()))
half_a=[ai//2 for ai in a]
# print(half_a)
lcm=half_a[0]
for i in range(n-1):
    a,b=lcm,half_a[i+1]
    lcm=a*b//math.gcd(a,b)
# print(lcm)
pow_cnt=0
tmp=half_a[0]
while tmp%2==0:
    pow_cnt+=1
    tmp=tmp//2
flag=True
for ai in half_a[1:]:
    if ai%(2**pow_cnt)!=0:
        flag=False
        break
    elif  ai%(2**(pow_cnt+1))==0:
        flag=False
        break
if flag:
    print(math.ceil(m//lcm/2))
else:
    print(0)

Submission status: Accepted

Solution code:
import math
import sys
from functools import reduce

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

for i in range(N):
  A[i] = A[i] // 2
  
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
  
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

C = lcm_list(A)
B = [0 for _ in range(N)]

for i in range(N):
  B[i] = C // A[i]
  if B[i] % 2 == 0:
    print(0)
    sys.exit()

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