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:
import sys
# import fractions
import math
from functools import reduce
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
stdin = sys.stdin

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

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

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

i_i = lambda: int(i_s())
i_l = lambda: list(map(int, stdin.readline().split()))
i_s = lambda: stdin.readline().rstrip()

N, M = i_l()
a = i_l()
half_lcm = lcm_list(a) // 2

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

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

Submission status: Accepted

Solution code:
import fractions


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

lcm=A[0]
for i in range(1,n):
    lcm=lcm*A[i]//fractions.gcd(lcm,A[i])

if any([i for i in range(n) if lcm%(A[i]*2)==0]):
    print(0);exit()

ans=m//(2*lcm)
print(ans if (m//lcm)%2==0 else ans+1)

Submission status: Accepted

Solution code:
import fractions


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

lcm=A[0]
for i in range(1,n):
    lcm=lcm*A[i]//fractions.gcd(lcm,A[i])
    if lcm>m:
        print(0);exit()

if any([i for i in range(n) if lcm%(A[i]*2)==0]):
    print(0);exit()

ans=m//(2*lcm)
print(ans if (m//lcm)%2==0 else ans+1)

Submission status: Accepted

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

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

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)

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

Submission status: Accepted

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

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

N, M = map(int, raw_input().split())
a = map(int, raw_input().split())

lcm = 1
for i in range(N):
    lcm = lcm_func(lcm, a[i])

for i in range(N):
    if lcm/a[i] %2 == 0:
        print 0
        exit()

lcm2 = lcm/2

ans = ((M/lcm2)+1)/2

print ans

Submission status: Accepted

Solution code:
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)
l=a[0]//2
ll=a[0]
for i in range(1,n):
  if a[i]%2:odd=True
  else:even=True
  l=lcm(l,a[i]//2)
  ll=lcm(ll,a[i])
  if l>m:print(0);exit()
for i in range(n):
  if l%a[i]==0:print(0);exit()
print((m-l)//ll+1)

Submission status: Accepted

Solution code:
import fractions
import math
 
N, M = map(int, input().split())
a = list(map(int, input().split()))
a = [i // 2 for i in a]
 
def lcm(a, b):
    return a * b // fractions.gcd(a, b)
    
def check_two(num):
    count = 0
    while num % 2 == 0:
        num //= 2
        count += 1
    return count

two_num = check_two(a[0])

for i in range(1, len(a)):
    if two_num != check_two(a[i]):
        print(0)
        exit()
 
my_lcm = a[0]
for i in range(1, len(a)):
    my_lcm = lcm(my_lcm, a[i])
    if my_lcm > M:
        print(0)
        exit()
    
ans = M // my_lcm
print(math.ceil(ans / 2))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from fractions import gcd


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


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


n, m = map(int, input().split())
a = list(map(lambda x: int(x) // 2, input().split()))
b = 1
c = f(a[0])
for i in range(n):
    if f(a[i]) != c:
        print(0)
        exit()
    a[i] >>= c
    b = lcm(b, a[i])
m >>= c
if b > m:
    print(0)
    exit()

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

Submission status: Accepted

Solution code:
N, M = (int(i) for i in input().split())
A = [int(i) for i in input().split()]

def kouyaku(a,b):
    aa = max(a,b)
    bb = min(a,b)
    if bb == 0:
        return aa
    else:
        return kouyaku(bb,aa%bb)

g = 1
A = [a//2 for a in A]
for i in range(N):
    g = g//kouyaku(g, A[i])*A[i]
    if g > M:
        print(0)
        exit()
Flag = False
for i in range(N):
    if (g//A[i])%2 == 0:
        Flag = True
if Flag:
    print(0)
else:
    print((M//g+1)//2)

Submission status: Accepted

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

def gcd(a,b):
  if a==b:
    return a
  a,b=max(a,b),min(a,b)
  if a%b==0:
    return b
  else:
    return gcd(b,a%b)
  
def lcm(a,b):
  return a*b//gcd(a,b)

if N==1:
  v=M//int(a[0]*0.5)
  if v%2==0:
    print(v//2)
  else:
    print(v//2+1)
  sys.exit()
  
for i in range(N-1):
  if i==0:
    tmp=lcm(a[i]//2,a[i+1]//2)
    devider=min(a[i]//2,a[i+1]//2)
    if (tmp//devider)%2==0:
      print(0)
      sys.exit()
  else:
    tmp=lcm(tmp,a[i+1]//2)
    devider=min(tmp,a[i+1]//2)
    if (tmp//devider)%2==0:
      print(0)
      sys.exit()

v=M//tmp
if v%2==1:
  print(v//2+1)
else:
  print(v//2)

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd

def lcm(a, b):
    return a * b // gcd(a, b)
def lcm_all(A):
    return reduce(lcm, A, 1)

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

scm_core = lcm_all(A)

canmake_scm = True
for a in A:
    if scm_core // a % 2 == 0:
        canmake_scm = False
        break

if canmake_scm:
    print(((M // scm_core)+1) // 2)
else:
    print(0)

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd

def lcm(a, b):
    return a * b // gcd(a, b)
def lcm_all(A):
    return reduce(lcm, A, 1)

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

scm_core = lcm_all(A)

canmake_scm = True
for a in A:
    if scm_core // a % 2 == 0:
        canmake_scm = False
        break

if canmake_scm:
    print(((M // scm_core)+1) // 2)
else:
    print(0)

Submission status: Accepted

Solution code:
from fractions import gcd
from math import ceil

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

n, M = map(int, input().split())
A = tuple(map(lambda x: int(int(x)/2), input().split()))
scm_core = 1
for a in A:
    scm_core = lcm(scm_core, a)

canmake_scm = True
for a in A:
    if scm_core // a % 2 == 0:
        canmake_scm = False

if canmake_scm:
    print(ceil(M // scm_core / 2))
else:
    print(0)

Submission status: Accepted

Solution code:
from functools import reduce

INF = 10**9+1

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

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

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

def LCM_list(L):
    return reduce(LCM,L)

B = [A[i]//2 for i in range(N)]
flag = False
for i in range(N-1):
    count,count_,b,b_ = 0,0,B[i],B[i+1]
    while b % 2 == 0:
        b //= 2
        count += 1
    while b_ % 2 == 0:
        b_ //= 2
        count_ += 1
    if count != count_:
        flag = True
        print(0)
        exit()

hlcm = LCM_list(B)
if hlcm <= M:
    lb,ub = 1,INF
    while lb < ub:
        mid = (lb + ub) // 2
        if hlcm * mid <= M and hlcm * (mid+1) > M:
            break
        elif hlcm * mid > M:
            ub = mid
        else:
            lb = mid
    ans = (mid+1)//2
    print(ans)
else:
    print(0)

Submission status: Accepted

Solution code:
from fractions import gcd


def cnt_div2(x):
    ret = 0
    while x % 2 == 0:
        ret += 1
        x //= 2

    return ret


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

aa = [e // 2 for e in a]

cnt = cnt_div2(aa[0])
for e in aa:
    if cnt_div2(e) != cnt:
        print(0)
        exit()


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


c = 1
for e in aa:
    c = lcm(c, e)

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

Submission status: Accepted

Solution code:
import fractions
from functools import reduce
def lcm1(x,y):
    return (x*y)//fractions.gcd(x,y)
def lcm2(*numbers):
    return reduce(lcm1,numbers,1)
n,m = map(int,input().split())
a = set(map(lambda x: int(x)//2,input().split()))
l = lcm2(*a)
for i in a:
    if l // i % 2 == 0:
        print(0)
        exit()
print(((m // l) + 1) // 2)

Submission status: Accepted

Solution code:
from math import *
from fractions import *
from sys import stdout, stderr, version_info
def fprintf(fs, s, *argv):
    fs.write(s.format(*argv))

def printf(s, *argv):
    fprintf(stdout, s, *argv)

if version_info[0] == 2:
    input = raw_input

def gets(type=int, sep=' '):
    return map(type, input().split(sep))

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

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

def main():
    n,m = gets()
    a = gets()
    lcm = 1
    cnt2 = -1
    for ai in a:
        lcm = _lcm(lcm,ai)
        n2 = num2(ai)
        if (cnt2 != -1 and cnt2 != n2):
            printf('0\n');
            return
        cnt2 = n2

    fprintf(stderr, 'lcm: {}\n', lcm)

    lo, hi = -1, m+1
    while (lo+1 < hi):
        mid = (lo+hi)//2
        if ((mid*2+1) * lcm//2 <= m):
            lo = mid
        else:
            hi = mid

    printf('{}\n', hi)

main()

Submission status: Accepted

Solution code:
import fractions
from functools import reduce
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)#数列に対しての最小公倍数

n,m = map(int,input().split())
a = list(map(int,input().split()))
b = [x//2 for x in a]
c = 0
while True:
    if a[0]%2:
        for i in range(n):
            if a[i]%2 == 0:
                print(0)
                exit()
        break
    else:
        for i in range(n):
            if a[i]%2:
                print(0)
                exit()
            a[i]//=2
        c += 1

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

Submission status: Accepted

Solution code:
from fractions import gcd
n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):
  a[i]//=2
a=sorted(set(a))[::-1]
n=len(a)
b=a[0]
d=a[0]
e=a[0]
ans=m
for i in range(n-1):
  b=gcd(d,a[i+1])
  d=d*a[i+1]//b
  e=gcd(e,a[i+1])
 
c=m//d-m//(2*d)
for i in range(n):
  a[i]//=e
  if a[i]%2==0:
    c=0
    break
 
print(c)

Submission status: Accepted

Solution code:
from fractions import gcd
n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):
  a[i]//=2
a=sorted(set(a))[::-1]
n=len(a)
b=a[0]
d=a[0]
e=a[0]
ans=m
for i in range(n-1):
  b=gcd(d,a[i+1])
  d=d*a[i+1]//b
  e=gcd(e,a[i+1])

c=m//d-m//(2*d)
for i in range(n):
  a[i]//=e
  if a[i]%2==0:
    c=0
    break

print(c)

Submission status: Accepted

Solution code:
import sys
import math
INF=1e9
mod=1e9+7

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

n,m=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]
g=1
init=0
for i in range(n):
    a[i]//=2
num=a[0]
while(num%2==0):
    num/=2
    init+=1
for i in range(1,n):
    num=a[i]
    cnt=0
    while(num%2==0):
        num/=2
        cnt+=1
    if(cnt!=init):
        print(0)
        sys.exit()
for i in range(n):
    g=lcm(g,a[i])
#print(g)
ans=(m//g)
if(ans%2==1):
    print(ans//2+1)
else:
    print(ans//2)

Submission status: Accepted

Solution code:
# tx = lcm(A[0],A[1], ..., A[N-1])
# B = [tx/A[0], tx/A[1], ..., tx/A[N-1]]
# 2X/A[i] = 2p + 1 となるようなpが存在する, が条件
# tx = 2Xとおくと, txは偶数 かつ すべてのi(<N)において, tx/A[i]は奇数である必要がある. 
# よって, Bの要素はすべて奇数 かつ txは偶数である, が条件
# そのような, txが存在するならば, x = tx/2が条件を満たす集合の最小元であり, 他の要素は,xの奇数倍として表される.
# というのも, xの偶数倍となると2p+1が奇数となる条件を反すから

import sys

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

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

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

tx = 1
for a in A:
    tx = lcm(tx, a)

if tx % 2 == 1:
    print(0)
    sys.exit()

B = []
for a in A:
    B.append(tx // a)

for b in B:
    if b % 2 == 0:
        print(0)
        sys.exit()

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

Submission status: Accepted

Solution code:
from fractions import gcd

def lcm(a, b):
  return a * b // gcd(a, b)
  
N,M = map(int,input().split())
A = list(map(int,input().split()))

B = set()
l = 1
for i in range(len(A)):
  c = 0
  a = A[i]
  while(a%2 == 0):
    a //= 2
    c += 1
  if i == 0:
    c0 = c
  else:
    if c0 != c:
      print(0)
      exit()
  l = lcm(l,A[i]//2)

print((M+l)//(2*l))

Submission status: Accepted

Solution code:
import sys

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

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

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

tx = 1
for a in A:
    tx = lcm(tx, a)

B = []
for a in A:
    B.append(tx // a)

for b in B:
    if b % 2 == 0:
        print(0)
        sys.exit()
ans = ((M // (tx//2)) + 1) // 2
print(ans)

Submission status: Accepted

Solution code:
import fractions
import sys

def times_div2(n):
  times=0
  while(n%2==0):
    n//=2
    times+=1
  return times

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

aset=set()
tset=set()
for a in alist:
  aset.add(a)
  tset.add(times_div2(a))
  
if len(tset)>1:
  print(0)
  sys.exit(0)
  
lcm_a2s=1
for a in aset:
  a2=a//2
  lcm_a2s*=(a2)//fractions.gcd(lcm_a2s,a2)

#print(lcm_a2s)
print((M-lcm_a2s)//(2*lcm_a2s)+1)

Submission status: Accepted

Solution code:
import sys
import fractions as f
n,m=map(int,input().split())
A=list(map(int,input().split()))
a=A[0]
b=0
while a%2==0:
  a=a//2
  b=b+1
b=2**b
B=[0]*n
for i in range(n):
  B[i]=A[i]//b
  if B[i]*b!=A[i] or B[i]%2==0:
    print(0)
    sys.exit()
G=1
for i in range(n):
  G=G*B[i]//(f.gcd(G,B[i]))
print(int((m+G*b//2))//(G*b))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=[a[i]//2 for i in range(n)]
from fractions import gcd
from functools import reduce
def lcm(x,y):
  return (x*y)//gcd(x,y)
x=reduce(lcm,b,1)
y=reduce(lcm,a,1)
if x>m:
  print(0)
else:
  z=(m-x)//y+1
  for i in b:
    if (x//i)%2==0:
      z=0
      break
  print(z)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline
def inputS(): return input().rstrip().decode()
readlines = sys.stdin.buffer.readlines 


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

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

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

N, M = map(int, inp().split())
A = list(map(int, inp().split()))
# 2で割ったものに置き換え a -> a'
Ad = [a//2 for a in A]

# 各要素について、2で割り切れる回数が等しいかチェック
div2 = div2cnt(Ad[0])
for a in Ad:
  if div2cnt(a) != div2:
    print(0)
    exit()
    
# LCM
_lcm = Ad[0]
for a in Ad:
  _lcm = lcm(_lcm, a)
if _lcm > M:
  print(0)
  exit()
  
print((M//_lcm + 1) // 2)   # 切り上げ

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline
def inputS(): return input().rstrip().decode()
readlines = sys.stdin.buffer.readlines 

from functools import reduce

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

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

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

N, M = map(int, inp().split())
A = list(map(int, inp().split()))
# 2で割ったものに置き換え a -> a'
Ad = [a//2 for a in A]

# 各要素について、2で割り切れる回数が等しいかチェック
div2 = div2cnt(Ad[0])
for a in Ad:
  if div2cnt(a) != div2:
    print(0)
    exit()
    
# LCM
_lcm = reduce(lcm, Ad)
if _lcm > M:
  print(0)
  exit()
  
print((M//_lcm + 1) // 2)   # 切り上げ

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
input = sys.stdin.buffer.readline
def inputS(): return input().rstrip().decode()
readlines = sys.stdin.buffer.readlines 

from functools import reduce

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

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

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

N, M = map(int, input().split())
A = list(map(int, input().split()))
# 2で割ったものに置き換え a -> a'
Ad = [a//2 for a in A]

# 各要素について、2で割り切れる回数が等しいかチェック
div2 = div2cnt(Ad[0])
for a in Ad:
  if div2cnt(a) != div2:
    print(0)
    exit()
    
# LCM
_lcm = reduce(lcm, Ad)
if _lcm > M:
  print(0)
  exit()
  
print((M//_lcm + 1) // 2)   # 切り上げ

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
input = sys.stdin.buffer.readline
def inputS(): return input().rstrip().decode()
readlines = sys.stdin.buffer.readlines 

from functools import reduce

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

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

N, M = map(int, input().split())
A = list(map(int, input().split()))
# 2で割ったものに置き換え a -> a'
Ad = [a//2 for a in A]

# 各要素について、2で割り切れる回数が等しいかチェック
div2 = None
for a in Ad:
  cnt = 0
  while a%2 == 0:
    a //= 2
    cnt += 1
  if div2 is None:
    div2 = cnt
  elif div2 != cnt:
    print(0)
    exit()
    
# LCM
_lcm = reduce(lcm, Ad)
if _lcm > M:
  print(0)
  exit()
  
print((M//_lcm + 1) // 2)   # 切り上げ

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
n,m=f(); a=list(f())
from fractions import *
l=1
for i in a:
  i//=2; l=l*i//gcd(l,i)
  if (l//i)%2<1 or l>m: print(0); exit()
print(m//l-m//(l*2))

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
n,m=f(); l=list(f())
import fractions as f
k=1
for i in l:
  i//=2; k=k*i//f.gcd(k,i)
  if (k//i)%2<1 or k>m: print(0); break
else: print(m//k-m//(k*2))

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
n,m=f()
l=list(f())
def g(x,y):
  while y: x,y=y,x%y
  return x
k=1
for i in l:
  i//=2; k=k*i//g(k,i)
  if (k//i)%2<1 or k>m: print(0); break
else:
  print(m//k-m//(k*2))

Submission status: Accepted

Solution code:
#Atcoderではmathではなく，fractionsを使用するため．基本fractions
#a/2が全て同じ数の2の倍数を素因数に持つ必要がある．

import fractions
from functools import reduce

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 waru2(n):
    count = 0
    while True:
        if n % 2 == 0:
            n //= 2
            count += 1
        else:
            break
    return count

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

half_a = []
waru = []

for i in a:
    half_a.append(i//2)
    waru.append(waru2(i))

if max(waru) == min(waru):
    half_lcm = lcm_list(half_a)
    print(-(-(M//half_lcm)//2))
else:
    print(0)

Submission status: Accepted

Solution code:
import itertools
import sys
import math
import numpy as np
import fractions
from collections import deque
from itertools import combinations
from functools import reduce
from functools import lru_cache
sys.setrecursionlimit(10**9)

def get_lcm(num):
    return reduce(lambda x,y:(x * y) // fractions.gcd(x, y), num, 1)

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

    lcm = get_lcm(half_A)

    if lcm > M:
        print(0)
        exit()

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

    print(math.ceil((M//lcm)/2))


if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import itertools
import sys
import math
import numpy as np
import fractions
from collections import deque
from itertools import combinations
from functools import reduce
from functools import lru_cache
sys.setrecursionlimit(10**9)

def get_lcm(num):
    return reduce(lambda x,y:(x * y) // fractions.gcd(x, y), num, 1)

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

    lcm = get_lcm(half_A)

    if lcm > M:
        print(0)
        exit()

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

    # print(math.ceil(M/(2*lcm)))
    print((M//lcm + 1) // 2)


if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
def main():
    from fractions import gcd
    from functools import reduce
    n,m=map(int,input().split())
    a=list(map(int,input().split()))
    
    def cnt_2(n):
        cnt=0
        while n>0:
            if n%2==0:
                cnt+=1
                n//=2
            else:
                return cnt
    
    def lcm(x,y):
      return x*y//gcd(x,y)
    
    before=cnt_2(a[0])    
    for i in range(1,n):
        after=cnt_2(a[i])
        if after!=before:
            print(0)
            exit()
        before=after
    
    
    a=[num//(2**before) for num in a]
    before-=1
    G=reduce(lcm,a)*(2**before)
    ans=(m//G+1)//2
    print(ans) 
  
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from functools import reduce


def count_factors(a, factor):
    count = 0
    while a % factor == 0:
        count += 1
        a //= factor
    return count


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


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


if __name__ == "__main__":
    n, m = map(int, input().split())
    a = list(set(map(lambda x: int(x) // 2, input().split())))
    num_of_two = count_factors(a[0], 2)
    for ai in a[1:]:
        if count_factors(ai, 2) != num_of_two:
            print(0)
            exit()

    a_lcm = reduce(lambda x, y: lcm(x, y), a)
    if a_lcm > m:
        print(0)
        exit()

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
from fractions import gcd
def Lcm(x):
  L = 1
  for a in x:
    a=a//2
    L = (a // gcd(a, L))*L
  return L
X=Lcm(A)
fg = 0
for i in A:
  if (X//(i//2))%2==0:
    fg=1
    break
if fg==1:
  print(0)
else:
  print(((M//X)+1)//2)

Submission status: Accepted

Solution code:
from  functools import reduce
from fractions import gcd
n,m=map(int,input().split())
a=list(map(int,input().split()))
a=[i//2 for i in a]
#print(a)
lc=reduce(lambda x,y: (x*y)//gcd(x,y) , a)
#print(lc)
flag=True
for i in a:
  if (lc//i)%2==0:
    flag=False
    break
if flag==False:
  print(0)
else:
  x=m//lc
  print(x//2) if (x%2)==0 else print((x//2)+1)

Submission status: Accepted

Solution code:
from  functools import reduce
def gcd(v1,v2):
  v=v1%v2
  if v==0:
    return v2
  else :
    return gcd(v2,v)
n,m=map(int,input().split())
a=list(map(int,input().split()))
a=[i//2 for i in a]
#print(a)
lc=reduce(lambda x,y: (x*y)//gcd(x,y) , a)
#print(lc)
flag=True
for i in a:
  if (lc//i)%2==0:
    flag=False
    break
if flag==False:
  print(0)
else:
  x=m//lc
  print(x//2) if (x%2)==0 else print((x//2)+1)

Submission status: Accepted

Solution code:
# from math import sqrt
# from heapq import heappush, heappop
# from collections import deque
from functools import reduce

# a, b = [int(v) for v in input().split()]


def main():
    N, M = map(int, input().split())
    A = [int(v) // 2 for v in input().split()]

    def gcd(v1, v2):
        v = v1 % v2
        if v == 0:
            return v2
        return gcd(v2, v)

    def lcm(v1, v2):
        return v1 * v2 // gcd(v1, v2)

    lcma = reduce(lcm, A)

    if next(filter(lambda v: (lcma // v) % 2 == 0, A), None) is not None:
        print(0)
        exit()

    print((M + lcma) // (2 * lcma))


main()

Submission status: Accepted

Solution code:
# from math import sqrt
# from heapq import heappush, heappop
# from collections import deque
from functools import reduce

# a, b = [int(v) for v in input().split()]


def main():
    N, M = [int(v) for v in input().split()]
    A = list(set([int(v) // 2 for v in input().split()]))

    def func(a):
        count = 0
        while a % 2 == 0:
            count += 1
            a //= 2
        return count

    fa = func(A[0])
    for a in A[1:]:
        if func(a) != fa:
            print(0)
            exit()

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

    def lcm(v1, v2):
        return v1 * v2 // gcd(v1, v2)

    a_lcm = reduce(lambda v1, v2: lcm(v1, v2), A)
    if a_lcm > M:
        print(0)
        exit()

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


main()

Submission status: Accepted

Solution code:
from fractions import gcd

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

"""
A = [a_0, a_1, ...]として、
X = a_i * (p+0.5) = (a_i//2) * (2*p+1)
(2p+1)は奇数より、Xが2で割り切れる回数は(a_i//2)が2で割り切れる回数に等しい。
特に全てのa_iに関して2で割り切れる回数が等しくなければXは存在しない。

もし全てのa_iに関して2で割り切れる回数が等しいならば、
    T = LCM(a_0//2, a_1//2, ...)
と定めれば、XはTの奇数倍で尽くされる。
"""

def quotBy2(n):
    num = 0
    while n % 2 == 0:
        num += 1
        n //= 2
    return num

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

T = A[0] // 2
quot = quotBy2(A[0])
for i in range(N - 1):
    T = lcm(T, A[i + 1]//2)
    #print("T={}".format(T))
    if quot != quotBy2(A[i + 1]):
        print(0)
        exit()

print((M + T) // (2 * T))

Submission status: Accepted

Solution code:
# from math import sqrt
# from heapq import heappush, heappop
# from collections import deque
from functools import reduce

# a, b = [int(v) for v in input().split()]


def main():
    N, M = [int(v) for v in input().split()]
    A = list(set([int(v) // 2 for v in input().split()]))

    def func(a):
        count = 0
        while a % 2 == 0:
            count += 1
            a //= 2
        return count

    fa = func(A[0])
    for a in A[1:]:
        if func(a) != fa:
            print(0)
            exit()

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

    def lcm(v1, v2):
        return v1 * v2 // gcd(v1, v2)

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

    # a_lcm = reduce(lambda v1, v2: lcm(v1, v2), A)

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


main()

Submission status: Accepted

Solution code:
import fractions
import math
n, m = list(map(int, input().split()))
a = sorted(list(map(int, input().split())))
a = [int(i/2) for i in a]
num_gcd = a[0]
for i in range(1, n):
    num_gcd = num_gcd * a[i] // fractions.gcd(num_gcd, a[i])
flag = False
c = 0
p = a[0]
while True:
    if p % 2 != 0:
        break
    p /= 2
    c += 1
for i in range(1, n):
    if a[i] % (2 ** c) == 0 and (a[i] // (2 ** c)) % 2 != 0:
        pass
    else:
        flag = True
if flag:
    print(0)
else:
    print(math.ceil((m // num_gcd) / 2))

Submission status: Accepted

Solution code:
#coding:utf-8
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]
    N,M = LMIIS()
    A =  list(set(map(lambda x: int(x)//2 ,input().split())))
    # print(A)
    from fractions import gcd
    a = A[0]
    lcm = a
    x = len(bin(a))-len(bin(a).rstrip('0'))
    for a in A:
        # print(bin(a),len(bin(a))-len(bin(a).rstrip('0')))
        if x != len(bin(a))-len(bin(a).rstrip('0')):
            print(0)
            return
        lcm = lcm * a // gcd(lcm,a)


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

    

    



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import fractions
N, M = map(int, input().split())
a_array = list(map(int, input().split()))

Q = 2 ** 35

two_count = fractions.gcd(a_array[0], Q)
lcm = 1

for a in a_array:
    aa = a // 2
    if two_count != fractions.gcd(a, Q):
        print(0)
        exit()
    lcm = int(aa * lcm) // fractions.gcd(aa, lcm)
    if lcm > M:
        print(0)
        exit()

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

Submission status: Accepted

Solution code:
import sys
import math

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

sys.setrecursionlimit(1000000)
input = lambda: sys.stdin.readline().rstrip()

N, M = map(int, input().split())
a = list(map(lambda x : int(x) // 2, input().split()))
lcm = 1
for i in a:
    lcm = lcm * i // gcd(lcm, i)
ok = True
for i in a:
    if lcm // i % 2 == 0:
        ok = False

if not ok:
    print(0)
else:
    print((M // lcm - 1) // 2 + 1)

Submission status: Accepted

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

n,m = map(int,readline().split())
lst1 = list(map(int,readline().split()))
"""
lst1の全要素に対して、
X = lst1[i]*(p+0.5)となるXの個数を求めよ
↓問題文を言い換えると
X=(lst1[i]//2)*(2p+1)を満たすXの個数を求めよ。
※プログラミングでは大体の場合整数に置き換えて考えたほうが良い

これを考慮すると、2p+1部分より、Xはlst1[i]//2の奇数倍である事がわかり、
・任意のiに対して、Xはlst1[i]//2の倍数である。
・任意のiに対して、Xが2で割り切れる回数とlst1[i]//2が2で割り切れる回数は等しい

これを満たさなかった場合、半公倍数は1つも存在しないことになる。
そうでない場合、答えはlst1全ての最小公倍数をTとして、
ans = (X-T)//(2*T)+1 #XはTの奇数倍である為
"""
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
def lcm(a,b):
    return (a//gcd(a,b)*b)

tmp = lst1[0]//2 #最初の要素は手計算しておく
con = 0

while True:
    if tmp%2==0:
        tmp //= 2
        con += 1
    else:
        break

x = 1 #最小公倍数の単位元は1

for i in range(n):
    lst1[i] //= 2 #全要素は偶数である

    x = lcm(lst1[i],x)

    tmp = lst1[i]
    cnt = 0
    while True:
        if tmp%2==0:
            tmp //= 2
            cnt += 1
        else:
            break
    if cnt != con: #2で割り切れる回数が全て等しい必要がある
        print(0)
        exit()

if m < x: #最初に出てくる半公倍数が制約mより大きいなら、条件を満たすXは存在しないので
    print(0)
else:
    print((m-x)//(2*x)+1) #条件を満たす半公倍数の数は、(制約-最小公倍数)//(最小公倍数*2)+1個

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[ i //2 for i in list(map(int,input().split()))]
def f(x):
  c=0
  while(x%2==0):
    x//=2
    c+=1
  return c
def gcd(a,b):
  if b==0:
    return a
  return gcd(b,a%b)
def lcm(a,b):
  return a//gcd(a,b)*b

t=f(a[0])
for i in range(len(a)):
  if t!=f(a[i]):
    print(0)
    exit(0)
  a[i]//=2**t
m//=2**t
l=1
for i in a:
  l=lcm(l,i)
  if l>m:
    print(0)
    exit(0)
m//=l
print((m+1)//2)