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: Runtime Error

Solution code:
import math
from functools import reduce

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

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

def main():
    n, m, *a_n = map(int, open(0).read().split())
    a_n_half = list(map(lambda x: x // 2, a_n))
    a_n_lcm = lcm(a_n_half)
    
    cnt = m // a_n_lcm
    
    if cnt % 2 == 0:
        print(cnt // 2)
    else:
        print(cnt // 2 + 1)
        
    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import math
from functools import reduce

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

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

def main():
    n, m, *a_n = map(int, open(0).read().split())
    a_n_half = list(map(lambda x: x // 2, a_n))
    a_n_lcm = lcm(a_n_half)
    
    cnt = m // a_n_lcm
    
    if cnt % 2 == 0:
        print(cnt // 2)
    else:
        print(cnt // 2 + 1)
        
        
    
    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import fractions

n, m = map(int, input().split())
a = list(map(int, input().split()))
b = []
for i in a:
    b_ = i//2
    b.append(b_)
count = 0
flag = True

while res % 2 != 0:
    res = a[0]/2
    count += 1
for i in a:
    if i % 2**count != 0:
        flag = False
        break
if flag:    
    lcm = b[0]
    for i in range(1, len(b)):
        lcm = lcm*b[i]//fractions.gcd(lcm,b[i])
    ans = m // lcm - (m//(lcm*2))
    print(ans)
else:
    print(0)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys, math
from functools import reduce

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

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

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

def solve(N: int, M: int, a: "List[int]"):
    a = [aa // 2 for aa in a]
    mm = lcm_list(a)
    print((M // mm + 1) // 2)
    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)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, a)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
list_a = [int(x) for x in input().split()]

import fractions

def insu2(a) :
    insu = 0
    while a%2 == 0 :
        insu += 1
        a /= 2
    return insu

check = True

for i in list_a :
    if insu2(i) != insu2(list_a[0]) :
        check = False

ans_0 = list_a[0]
for i in range(1,N) :
    ans_0 = ans_0 * list_a[i] // fractions.gcd(ans_0, list_a[i])

if ans_0 == 2 :
    ans = int(M+1/2)
else :
    ans = int((int(M/(ans_0/2))+1)/2)

if check == False :
    print(0)
else :
    print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
list_a = [int(x) for x in input().split()]

import fractions

def insu2(a) :
    insu = 0
    while a%2 == 0 :
        insu += 1
        a /= 2
    return insu

check = True

for i in list_a :
    if insu2(i) != insu2(list_a[0]) :
        check = False

ans_0 = list_a[0]
for i in range(1,N) :
    ans_0 = ans_0 * list_a[i] // fractions.gcd(ans_0, list_a[i])

ans = int((int(M/(ans_0/2))+1)/2)

if check == False :
    print(0)
else :
    print(ans)

Submission status: Runtime Error

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

L = 1
for a in A:
    L = (L*a)//gcd(L,a)
print((M+L)//(2*L))

Submission status: Runtime Error

Solution code:
from fractions import gcd

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

a=list(map(lambda x: x//2, a))

def lcm(q):
  x = q[0]
  for i in range(1, len(q)):
    x = (x * q[i]) // gcd(x, q[i])
  return x

lcma=lcm(a)

if (lcma//a[0])%2==0:
  print(0)
  
else:
  flg=0
  for i in range(1,n):
    if (lcma//a[i])%2==0:
      print(0)
      flg=1

  if flg==0:
    temp=m//lcma
    print(temp//2 if temp%2==0 else temp//2+1)

Submission status: Runtime Error

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

def lcm(a, b):
  if a > b:
    a, b = b, a
  while True:
    a, b = b%a, a
    if a == 0:
      return b

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


def main():
  n, m = map(int, input().strip().split())
  As = list(map(int, input().strip().split()))
  x = 1
  for i in range(len(As)):
    x = gcm(x, As[i])
  if sum([(x//A)%2 == 1 for A in As]) == len(As):
    print(int(m/x-0.5)+1)
  else:
    print(0)

if __name__=='__main__':
  main()

Submission status: Runtime Error

Solution code:
from functools import reduce

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

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

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

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

lcm = lcm(*a_list)

if m < lcm/2:
    print(0)
else:
    print(m // lcm + 1)

Submission status: Runtime Error

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

import numpy as np

lcm = np.lcm.reduce(a_list)

if m < lcm/2:
    print(0)
else:
    print(m // lcm + 1)

Submission status: Runtime Error

Solution code:
import numpy as np
def lcm(a):
    from fractions import gcd
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x


def main():
    N,M=[int(x) for x in input().split()]
    a = [int(x) for x in input().split()]
    b = [x//2 for x in a]

    # l = np.lcm.reduce(b)
    l = lcm(b)
    for x in b:
        if l // x % 2 == 0:
            print(0)
            return

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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np


def main():
    N,M=[int(x) for x in input().split()]
    a = [int(x) for x in input().split()]
    b = [x//2 for x in a]

    lcm = np.lcm.reduce(b)
    for x in b:
        if lcm // x % 2 == 0:
            print(0)
            return

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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import fractions
n, m = map(int, input().split())
a = list(map(int, input().split()))
num = 1
cnt = []
for x in a:
    c = 0
    for i in range(int(math.log(x,2))+1):
        if x>>c&1:
            break
        else:
            c+=1
    cnt.append(c)
if max(cnt) != min(cnt):
    print(0)
else:
    for x in a:
        num = num * (x//2) // fractions.gcd(num, x//2)
    print(m//num-(m//num)//2)

Submission status: Runtime Error

Solution code:
import math
n, m = map(int, input().split())
a = list(map(int, input().split()))
num = 1
for x in a:
    num = num * (x//2) // math.gcd(num, x//2)
cnt = 0
print(m//num-(m//num)//2)

Submission status: Runtime Error

Solution code:
import math
n, m = map(int, input().split())
a = list(map(int, input().split()))
num = 1
for x in a:
    num = num * (x//2) // math.gcd(num, x)
cnt = 0
print(m//num-(m//num)//2)

Submission status: Runtime Error

Solution code:
import math
from functools import reduce
def f(n):
    res = 0
    while(n%2 == 0):
        res += 1
        n //= 2
    return res

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

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

F = set()
for a in A:
    F.add(f(a))
if(len(F) != 1):
    print(0)
    exit()

l = reduce(lcm, A, 1)
ans = 0 if (l == 0) else (- (- (m // 2) // l))
print(ans)

Submission status: Runtime Error

Solution code:
import math
from functools import reduce
def f(n):
    res = 0
    while(n%2 == 0):
        res += 1
        n //= 2
    return res

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

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

F = set()
for a in A:
    F.add(f(a))
if(len(F) != 1):
    print(0)
    exit()

l = reduce(lcm, A)
ans = 0 if (l == 0) else (- (- (m // 2) // l))
print(ans)

Submission status: Runtime Error

Solution code:
import math
from functools import reduce
def f(n):
    res = 0
    while(n%2 == 0):
        res += 1
        n //= 2
    return res

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

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

F = set()
for a in A:
    F.add(f(a))
if(len(F) != 1):
    print(0)
    exit()

l = reduce(lcm, A)
ans = - (- (m // 2) // l)
print(ans)

Submission status: Runtime Error

Solution code:
import math
import sys
from functools import reduce
def f(n):
    res = 0
    while(n%2 == 0):
        res += 1
        n //= 2
    return res

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

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

F = set()
for a in A:
    F.add(f(a))
if(len(F) != 1):
    print(0)
    sys.exit()

l = reduce(lcm, A)
ans = - (- (m // 2) // l)
print(ans)

Submission status: Runtime Error

Solution code:
import math
import sys
def f(n):
    res = 0
    while(n%2 == 0):
        res += 1
        n //= 2
    return res

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

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

t = f(a[0])
for v in a:
    if(f(v) != t):
        print(0)
        sys.exit()
a = list(map(lambda x: x >> t, a))
m >>= t

l = 1
for v in a:
    l = lcm(l, v)
    if(l > m ):
        print(0)
        sys.exit()
ans = - (-m // (2*l))
print(ans)

Submission status: Runtime Error

Solution code:
import math
def f(n):
    res = 0
    while(n%2 == 0):
        res += 1
        n //= 2
    return res

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

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

t = f(a[0])
for v in a:
    if(f(v) != t):
        print(0)
        exit()
a = list(map(lambda x: x >> t, a))
m >>= t

l = 1
for v in a:
    l = lcm(l, v)
    if(l > m ):
        print(0)
        exit()
ans = - (-m // (2*l))
print(ans)

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

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

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

n,m=map(int,input().split())
arr=list(map(int,input().split()))
l=lcm(arr[0],arr[1])
for i in range(2,n):
  l=lcm(l,arr[i])
  if l//2>m:
    print(0)
    exit()
ans=(m-l//2)//l+1
print(ans)

Submission status: Runtime Error

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

N,M = map(int,input().split())
List=list(map(int,input().split()))
aa = int(lcm_list(List)/2)
cnt = 0
a = List[0]
while a%2 == 0:
  cnt+=1
  a = int(a/2)
out = 0
if cnt == 0:
  out = 1
  cnt = 1
for i in range(len(List)):
  if List[i] % (2**cnt) > 0:
    out = 1
  if List[i] % (2**(cnt+1)) == 0:
    out = 1

if out == 1:
  print(0)
else:
  print(int(math.ceil((M / aa)) // 2))

Submission status: Runtime Error

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

N,M = map(int,input().split())
List=list(map(int,input().split()))
aa = int(lcm_list(List)/2)
cnt = 0
a=List[0]
while a%2 == 0:
  cnt+=1
  a = int(a/2)
out = 0
if cnt == 0:
  out = 1
  cnt = 1
for i in range(len(List)):
  if List[i] % (2**cnt) > 0:
    out = 1
  elif List[i] % (2**(cnt+1)) == 0:
    out = 1

if out == 1:
  print(0)
else:
  print(int(math.ceil((M / aa)) // 2))

Submission status: Runtime Error

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

N,M = map(int,input().split())
List=list(map(int,input().split()))
aa = int(lcm_list(List)/2)
cnt = 0
a=List[0]
while a%2 == 0:
  cnt+=1
  a = int(a/2)
out = 0
if cnt == 0:
  out = 1
  cnt = 1
for i in range(len(List)):
  if List[i] % (2**cnt) == 1:
    out = 1
  elif List[i] % (2**(cnt+1)) == 0:
    out = 1

if out == 1:
  print(0)
else:
  print(int(math.ceil((M / aa)) // 2))

Submission status: Runtime Error

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

N,M = map(int,input().split())
List=list(map(int,input().split()))
aa = int(lcm_list(List)/2)
cnt = 0
a=List[0]
while a%2 == 0:
  cnt+=1
  a = int(a/2)
out = 0
if cnt == 0:
  out = 1
  cnt = 1
for i in range(len(List)):
  if List[i] % (2**cnt) == 1:
    out = 1
  elif List[i] % (2**(cnt+1)) == 0:
    out = 1

if out == 1:
  print(0)
else:
  print(int(math.ceil((M / aa)) // 2))

Submission status: Runtime Error

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

N,M = map(int,input().split())
List=list(map(int,input().split()))
aa = int(lcm_list(List)/2)
cnt = 0
a=List[0]
while a%2 == 0:
  cnt+=1
  a = int(a/2)
out = 0
if cnt == 0:
  out = 1
  cnt = 1
for i in range(len(List)):
  if List[i] % (2**cnt) == 1:
    out = 1
  elif List[i] % (2**(cnt+1)) == 1:
    out = 1

if out == 1:
  print(0)
else:
  print(int(math.ceil((M / aa)) // 2))

Submission status: Runtime Error

Solution code:
import fractions
from functools import reduce
import math
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 = map(int,input().split())
List=list(map(int,input().split()))
aa = int(lcm_list(List) / 2)
cnt = 0
a=List[0]
while a%2 == 0:
  cnt+=1
  a /= 2
out = 0
if cnt == 0:
  out = 1
  cnt = 1
for i in range(len(List)):
  if List[i] % (2**cnt) == 1:
    out = 1
  elif List[i] % (2**(cnt+1)) == 1:
    out = 1

if out == 1:
  print(0)
else:
  print(int(math.ceil((M / aa)) // 2))

Submission status: Runtime Error

Solution code:
import fractions
from functools import reduce
import math
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 = map(int,input().split())
List=list(map(int,input().split()))
aa = lcm_list(List) / 2
cnt = 0
a=List[0]
while a%2 == 0:
  cnt+=1
  a /= 2
out = 0
if cnt == 0:
  out = 1
  cnt = 1
for i in range(len(List)):
  if List[i] % (2**cnt) == 1:
    out = 1
  elif List[i] % (2**(cnt+1)) == 1:
    out = 1

if out == 1:
  print(0)
else:
  print(math.ceil((M / aa)) // 2)

Submission status: Runtime Error

Solution code:
import fractions
from functools import reduce
import math
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 = map(int,input().split())
List=list(map(int,input().split()))
aa = lcm_list(List) / 2
cnt = 0
a=List[0]
while a%2 == 0:
  cnt+=1
  a /= 2
out = 0
for i in range(len(List)):
  if List[i] % (2**cnt) == 1:
    out = 1
  elif List[i] % (2**(cnt+1)) == 1:
    out = 1

if out == 1:
  print(0)
else:
  print(math.ceil((M / aa)) // 2)

Submission status: Runtime Error

Solution code:
import fractions

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

NM = input().split()
N = int(NM[0])
M = int(NM[1])

a_string = input().split()
a = []
for i in range(N):
  a.append(int(a_string[i]))
  
tmp = lcm(a[0],a[1])
for i in range(2,N):
  tmp = lcm(tmp,a[i])

count = 0

y = (M//tmp)*2

for i in range(y):
	u = i+0.5
	if(1 <= tmp*u <= M):
  		count += 1

        
print(count)

Submission status: Runtime Error

Solution code:
import fractions

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

NM = input().split()
N = int(NM[0])
M = int(NM[1])

a_string = input().split()
a = []
for i in range(N):
  a.append(int(a_string[i]))
  
tmp = lcm(a[0],a[1])
for i in range(2,N):
  tmp = lcm(tmp,a[i])

count = 0

y = M//tmp +2

for i in range(y):
	u = i+0.5
	if(1 <= tmp*u <= M):
  		count += 1

        
print(count)

Submission status: Runtime Error

Solution code:
import fractions

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

NM = input().split()
N = int(NM[0])
M = int(NM[1])

a_string = input().split()
a = []
for i in range(N):
  a.append(int(a_string[i]))
  
tmp = lcm(a[0],a[1])
for i in range(2,N):
  tmp = lcm(tmp,a[i])

count = 0
tmp_2 = tmp/2

i = 0.5
while(tmp*i <= M):
  i += 1
  count += 1

        
print(count)

Submission status: Runtime Error

Solution code:
from fractions import gcd
from functools import reduce

N, M = map(int, input().split())
*a, = map(int, input().split())
lcm = reduce(lambda x,y:x*y//gcd(x,y), a)

m = 10**9
for i in map(lambda x:lcm//x, a):
    if i%2==0:
        print(0)
        break
    m = min(m, i)
else:
    start = int(lcm*0.5)
    print((M-start)//lcm+1)

Submission status: Runtime Error

Solution code:
from fractions import gcd
from functools import reduce

N, M = map(int, input().split())
*a, = map(int, input().split())
lcm = reduce(lambda x,y:x*y//gcd(x,y), a)

m = 10**9
for i in map(lambda x:lcm//x, a):
    if i%2==0:
        print(0)
        break
    m = min(m, i)
else:
    if m==1:
        start = int(lcm*1.5)
    else:
        start = int(lcm*0.5)

    print((M-start)//lcm+1)

Submission status: Runtime Error

Solution code:
from functools import reduce

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

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

def ex_euclid(x,y):
    c0,c1 = x,y
    a0,a1 = 1,0
    b0,b1 = 0,1
    while c1:
        a0,a1 = a1,a0-c0//c1*a1
        b0,b1 = b1,b0-c0//c1*b1
        c0,c1 = c1,c0%c1
    return c0,a0,b0

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

LCM = reduce(lcm,A)

SCMs = []
flag = True

for i in range(N-1):
    c,a,b = ex_euclid(A[i],-A[i+1])
    if (A[i+1]-A[i])//2%c == 0:
        SCMs.append(A[i]*((A[i+1]-A[i])//2//c)*a+A[i]//2)
    else:
        flag = False
        break
        
print((M-reduce(lcm,SCMs)%LCM)//LCM+1 if flag else 0)

Submission status: Runtime Error

Solution code:
import sys

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

n,m=map(int,input().split())
a=tuple(map(int,input().split()))
a.sort()
lcm = 1
for i in a:
    lcm = lcm * i // gcd(lcm,i)
for i in a:
    if (lcm//i)%2 == 0:
        print(0)
        sys.exit()
print((m+lcm//2)//lcm)

Submission status: Runtime Error

Solution code:
import sys

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

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

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

Submission status: Runtime Error

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

n,m = map(int,input().split())
a = [int(x) for x in input().split()]
l = 1
for i in a:
  l = lcm(l,i)

ans = 0
actL = l
while actL<=m:
  if actL % 4 !=0:
    ans+=1
  actL+=l
print(ans)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.read


n, m, *alst = list(map(int, read().split()))
mm = 2 * m


def min_factor(n):
    sieve = list(range(n + 1))
    sieve[2::2] = [2] * (n // 2)
    for i in range(3, int(n ** 0.5) + 2, 2):
        if sieve[i] == i:
            sieve[i * i::2 * i] = [i] * ((n - i * i) // (2 * i) + 1)
    return sieve


# 素因数分解
def prime_factorize(n):
    a = {}
    while n != 1:
        b = table[n]
        if b in a:
            a[b] += 1
        else:
            a[b] = 1
        n //= b
    return a

table = min_factor(max(alst))

dic = {}
prep = -1
for i in alst:
    for key, value in prime_factorize(i).items():
        if key == 2:
            if prep == -1:
                prep = value
            elif value != prep:
                print(0)
                quit()
        if key in dic:
            dic[key] = max(dic[key], value)
        else:
            dic[key] = value

lcm = 1
for i, j in dic.items():
    lcm *= pow(i, j)
    if lcm > mm:
        print(0)
        quit()
res = mm // lcm
print(res // 2 + res % 2)

Submission status: Runtime Error

Solution code:
import math
import fractions
def gcd(a):
    ans = a[0]
    for i in range(1, len(a)):
        ans = ans * a[i] // fractions.gcd(ans, a[i])
    return(ans)

def even_pow(a):
    if(a%2==1):
        return 0
    else:
        x = 1
        while(a%(math.pow(2,x))==0):
            x += 1
        return x-1

def even_bool(a,k):
    n = len(a)
    ans = 1
    for i in range(k):
        ans = ans*(a[i]%(math.pow(2,k)))
    if(ans == 0):
        return 1
    else:
        return 0

N = input().split()
N = [int(i) for i in N]
A = input().split()
a = [int(i)//2 for i in A]

mul = 1
mul = gcd(a)

if((mul%2==0)and(even_bool(a, even_pow(mul))==0)):
    print(0)
    #print('even')
else:
    n = N[1]//mul
    n = (n+1)//2
    print(n)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
aa = list(map(int, input().split()))


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

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



ct = format(aa[0], 'b')[::-1].find('1')
ll = aa[0]/2

for i in range(1,len( aa)):
    if ct != format(aa[i], 'b')[::-1].find('1'):
        ct = -1
        break
    ll = lcm(ll, aa[i]/2)

c = 0
if ct == -1:
    pass
elif k > ll:
    c = k //ll

print(int(-(-c//2)))

Submission status: Runtime Error

Solution code:
import math
def gcd(a):
    ans = a[0]
    for i in range(1, len(a)):
        ans = ans * a[i] // math.gcd(ans, a[i])
    return(ans)

N = input().split()
N = [int(i) for i in N]
A = input().split()
a = [int(i)//2 for i in A]

mul = 1
mul = gcd(a)

if(mul%2==0):
    print(0)
    #print('even')
else:
    n = N[1]//mul
    n = (n-1)//2 + 1
    print(n)

Submission status: Runtime Error

Solution code:
import math
def gcd(a):
    ans = a[0]
    for i in range(1, len(a)):
        ans = ans * a[i] // math.gcd(ans, a[i])
    return(ans)

N = input().split()
N = [int(i) for i in N]
A = input().split()
a = [int(i)//2 for i in A]

#print(a)
mul = 1
mul = gcd(a)
#for i in range(len(a)):
    #mul *= a[i]
#print(mul)

if(mul%2==0):
    print(0)
    print('even')
else:
    n = N[1]//mul
    n = (n-1)//2 + 1
    print(n)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
aa = list(map(int, input().split()))


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

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



ct = format(aa[0], 'b')[::-1].find('1')
ll = aa[0]/2

for i in range(1,len( aa)):
    if ct != format(aa[i], 'b')[::-1].find('1'):
        ct = -1
        break
    ll = lcm(ll, aa[i]/2)

c = 0
if ct == -1:
    pass
elif k > ll:
    c = (k - ll ) //(ll * 2 ) + 1
print (int(c))

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
aa = list(map(int, input().split()))

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

def hgcd (a,b):
    return gcd(a,b)/ 2   

def hlcm(a,b):
    hg = hgcd(a,b)
    lg = gcd ((a/hg) ,(b/hg) )
    
    step = ( a * b  /(lg * lg) )

    return hg * step, step * 2


ll = 0
step = 0
for i in range(n -1):
    ll ,step = hlcm(aa [i], aa[i + 1])

c = 0
if k >= ll:
    c = k - ll //step  + 1

print(int(c))

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
aa = list(map(int, input().split()))

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

def hgcd (a,b):
    return gcd(a,b)/ 2   

def hlcm(a,b):
    hg = hgcd(a,b)
    lg = gcd ((a/hg) ,(b/hg) )
    
    step = ( a * b  /(lg * lg) )

    return hg * step, step * 2


ll = 0
step = 0
for i in range(n -1):
    ll ,step = hlcm(aa [i], aa[i + 1])

c = 0
if k >= ll:
    c = int(k - ll /step ) //step + 1

print(int(c))

Submission status: Runtime Error

Solution code:
from math import sqrt, floor

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


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

    return ret, x


def e_sieve(x):
    li = list(range(2, x + 1))
    primes = []
    while li[0] <= floor(sqrt(x)):
        prime = li[0]
        primes.append(prime)
        li = [e for e in li if e % prime != 0]

    primes += li

    return primes


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

for i, e in enumerate(a):
    a[i] //= 2 ** cnt

primes = e_sieve(max(a))
primes.pop(0)

fact_cnt = [0] * len(primes)

for e in a:
    for i, p in enumerate(primes):
        cnt = 0
        while e % p == 0:
            e //= p
            cnt += 1
        fact_cnt[i] = max(fact_cnt[i], cnt)

lcm = 1
for p, f in zip(primes, fact_cnt):
    lcm *= p ** f

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

Submission status: Runtime Error

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

import math
from functools import reduce

# for i, j in enumerate(a):

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

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

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

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

kouyakusuu = gcd_list(a)
koubaisuu = lcm_list(a)

buf = 1
for i, j in enumerate(a):
    buf *= j / kouyakusuu

ans = (m - buf) // koubaisuu + 1

print(int(ans))

Submission status: Runtime Error

Solution code:
import sys
from math import gcd


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


input = sys.stdin.readline

N, M = map(int, input().split())
A = sorted(map(int, input().split()))
LCM = 1
count = -1
for a in A:
    if a % 2 == 1:
        print(0)
        exit()
    tmp_count = 0
    tmp = a
    while tmp % 2 == 0:
        tmp = tmp//2
        tmp_count += 1
    LCM = lcm_base(LCM, a//2)

    if count == -1:
        count = tmp_count
    if tmp_count != count:
        print(0)
        exit()
tmp = (M//LCM)
if tmp % 2 == 0:
    tmp = tmp//2
else:
    tmp = tmp//2+1
print(tmp)

Submission status: Runtime Error

Solution code:
from fractions import gcd

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

def get_all_lcm(numbers):
    
    
    cache = {}
    value = 1
    for number in numbers:

        if not number in cache:
            value = lcm(value, number)
            cache[number] = 1
    return value

def logic(m, value):
    x, x_mod = divmod(m, value)
    y, y_mod = divmod(x, 2)

    answer = y + y_mod
    return int(m // value - 1) // 2 + 1 
def logic2(M, value):
    return int(M // value - 1) // 2 + 1

def main(print=__builtin__.print):
    n, m = [int(x) for x in input().rstrip("\n").split(" ")]

    numbers = [int(x) // 2 for x in input().rstrip("\n").split(" ")]

    evens = []

    for number in numbers:
        even = 0
        while number % 2 == 0:
            number //= 2
            even += 1
        evens.append(even)

    if max(evens) != min(evens):
        return 0
    
    cache = {}
    value = 1
    for number in numbers:

        if not number in cache:
            value = lcm(value, number)
            cache[number] = 1
    #print(value)
    answer = logic2(m, value)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from fractions import gcd

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

def get_all_lcm(numbers):
    
    
    cache = {}
    value = 1
    for number in numbers:

        if not number in cache:
            value = lcm(value, number)
            cache[number] = 1
    return value

def logic(m, value):
    """
    >>> logic(50, 15)
    2
    >>> logic(15, 15)
    1
    >>> logic(30, 15)
    1
    >>> logic(44, 15)
    1
    >>> logic(1000000000, 3)
    166666667
    """
    x, x_mod = divmod(m, value)
    y, y_mod = divmod(x, 2)

    answer = y + y_mod
    return int(m // value - 1) // 2 + 1 
def logic2(M, value):
    """
    >>> logic2(50, 15)
    2
    >>> logic2(15, 15)
    1
    >>> logic2(30, 15)
    1
    >>> logic2(44, 15)
    1
    >>> logic(1000000000, 3)
    166666667
    """
    return int(M // value - 1) // 2 + 1

def main(print=__builtin__.print):
    n, m = [int(x) for x in input().rstrip("\n").split(" ")]

    numbers = [int(x) // 2 for x in input().rstrip("\n").split(" ")]

    evens = []

    for number in numbers:
        even = 0
        while number % 2 == 0:
            number //= 2
            even += 1
        evens.append(even)

    if max(evens) != min(evens):
        return 0
    
    cache = {}
    value = 1
    for number in numbers:

        if not number in cache:
            value = lcm(value, number)
            cache[number] = 1
    #print(value)
    answer = logic2(m, value)
    print(answer)


if __name__ == '__main__':
    main()