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: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal
from argparse import ArgumentParser

args=ArgumentParser()
args.add_argument('-loc', '--local', type=bool,default=False)
LOCAL=args.parse_args().local

def input(): 
    x=sys.stdin.readline(); 
    if x[-1]=="\n": 
        return x.rstrip() 
    return x
    
def printe(*x):_=print("## ",*x,file=sys.stderr) if LOCAL else 0
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def primes(n):
    a = Counter()
    while n % 2 == 0:
        a[2]+=1
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a[f]+=1
            n //= f
        else:
            f += 2
    if n != 1:
        a[n]+=1
    return a

def lcm(A,M,f=0):
    logm=math.log2(M)
    tc=Counter()
    for a in A:
        c=primes(a)
        for p in c:
            tc[p]=max(c[p],tc[p])
    tot=1
    tl=0
    for p,val in tc.items():
        tl+=p*math.log2(val)
        if tl>logm:
            return -1
        tot*=p**val
        
    if f:
        for a in A:
            if tot//a%2==0:
                return -1
        
    return tot

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, M = map(int, input().split())
    A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    m1=lcm(tuple(a//2 for a in A),M,1)
    if m1==-1:
        print(0)
        return
    m2=lcm(A,M)
    if m2==-1:
        print(1)
        return
    ans=1+(M-m1)//m2
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal
from argparse import ArgumentParser

args=ArgumentParser()
args.add_argument('-loc', '--local', type=bool,default=False)
LOCAL=args.parse_args().local

def input(): 
    x=sys.stdin.readline(); 
    if x[-1]=="\n": 
        return x.rstrip() 
    return x
    
def printe(*x):_=print("## ",*x,file=sys.stderr) if LOCAL else 0
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def primes(n):
    a = Counter()
    while n % 2 == 0:
        a[2]+=1
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a[f]+=1
            n //= f
        else:
            f += 2
    if n != 1:
        a[n]+=1
    return a

def lcm(A,M,f=0):
    tc=Counter()
    for a in A:
        c=primes(a)
        for p in c:
            tc[p]=max(c[p],tc[a])
    tot=1
    for p in tc:
        tot*=p**tc[p]
        if tot>M:
            return -1
    if f:
        for a in A:
            if tot//a%2==0:
                return -1
        
    return tot

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, M = map(int, input().split())
    A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    m1=lcm(tuple(a//2 for a in A),M,1)
    if m1==-1:
        print(0)
        return
    m2=lcm(A,M)
    if m2==-1:
        print(1)
        return
    ans=1+(M-m1)//m2
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal
from argparse import ArgumentParser

args=ArgumentParser()
args.add_argument('-loc', '--local', type=bool,default=False)
LOCAL=args.parse_args().local

def input(): 
    x=sys.stdin.readline(); 
    if x[-1]=="\n": 
        return x.rstrip() 
    return x
    
def printe(*x):_=print("## ",*x,file=sys.stderr) if LOCAL else 0
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def primes(n):
    a = Counter()
    while n % 2 == 0:
        a[2]+=1
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a[f]+=1
            n //= f
        else:
            f += 2
    if n != 1:
        a[n]+=1
    return a

def lcm(A,M):
    tc=Counter()
    for a in A:
        c=primes(a)
        for p in c:
            tc[p]=max(c[p],tc[a])
    tot=1
    for p in tc:
        tot*=p**tc[p]
        if tot>M:
            return -1
    return tot

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, M = map(int, input().split())
    A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    m1=lcm(tuple(a//2 for a in A),M)
    if m1==-1:
        print(0)
        return
    m2=lcm(A,M)
    if m2==-1:
        print(1)
        return
    ans=1+(M-m1)//m2
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from math import gcd

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

memo = {}

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

b = 1

for a in A:
    b = lcm(a//2, b)
    if b > M:
        break

ans = M // b
print(ans - ans // 2)

Submission status: Wrong Answer

Solution code:
from math import gcd

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

memo = {}

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

b = 1

for a in A:
    b = lcm(a//2, b)
    if b > M:
        break

ans = M // b
print(ans - ans // 2)

Submission status: Wrong Answer

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

memo = {}

def gcd(a, b):
    if b == 0:
        return a
    if (a, b) in memo:
        return memo[(a, b)]
    ans = gcd(b, a % b)
    memo[(a, b)] = ans
    return ans

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

b = 1

for a in A:
    b = lcm(a//2, b)
    if b > M:
        break

ans = M // b
print(ans - ans // 2)

Submission status: Wrong Answer

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

memo = {}

def gcm(a, b):
    if b == 0:
        return a
    if (a, b) in memo:
        return memo[(a, b)]
    ans = gcm(b, a % b)
    memo[(a, b)] = ans
    return ans

def lcm(a, b):
    a, b = max(a, b), min(a, b)
    return a * b // gcm(a, b)

b = 1

for a in A:
    b = lcm(a//2, b)

ans = M // b
print(ans - ans // 2)

Submission status: Wrong Answer

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

memo = {}

def gcm(a, b):
    if b == 0:
        return a
    if (a, b) in memo:
        return memo[(a, b)]
    ans = gcm(b, a % b)
    memo[(a, b)] = ans
    return ans

def lcm(a, b):
    a, b = max(a, b), min(a, b)
    return a * b // gcm(a, b)

b = 1

for a in A:
    b = lcm(a//2, b)
    if b > M:
        break

ans = M // b
print(ans - ans // 2)

Submission status: Wrong Answer

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

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

x = 1
for i in range(n):
    b =a[i] // 2
    x = x * b // gcd(x, b)
if x % 2 == 0:
    print(0)
    quit()
print((m - x) // (2 * x) + 1)

Submission status: Wrong Answer

Solution code:
def gcd(l, r):
    l, r = max(l, r), min(l, r)
    while True:
        l, r = r, l % r
        if r == 0:
            break
    return l

def lcm(l, r):
    k = gcd(l, r)
    return l * r // k

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

k = 2
for i in p:
    k = lcm(k, i)
r = k // 2
print(m // r - m // k)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


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


def read_float():
    return float(buff_readline())


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


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, A):
    b_lcm = 1


    d2 = set()
    for a in A:
        b = a // 2
        b_lcm = b_lcm//math.gcd(b_lcm, b) * b
        for i in range(100000000):
            if a % 2 == 0:
                a //= 2
            else:
                d2.add(i)
                break

    return -(-(M // b_lcm)//2) if len(d2) == 0 else 0





def main():
    N, M = read_int_n()
    A = read_int_n()
    print(slv(N, M, A))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


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


def read_float():
    return float(buff_readline())


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


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, A):
    b_lcm = 1
    for a in A:
        b = a // 2
        b_lcm = b_lcm//math.gcd(b_lcm, b) * b

    return -(-(M // b_lcm)//2)





def main():
    N, M = read_int_n()
    A = read_int_n()
    print(slv(N, M, A))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce

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

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

n, m = map(int, input().split())
A = list(map(int, input().split()))
halfA = [A[i] // 2 for i in range(n)]
checkA = halfA
cnt = 0
while checkA[0] % 2 == 0:
  checkA[0] //= 2
  cnt += 1

for i in range(1, n):
  ct = 0
  while checkA[i] % 2 == 0:
    checkA[i] //= 2
    ct += 1
  if cnt != ct:
    print(0)
    exit()

l = lcm_list(halfA)

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

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce

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

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

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

l = lcm_list(halfA)

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

Submission status: Wrong Answer

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


count = 0
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

def factorization(n):
  M = n
  k = 1
  faclist = []
  while(k**2 <= M):
    k += 1
    if M%k == 0:
      count = 0
      while M%k == 0:
        M //= k
        count += 1
      faclist.append((k, count))
  if M > 1:
    faclist.append((M, 1))
  return faclist
A = max(a)
li = factorization(A)
foo *= A
for odd in li:
  for k in range(N):
    count = 0
    while a[k]%odd[0] == 0 and count <= odd[1]:
      a[k] //= odd[0]
      count += 1

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

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

Submission status: Wrong Answer

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


count = 0
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

primenum = [2]
n = max(a)
sgn = [-1 for _ in range(int(n**0.5)+1)]
k = 3
while k**2 <= n:
  if sgn[k] == -1:
    primenum.append(k)
    add = k*k
    while k**2 <= n:
      sgn[k] = 1
      k += add
  k += 2
#prime_num が用意されているとき
counter = [0 for _ in range(n+2)]
faclist = []
def factorization(n):
  M = n
  for p in primenum:
    if p**2 > M:
      break
    else:
      if M%p == 0:
        count = 0
        while M%p == 0:
          M //= p
          count += 1
        if counter[p] == 0:
          faclist.append(p)
        counter[p] = max(counter[p], count) 
  if M > 1:
    if counter[M] == 0:
      faclist.append(M)
      counter[M] = 1
  return 0
for k in range(N):
  factorization(a[k])
lcm = 1
for f in faclist:
  lcm *= f**counter[f]
lcm *= foo
ans = int((M / lcm -1)//2 + 1)
print(ans)

Submission status: Wrong Answer

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 lb <= m:
            lb += 1
        print(lb)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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
        print(lb + 1)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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:
        gcd = lcm_list(list(map(lambda x: x // 2, a)))
        ub = 10 ** 14
        lb = 0
        while ub - lb > 1:
            mid = (ub + lb) // 2
            if gcd * (2 * mid + 1) <= m:
                lb = mid
            else:
                ub = mid
        if gcd * (2 * ub + 1) <= m:
            lb = ub
        print(lb + 1)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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:
        gcd = lcm_list(list(map(lambda x: x // 2, a)))
        ub = 10 ** 14
        lb = 0
        while ub - lb > 1:
            mid = (ub + lb) // 2
            if gcd * (2 * mid + 1) <= m:
                lb = mid
            else:
                ub = mid
        print(lb + 1)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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
for i in range(n):
    a = A[i]
    b = lcm(a,b)
    if b >m:print(0);exit()

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

Submission status: Wrong Answer

Solution code:
from math import gcd


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])

ans = m // lcm_v

if ans % 2 == 1:
    ans //= 2
    ans += 1
else:
    ans //= 2

print(ans)

Submission status: Wrong Answer

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)
  
print((m+x)//(2*x))

Submission status: Wrong Answer

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)
  
print((m//x+1)//2)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce
n, m = map(int, input().split())
a = list(map(int, input().split()))
a = [aa//2 for aa in a]


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: Wrong Answer

Solution code:
import math
from functools import reduce
n, m = map(int, input().split())
a = list(map(int, input().split()))
for aa in a:
    if aa%2 == 1:
        print(0)
        exit()


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)
x = m + lcm//2
print(x//lcm)

Submission status: Wrong Answer

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


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)
x = m - lcm//2
print(x//lcm+1)

Submission status: Wrong Answer

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


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)
x = m + lcm//2
print(x//lcm)

Submission status: Wrong Answer

Solution code:
import math

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

x=a[0]//2
y=a[0]

for s in range(1,n):
  x=(x*(a[s]//2))//math.gcd(x,a[s]//2)
  y=(y*a[s])//math.gcd(y,a[s])
  
if x>m:
  print(0)
else:
  print((m-x)//y+1)

Submission status: Wrong Answer

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)

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

print((M-X)//(2*X) + 1)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict


def factorization(n):
    """ n の素因数分解 / 基数と指数で取り出す

    Args:
        n (int): [description]

    Returns:
        [type]: [description]
    """

    arr = []
    tmp = n
    for i in range(2, int(-(-n**0.5 // 1)) + 1):  # sqrt(n) まで

        # i で割れるだけ割る、を繰り返す
        if tmp % i == 0:
            cnt = 0

            while tmp % i == 0:
                cnt += 1
                tmp //= i

            arr.append((i, cnt))  # 結果を追加

    if tmp != 1:
        arr.append((tmp, 1))  # まだ余っていれば追加しておく

    if arr == []:
        arr.append((n, 1))  # このブロック、必要か？

    return arr


def main():
    N, M = map(int, sys.stdin.readline().rstrip().split())
    A = [int(x) for x in sys.stdin.readline().rstrip().split()]

    A2 = [0] * N

    d = defaultdict(int)
    for i, a in enumerate(A):
        # print(factorization(a//2))
        for p, m in factorization(a//2):
            d[p] = max(d[p], m)

            # 2 の数は同じか？
            if p == 2:
                A2[i] = m

    if max(A2) != min(A2):
        print(0)
        return

    # print(d)

    # 最小公倍数を求める
    lcm = 1
    for p, m in d.items():
        lcm *= pow(p, m)

    ans = int((M / lcm - 1) / 2) + 1

    print(ans)


main()

Submission status: Wrong Answer

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


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


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

tmp = multi_lcm(A)

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

def factorization(n):
    """ n の素因数分解 / 基数と指数で取り出す

    Args:
        n (int): [description]

    Returns:
        [type]: [description]
    """

    arr = []
    tmp = n
    for i in range(2, int(-(-n**0.5 // 1)) + 1):  # sqrt(n) まで

        # i で割れるだけ割る、を繰り返す
        if tmp % i == 0:
            cnt = 0

            while tmp % i == 0:
                cnt += 1
                tmp //= i

            arr.append((i, cnt))  # 結果を追加

    if tmp != 1:
        arr.append((tmp, 1))  # まだ余っていれば追加しておく

    if arr == []:
        arr.append((n, 1))  # このブロック、必要か？

    return arr



def main():
    N, M = map(int, sys.stdin.readline().rstrip().split())
    A = [int(x) for x in sys.stdin.readline().rstrip().split()]

    d = defaultdict(int)
    
    for a in A:
        # print(factorization(a//2))
        for p, m in factorization(a//2):
            d[p] = max(d[p], m)

    if d[2] > 0:
        print(0)
        return

    # print(d)

    # 最小公倍数を求める
    lcm = 1
    for p, m in d.items():
        lcm *= pow(p,m)

    ans = int((M / lcm - 1) / 2) + 1

    print(ans)


main()

Submission status: Wrong Answer

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

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

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