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:
#!/usr/bin/env python3
import sys
from fractions import gcd

def solve(N: int, M: int, a: "List[int]"):
    koubaisu = a[0]
    for i in range(1, N):

        koubaisu = koubaisu * a[i] // gcd(koubaisu, a[i])

    for i in a:
        if koubaisu // i % 2 == 0:
            print(0)
            exit()

    print(M // koubaisu - M // (2*koubaisu))


    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int(next(tokens)) // 2 for _ in range(N)]  # type: "List[int]"
    solve(N, M, a)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np 
import sys

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

A = np.array(a)

while np.sum(A%2) == 0:
    A = A//2

if np.sum(A%2) != len(A):
    print("0")
    sys.exit()
    
tmp = 1##LCM

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

if tmp > M:
    print("0")

else:
    print((M//tmp+1)//2)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
from fractions import gcd
from functools import reduce

n,m,*alst = list(map(int,read().split()))
mm=2*m
def lcm(x,y):
  g=gcd(x,y)
  if x//g %2==0 or y//g%2==0:
    return 0
  g=x*y//g
  if g>mm:
    return 0
  return g
f=lambda x,y:0 if x==0 else lcm(x,y)
g=reduce(f,alst)
if g==0:
  print(0)
  quit()
else:
  res=(mm//g)
  print(res//2+res%2)

Submission status: Accepted

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

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


lcm = a[0]
for i in range(1, N):
    g= fractions.gcd(lcm, a[i])
    lcm = lcm * a[i] // g


g=a[0]
for i in range(N):
    g=fractions.gcd(g,a[i])

for i in range(N):
    if (a[i]//g)%2==0:
        lcm=0
        break    
    
    
ans=0
l=lcm//2
if l:
    ans=(M//l)-(M//(l+l))
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
from fractions import gcd
from functools import reduce

n,m,*alst = list(map(int,read().split()))
mm=2*m
def lcm(x,y):
  g=gcd(x,y)
  if x//g %2==0 or y//g%2==0:
    return 0
  g=x*y//g
  if g>mm:
    return 0
  return g
g=reduce(lcm,alst)
if g==0:
  print(0)
  quit()
else:
  res=(mm//g)
  print(res//2+res%2)

Submission status: Accepted

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

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

n,m = map(int,input().split())
a = list(map(int,input().split()))
g = a[0]

for i in range(1, n):
    g = g * a[i] // gcd(g, a[i])

for i in a:
    if g // 2 % i == 0:
        print(0)
        exit()

print(-(-(m * 2 // g)//2))

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
from fractions import gcd
from functools import reduce

n,m = map(int,readline().split())
alst = list(map(int,readline().split()))

def lcm(x,y):
  g=gcd(x,y)
  if x//g %2==0 or y//g%2==0:
    return 0
  return x*y//g
g=reduce(lcm,alst)
if g==0:
  print(0)
  quit()
else:
  res=(2*m//g)
  print(res//2+res%2)

Submission status: Accepted

Solution code:
import sys
N, M = map(int, input().split())
a = 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)

c = 1
s = 0
for i in range(N):
    a[i] //= 2
    if a[i] % 2 == 0 and s == 0:
        if i != 0:
            print(0)
            sys.exit()
        while a[i] % 2 == 0:
            a[i] //= 2
            s += 1
        c *= 2 ** s
    elif s != 0:
        if a[i] < 2 ** s or a[i] % (2 ** s) != 0 or (a[i] // (2 ** s)) % 2 == 0:
            print(0)
            sys.exit()   
    c = lcm(c, a[i])
    
print((M // c) // 2 + (M // c) % 2)

Submission status: Accepted

Solution code:
import sys
from fractions import gcd
inputs = sys.stdin.readlines()

n, m = map(int, inputs[0].split())
A = list(set(map(int, inputs[1].split())))

a = A[0]
for i in range(1, len(A)):
    z = gcd(a, A[i])
    x, y = a // z, A[i] // z
    if x % 2 == y % 2 == 1:
        a = x*y*z
    else:
        print(0)
        break
else:
    print(round(((m+1)/a)))

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
A = list(map(int,input().split()))
import numpy as np
import math
import fractions
import functools
A = np.array(A)
A = np.unique(A)
B = A.copy()
x=0
while np.all(B%2==0):
  B//=2
  x+=1
if np.any(B%2==0):
  print(0)
  exit()
  
A /= 2
n = A[0]
for a in A[1::]:
  n = n*a//fractions.gcd(n,a)
ans = math.ceil(M//n/2)
print(ans)

Submission status: Accepted

Solution code:
import sys
import fractions


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, readline().split()))
    a = [v >> 1 for v in list(map(int, readline().split()))]
    lcm = a[0]
    for v in a[1:]:
        gcd = fractions.gcd(lcm, v)
        if lcm // gcd % 2 == 0 or v // gcd % 2 == 0:
            print(0)
            exit()
        else:
            lcm = lcm * v // gcd
        if lcm > m:
            print(0)
            exit()
    print(m // lcm - m // (lcm * 2))


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import numpy as np
n,m=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
A=list(set(A))
AA=np.array(A)
cnt=0
 
from fractions import gcd
 
def lcm(a,b):
  return a*b//gcd(a,b)
 
while sum(AA%2)==0:
    cnt+=1
    AA//=2
if np.sum(AA%2)!=len(AA):
    ans=0
else:
  A=np.array(A)//2
  maxbai=A[-1]
  for i in range(len(A)):
    maxbai=lcm(A[-i-1],maxbai)
  x=m//maxbai
  ans=x//2+(x%2)
print(ans)

Submission status: Accepted

Solution code:
import fractions
s=list(map(int,input().split()))
t=[int(i)//2 for i in input().split()]
ans = t[0]
for i in range(1,s[0]):
  ans=(ans*t[i])//fractions.gcd(ans,t[i])
  if ans>10**10:
    print(0)
    exit()
for j in t:
  if (ans//j)%2==0:
    print(0)
    exit()
if ans<=s[1]:
  print(int((s[1]//ans+1)//2))
else:
  print(0)

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:
from fractions import gcd
from functools import reduce


def lcm(x, y):
    res = (x * y) // gcd(x, y)
    if 10 ** 9 < res:
        res = 0
    return res


def solve():
    N, M, *a = map(int, open(0).read().split())
    
    half_a = [ai // 2 for ai in a]
    half_lcm = reduce(lcm, half_a)
    
    for ai in half_a:
        if (half_lcm // ai) % 2 == 0:
            print(0)
            exit()
    
    if half_lcm == 0:
        ans = 0
    else:
        ans = (M // half_lcm) - (M // (2 * half_lcm))
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def gcd(a,b):
    while b:
        a,b=b,a%b
    return a
n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):
    a[i]//=2
x=a[0]
for j in range(30):
    if x%2==0:
        x//=2
    else:
        p=j
        break
for i in range(1,n):
    x=a[i]
    for j in range(30):
        if x%2==0:
            x//=2
        else:
            if p!=j:
                print(0)
                exit()
            break
ans = a[0]
for i in range(1, n):
    ans = ans * a[i] // gcd(ans, a[i])
    if ans>m:
        print(0)
        exit()
if (m//ans)%2==0:
    print(m//ans//2)
else:
    print(m//ans//2+1)

Submission status: Accepted

Solution code:

import sys
from fractions import gcd
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

INF = 10**18
N, M, *A = map(int, read().split())

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

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

Submission status: Accepted

Solution code:

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



def gcd(a,b):
    x = max([a,b])
    y = min([a,b])
    while y:
        x, y = y, x % y
    return x

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

# 全体の最大公約数, 最小で2
num = A[0]
for i in range(1,N):
    num = gcd(num, A[i])

# それぞれをnumで割った時の偶奇が異なれば、NG
odd = 0
even = 0
for i in range(N):
    if (A[i] / num)  % 2 == 0:
        even += 1
    else:
        odd += 1

if odd > 0 and even > 0:
    print(0)
else:
    # 半最小公倍数
    h = A[0] // 2
    # 最小公倍数
    n = A[0]
    for i in range(1,N):
        h = lcm(h, A[i]//2)
        n = lcm(n, A[i])
    if h == A[-1]:
        h *= 1.5

    if M < h:
        print(0)
    else:
        ans = 1
        M -= h
        ans += M // n
        print(ans)

Submission status: Accepted

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-

import pdb
import sys
import fractions
F = sys.stdin

N, M = list(map(int,F.readline().rstrip().split()))
a_list = list(map(int,F.readline().rstrip().split()))

num = 1
while a_list[0] % 2**(num + 1) == 0:
    num += 1
def lcm(a, b):
    return (a * b) // fractions.gcd(a, b)

lcm_before = 1
for a in a_list:
    if (a/(2**num)) % 2 != 1:
        print(0)
        sys.exit()

    lcm_before = lcm(lcm_before, a//2)



ans1 = M // lcm_before
ans = (ans1 + 1) // 2
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
n, m, *a = map(int, open(0).read().split())
lcm = a[0] // 2
for x in a:
	x //= 2
	g = gcd(lcm, x)
	if (lcm // g) % 2 != (x // g) % 2:
		print(0)
		exit()
	lcm = lcm * x // g
print(m // (2 * lcm) + (m % (2 * lcm) >= lcm))

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)

import fractions
from functools import reduce
def lcm_base(x, y):
    r = (x * y) // fractions.gcd(x, y)
    if r > 2*M:
        return 0
    return r

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


N,M = map(int, input().split())
xs = list(map(int, input().split()))
b = None
for x in xs:
    for i in range(30):
        if x%(2**i):
            break
    if b!=None:
        if b!=i:
            b = -1
            break
    b = i
if b==-1:
    print(0)
else:
    r = lcm_list(xs)
    if r//2 > M:
        print(0)
    elif r == 0:
        print(0)
    else:
        print((M-r//2)//r+1)

Submission status: Accepted

Solution code:
from fractions import gcd
def lcm(x, y): return x * y // gcd(x, y)

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

c = ha[0]
for d in ha[1:]:
    l = lcm(c, d)
    if not (l//c % 2 and l//d % 2): print(0); exit()
    c = l

print((m+c) // (c*2))

Submission status: Accepted

Solution code:
from fractions import gcd
n, m, *a = map(int, open(0).read().split())
lcm = a[0] // 2
for x in a:
	x //= 2
	g = gcd(lcm, x)
	if (lcm // g) % 2 != (x // g) % 2:
		print(0)
		exit()
	lcm = lcm * x // g
print((m // lcm + 1) // 2)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a = [int(x)//2 for x in input().split()]
import fractions
lmc=a[0]
for i in range(1,n):
    lmc=lmc*a[i]//fractions.gcd(lmc,a[i])
    if lmc>m:
        print("0")
        exit()
for i in range(n):
   if (lmc//a[i])%2==0:
      print("0")
      exit()
if (m//lmc)%2==0:
    print((m//lmc)//2)
else:
    print(((m//lmc)+1)//2)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
lists=list(map(int,input().split()))
uselist=[]
for some in lists:
    some=some//2
    uselist.append(some)

import fractions
import math
ans = uselist[0]
for i in range(1, n):
    ans = ans* uselist[i] // fractions.gcd(ans, uselist[i])

flags=True
for some in uselist:
    a=ans//some
    if a%2==0:
        flags=False
        break
if flags:
    p=math.floor(m/ans)
    if p%2==0:
      print(p//2)
    elif p%2!=0:
      print(p//2+1)
    
else:
    print(0)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

N, M = map(int, input().split())
a = [int(i) for i in input().split()]

# 最大公約数
def gcd(a, b) :
    if b > a : 
        a, b = b, a
    
    while b != 0 :
        a, b = b, a % b
    return a
    
# 最小公倍数
def lcm(a, b) :
    return a * b // gcd(a, b)

def solve() :
  f = a[0]
  if N >= 2 :
    for i in range(1, N) :
      f = lcm(f, a[i])
      if f > M * 2 :
        return 0
      
  cnt = 0
  while a[0] % 2 == 0 :
    a[0] //= 2
    cnt += 1
  
  for i in range(1, N) :
    tmp = 0
    while a[i] % 2 == 0 :
      a[i] //= 2
      tmp += 1
    if tmp != cnt :
      return 0
      
  return int(M / f + 0.5)
      
print(solve())

Submission status: Accepted

Solution code:
"""
最小公倍数
"""

import sys
sys.setrecursionlimit(4100000)

import math
import fractions
from functools import reduce

import logging

logging.basicConfig(level=logging.DEBUG)

logger = logging.getLogger(__name__)


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


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


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


def resolve():
    N, M = [int(x) for x in sys.stdin.readline().split()]
    a_list = [int(x) for x in sys.stdin.readline().split()]

    L = lcm_list(a_list)
    if any([(L // a) % 2 == 0 for a in a_list]):
        print(0)
        return
    else:
        X = L // 2

        y = M - X
        if y < 0:
            print(0)
        else:
            print(y // (2 * X) + 1)


if __name__ == "__main__":
    resolve()

# AtCoder Unit Test で自動生成できる, 最後のunittest.main は消す
# python -m unittest template/template.py で実行できる
# pypy3 -m unittest template/template.py で実行できる

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """2 50
6 10"""
        output = """2"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """3 100
14 22 40"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """5 1000000000
6 6 2 6 2"""
        output = """166666667"""
        self.assertIO(input, output)

Submission status: Accepted

Solution code:
def GCD(x,y):
    if y==0:
        return x
    return GCD(y,x%y)
def LCM(x,y):
    return x*y // GCD(x,y)
N, M = map(int,input().split())
A = list(map(int,input().split()))
ans = 1
for i in A:
    i //= 2
    ans = LCM(ans,i)
    if (ans//i)%2 == 0:
        print(0)
        exit()
    if ans > M:
        print(0)
        exit()
print(M//ans-M//(ans*2))

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd

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

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

l = reduce(lcm,b)

for i in range(n):
    if l//b[i]%2 == 0:
        print(0)
        break
else:
    print(m//l//2+m//l%2)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()

a = LIST()

tmp = a[0]//2
for i in range(1, N):
	if abs(a[0]//2-a[i]//2) % gcd(a[0], a[i]) != 0:
		print(0)
		sys.exit()
	tmp = a[i]//2*tmp//gcd(a[i]//2, tmp)

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

Submission status: Accepted

Solution code:
import sys

def LCM(a, b):
    m = a * b
    a, b = min(a, b), max(a, b)
    while a % b > 0:
        a, b = b, a % b
    return m // b

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = [int(a) for a in input().split()]
    div = 0
    d = A[0]
    while d % 2 == 0:
        div += 1
        d //= 2
    for i in range(1, N):
        d = A[i]
        di = 0
        while d % 2 == 0:
            di += 1
            d //= 2
        if di != div: 
            print(0)
            break
    else:
        if N > 2:
            lcm = LCM(A[0] // 2, A[1] // 2)
            for i in range(2, N):
                lcm = LCM(lcm, A[i] // 2)
        elif N == 2:
            lcm = LCM(A[0] // 2, A[1] // 2)
        else: lcm = A[0] // 2

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

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from fractions import gcd

import sys
input = sys.stdin.readline


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

    B = []

    ok = True
    a = A[0]
    c = 0
    while a%2 == 0:
        a //= 2
        c += 1
    
    p = 2**c

    for a in A:
        if a % p == 0 and a % (2*p) != 0:
            B.append(a//p)
        else:
            ok = False
            break
    if not ok:
        print(0)
    else:
        B.sort()
        g = 1
        for b in B:
            l = gcd(b, g)
            g = g*b//l
            if g > M:
                ok = False
                break
        if not ok:
            print(0)
        else:
            p = g*2**(c-1)
            ans = (M+p)//(2*p)
            print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()

a = LIST()

for i in range(1, N):
	if abs(a[0]//2-a[i]//2) % gcd(a[0], a[i]) != 0:
		print(0)
		sys.exit()
tmp = 1
for x in a:
	tmp = x//2*tmp//gcd(x//2, tmp)
print((M-tmp)//(tmp*2)+1)

Submission status: Accepted

Solution code:

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

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

def lcm(x, y):
    ans = (x * y) // gcd(x, y)
    return(ans)
l = 1
cnt = [0 for i in range(len(A))]
for i in range(len(A)):
    a = A[i]
    l = lcm(l, a)
    count = 0
    while True:
        if a % 2 == 0:
            a //= 2
            count += 1
        else:
            cnt[i] = count
            break
count = cnt[0]
flag = True
for i in range(len(A)):
    if cnt[i] != count:
        flag = False
        break
if flag:
    l = l // 2
    ans = M // l
    print((ans+1)//2)
else:
    print(0)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()

a = LIST()

# a = [x//2 for x in a]
# if a[0] % 2 == 0:  # 偶数の時
# 	for x in a:
# 		if x % 2 == 1:
# 			print(0)
# 			sys.exit(0)
# 	for x in a:
# 		if a[0] != x and abs(a[0]-x)%gcd(2*a[0], 2*x) != 0:
# 			print(0)
# 			sys.exit()

# 	tmp = 1
# 	for x in a:
# 		tmp = x*tmp//gcd(x, tmp)
# 	print((M-tmp)//(tmp*2)+1)

# else:
# 	for x in a:
# 		if x % 2 == 0:
# 			print(0)
# 			sys.exit(0)
# 	tmp = 1
# 	for x in a:  # 奇数の時
# 		tmp = x*tmp//gcd(x, tmp)
# 	print((M-tmp)//(tmp*2)+1)

for i in range(1, N):
	if abs(a[0]//2-a[i]//2) % gcd(a[0], a[i]) != 0:
		print(0)
		sys.exit()
tmp = 1
for x in a:
	tmp = x//2*tmp//gcd(x//2, tmp)
print((M-tmp)//(tmp*2)+1)

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

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

def lcm(n,m):
    return n*m // gcd(n,m)


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

lb = 1
for i in b:
    lb = lcm(lb,i)
    if lb > m:
        print(0)
        quit()

for i in b:
    if lb//i % 2 == 0:
        ans = 0
        break
else:
    ans = (m//lb + 1)//2
print(ans)

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

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

def lcm(n,m):
    return n*m // gcd(n,m)


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

lb = 1
for i in b:
    lb = lcm(lb,i)
    if lb > m:
        print(0)
        quit()

for i in b:
    if lb//i % 2 == 0:
        ans = 0
        break
else:
    if lb > m:
        ans = 0
    else:
        ans = (m//lb + 1)//2
print(ans)

Submission status: Accepted

Solution code:
import fractions
import math

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

z = a[0]
for x in a[1:]:
    g = fractions.gcd(z, x)
    l = z / g
    m = x / g

    if l % 2 == 1 and m % 2 == 1:
        z = l * m * g
    else:
        print(0)
        exit()

print(round((M + 1) / z))

Submission status: Accepted

Solution code:
from fractions import gcd
N, M = map(int, input().split())
a = list(map(int, input().split()))
k = a[0]
for i in range(1, N):
    k = (a[i]*k) // gcd(a[i], k)
    if k > M*2:
        print(0)
        exit(0)
    k = int(k)
ans = (M - (k // 2)) // k

if M >= (k // 2):
    flag = True
    for i in range(N):
        if (k // a[i]) % 2 == 0:
            print(0)
            exit(0)
    if flag:
        ans += 1

print(int(ans))

Submission status: Accepted

Solution code:
from fractions import gcd
#from math import gcd
N,M = map(int,input().split())
A = list(map(int,input().split()))
lcm = A[0]
lis = [[0] for _ in range(30)]
tmp = 0
while A[0]%2 == 0:
    A[0]//= 2
    tmp += 1
lis[tmp] = 1

for i in range(1,N):
    tmp = 0
    Ai = A[i]
    while Ai%2 == 0:
        Ai//= 2
        tmp += 1
    lis[tmp] = 1
    lcm = (lcm*A[i]) // gcd(lcm,A[i])
    if lcm > 2*M:
        print(0)
        exit()
jud = False
if lis.count(1) > 1:
    print(0)
    exit()


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

Submission status: Accepted

Solution code:
import sys #追加
sys.setrecursionlimit(10**9)
import time
s = time.time()

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

bl = [i//2 for i in al]
from fractions import gcd
ans = 1
for b in bl:
   if time.time() - s > 1.9:
      print(0)
      import sys
      sys.exit()
   ans = (ans * b) // gcd(ans, b)

for a in al:
   if time.time() - s > 1.9:
      print(0)
      import sys
      sys.exit()
   if ans % a == 0:
      print(0)
      import sys
      sys.exit()

def ceil(a, b):
   return a // b + (a % b > 0)

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

Submission status: Accepted

Solution code:
from fractions import gcd
def lcm(p,q):
    return p*q//gcd(p,q)

n,m = map(int, input().split())
a = list(map(int, input().split()))
x = 1
for i in range(n):
    a[i] = a[i]//2
    x = lcm(x,a[i])
    if x>m:
        print(0)
        exit()
for i in range(n):
    if (x//a[i])%2==0:
        print(0)
        exit()
p = m//x
if p%2==0:
    ans = p//2
else:
    ans = p//2 +1
print(ans)

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)

def invalid(a, b):
    if a > b:
        a, b = b, a
    return (b % a == 0 and ((b - a) // 2) % a != 0)

def main():
    N, M = map(int, input().split())
    A = list(set(map(int, input().split())))
    A.sort(reverse=True)
    if len(A) == 1:
        l = A[0]
    else:
        if invalid(A[0], A[1]):
            return 0
        l = lcm(A[0], A[1])
        for i in A[2:]:
            if invalid(l, i):
                return 0
            if l % i == 0:
                continue
            if l // 2 > M:
                return 0
            l = lcm(l, i)
    return (M + l // 2) // l

print(main())

Submission status: Accepted

Solution code:
# from functools import reduce
# N,M = map(int, input().split())
# a = list(map(int, input().split()))
# maxmax = 0.5
# List =list()
# for i in range(len(a)):
#     l = list()
#     while a[i]*maxmax<M:
#         l.append(a[i]*maxmax)
#         maxmax+=1
#     maxmax = 0.5
#     List.append(l)
# res = reduce(set.intersection, [set(l_) for l_ in List])
# print(len(res))
from fractions import gcd
 
N, M = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
a = set(a)
 
c = set()
l = 1
for ai in a:
    l *= ai // gcd(l, ai)
    if 0.5 * l > M:
        ans = 0
        break
    j = 0
    while True:
        if (ai >> j) % 2 == 0:
            j += 1
        else:
            c.add(j)
            break
    if len(c) > 1:
        ans = 0
        break
else:
    ans = (M + l // 2) // l
 
print(ans)

Submission status: Accepted

Solution code:
import fractions
from functools import reduce


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

hA = [a//2 for a in A]
lcm = 1
for a in hA:
    lcm = (lcm * a) // fractions.gcd(lcm, a)
    if lcm > m:
        print(0)
        break
else:
    for a in A:
        if lcm % a == 0:
            print(0)
            break
    else:
        if (m//lcm) % 2 == 0:
            print(m//lcm//2)
        else:
            print(m//lcm//2 + 1)

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()))
AA = list(map(lambda x: x//2, A))
def lcm(x, y):
    return x * y // gcd(x, y)
b0 = AA[0]&-AA[0]
for a in AA[1:]:
    if b0 != a&-a:
        print(0)
        break
else:
    a = reduce(lcm, AA)
    print(M//a - M//(2*a))

Submission status: Accepted

Solution code:
from fractions import gcd
def lcm(nums):
    ret = 1
    for i in nums:
        ret = ret*i//gcd(ret, i)
        if ret>m:
            return m+1
    return ret

n,m = map(int, input().split())
a = list(map(int, input().split()))
b = [i//2 for i in a]
g = lcm(b)
if any((g//i)%2==0 for i in b):
    ans = 0
else:
    ans = (m//g+1)//2
print(ans)

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()))
AA = list(map(lambda x: x//2, A))
def lcm(x, y):
    return x * y // gcd(x, y)
b0 = AA[0]&-AA[0]
for a in AA[1:]:
    if b0 != a&-a:
        print(0)
        break
else:
    a = reduce(lcm, AA)
    print(M//a - M//(2*a))

Submission status: Accepted

Solution code:
from fractions import gcd

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

c = set()
l = 1
for ai in a:
    l *= ai // gcd(l, ai)
    if 0.5 * l > M:
        ans = 0
        break
    j = 0
    while True:
        if (ai >> j) % 2 == 0:
            j += 1
        else:
            c.add(j)
            break
    if len(c) > 1:
        ans = 0
        break
else:
    ans = (M + l // 2) // l

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

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

[n, m] = get_ints()
a = get_ints()

def small_lcm(x, y):
    if x is None or y is None:
        return None
    ans = x * y // gcd(x, y)
    return ans if ans <= m else None

def count_div2(a):
    ans = 0
    while a % 2 == 0:
        ans += 1
        a //= 2
    return ans

cds = list(map(count_div2, a))
for v in cds:
    if v != cds[0]:
        print(0)
        exit(0)

l = reduce(small_lcm, map(lambda x: x // 2, a))
if l is None:
    print(0)
    exit(0)
t = m // l
print(t // 2 if t % 2 == 0 else t // 2 + 1)