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: Time Limit Exceeded

Solution code:
def lcm(x, y):
    return x * y // gcd(x, y)
def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)

def twos(x):
    m = 16
    ret = 0
    while True:
        if x % (1 << m) == 0:
            x = x >> m
            ret += m
        if m == 0:
            break
        m = m >> 1
    return ret

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

# check
p = twos(a[0])
for x in a:
    if twos(x) != p:
        print(0)
        exit()

l = lcm(b[0], b[0])
for x in b:
    l = lcm(l, x)

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

Submission status: Time Limit Exceeded

Solution code:
from math import floor
from fractions import gcd
N,M = map(int,input().split())

def prime_decomposition(n):
  i = 2
  d = {2:0}
  while i * i <= n:
    while n % i == 0:
      n //= i
      if i not in d:
          d[i] = 0
      d[i] += 1
    i += 1
  if n > 1:
    if n not in d:
        d[n] = 1
  return d
A = list(map(int,input().split()))
for i in range(N):
    A[i] //= 2

l = A[0]
for i in range(1,N):
    l = (l*A[i])//gcd(l,A[i])
ans = floor((M/l+1)/2)
n = prime_decomposition(l)[2]
p2 = 2**n
for i in range(N):
    if A[i]%p2 != 0:
        ans = 0
        break
print(ans)

Submission status: Time Limit Exceeded

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):
    return (x * y) // fractions.gcd(x, y)

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)
    else:
        print((M-r//2)//r+1)

Submission status: Time Limit Exceeded

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 = []
    C = []

    ok = True
    for a in A:
        c = 0
        while a%2 == 0:
            a //= 2
            c += 1
        B.append(a)
        if C:
            if c != C[-1]:
                ok = False
                break
        C.append(c)

    if not ok:
        print(0)
    else:
        g = 1
        for b in B:
            l = gcd(g, b)
            g = g*b//l
        p = g*2**(c-1)
        ans = (M+p)//(2*p)
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import fractions
 
N, M = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) // 2 for x in stdin.readline().rstrip().split()]
ans = 0
g = 1
 
for i in range(len(A)):
    g = g * A[i] // fractions.gcd(g, A[i])
 
for i in range(len(A)):
    if (g // A[i]) % 2 == 0:
        print(0)
        exit()
 
ans = M // g
if ans % 2 == 0:
    print(ans // 2)
else:
    print((ans + 1) // 2)

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce


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


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


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


hA = [a//2 for a in A]
lcm = lcm_list(hA)

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: Time Limit Exceeded

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

from fractions import gcd
from functools import reduce

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

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

lcm = lcm_list(ahs)

result = True
for ah in ahs:
    if (lcm // ah) % 2 == 0:
        result = False
        break

if result == False:
    print(0)
else:
    print((M//lcm-1)//2 + 1)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce
def lcm(a, b):
    return a*b//gcd(a,b)
def lcm_list(numbers):
    return reduce(lcm, numbers)
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
a = inpl()
b = list(map(lambda x: x//2, a))
L = lcm_list(b)
for i in range(N):
    if (L//b[i]) % 2 == 0:
        print(0)
        exit()
z = M // L
print((z+1)//2)

Submission status: Time Limit Exceeded

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

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

#a,bの最大公約数
def gcd(a, b):
   while b:
       a, b = b, a % b
   return a

#a,bの最小公倍数
def lcm(a, b):
   return a * b // gcd (a, b)


bl = [i//2 for i in al]
bl = sorted(bl, reverse=True)
ans = 1
for b in bl:
   ans = lcm(ans, b)

for a in al:
   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: Time Limit Exceeded

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()
import fractions
gcd=fractions.gcd
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=0

n,m=LI()
b=[int(i)//2 for i in input().split()]
#a=LI()

'''
s=time.time()
n=10**4
b=[random.randint(10,10**8) for i in range(n)]
t=time.time()
show(t-s)
'''

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

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

fl=False
for i in b:
    t=lcm//i
    if t%2==0:
        fl=True
    
if lcm%2==0 and fl:
    ans=0
    
    
print(ans)

Submission status: Time Limit Exceeded

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

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

#a,bの最大公約数
def gcd(a, b):
   while b:
       a, b = b, a % b
   return a

#a,bの最小公倍数
def lcm(a, b):
   return a * b // gcd (a, b)


bl = [i//2 for i in al]
bl = sorted(bl)
ans = 1
for b in bl:
   ans = lcm(ans, b)

for a in al:
   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: Time Limit Exceeded

Solution code:
from math import floor
N,M = map(int,input().split())
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
def prime_decomposition(n):
  i = 2
  d = {2:0}
  while i * i <= n:
    while n % i == 0:
      n //= i
      if i not in d:
          d[i] = 0
      d[i] += 1
    i += 1
  if n > 1:
    if n not in d:
        d[n] = 1
  return d
A = list(map(int,input().split()))
for i in range(N):
    A[i] //= 2

l = A[0]
for i in range(1,N):
    l = (l*A[i])//gcd(l,A[i])
ans = floor((M/l+1)/2)
n = prime_decomposition(l)[2]
p2 = 2**n
for i in range(N):
    if A[i]%p2 != 0:
        ans = 0
print(ans)

Submission status: Time Limit Exceeded

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

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

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

dame=0

for i in range(n):
    if i==0:
        swit=0
        wal=0
        now=alist[0]
        while swit==0:
            if now%2==0:
                now=now//2
                wal+=1
            else:
                swit=1
        kobai=alist[0]
        ruijo=2**wal
    else:
        if kobai%alist[i]!=0:
            kobai=lcm(kobai, alist[i])
            if not(alist[i]%ruijo==0 and alist[i]%(2*ruijo)!=0):
                dame=1
        else:
            if alist[i]%ruijo!=0:
                dame=1

if dame==0:
    answer=(m+kobai//2)//kobai
    print(answer)
else:
    print(0)

Submission status: Time Limit Exceeded

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

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

# return [g, x, y]
# g = gcd(a, b)
# x, y satisfies a x + b y = g
def extgcd(a, b):
    if b == 0:
        return [a, 1, 0]
    g, x, y = extgcd(b, a%b)
    return [g, y, x - a//b * y]

# eq0: x = a0 (mod m0)
# eq1: x = a1 (mod m1)
# returns [xt, mod] such that x = xt + k mod for integer k.
def crt(eq0, eq1):
    a0, m0 = eq0
    a1, m1 = eq1

    g = gcd(m0, m1)

    if a0 % g != a1 % g:
        return [0, -1]

    if g > 1:
        m0 //= g
        m1 //= g

        while True:
            gt = gcd(m0, g)
            if gt == 1:
                break
            m0 *= gt
            g //= gt
        
        m1 *= g

        a0 %= m0
        a1 %= m1

    g, p, q = extgcd(m0, m1)
    
    x = a0 * q * m1 + a1 * p * m0
    mod = m0 * m1
    x = x % mod

    return [x, mod]

sol = [0, 1]
for x in A:
  sol = crt(sol, [x + x // 2, x])
  if sol[1] < 0:
    break

res = 0
if sol[1] > 0 and sol[0] <= M:
  res = (M - sol[0]) // sol[1] + 1

print(res)

Submission status: Time Limit Exceeded

Solution code:
def lcm(x, y):
    return x * y // gcd(x, y)
def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)

def twos(x):
    l = 0
    r = 32
    while r - l > 1:
        if x % (2 ** ((l + r) // 2)) == 0:
            l = (l + r) // 2
        else:
            r = (l + r) // 2
    return l

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

# check
p = twos(a[0])
for x in a:
    if twos(x) != p:
        print(0)
        exit()

l = lcm(b[0], b[0])
for x in b:
    l = lcm(l, x)

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

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce
from math import ceil


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


N, M = map(int, input().split())
A = list(map(lambda x: int(x) // 2, input().split()))
l = reduce(lcm, A)
for a in A:
    if l // a % 2 == 0:
        print(0)
        exit()
ans = ceil((M // l) / 2)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
a = list(map(lambda x:int(x)//2, input().split()))
from fractions import gcd
from functools import reduce
import numpy as np
def lcm(x,y):
  return (x*y)//gcd(x,y)
l = reduce(lcm, a)
a = np.array(a)
if l > m:
  print(0)
elif np.all((l//a)%2!=0):
  print(1+(m-l)//(2*l))
else:
  print(0)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

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

@lru_cache(maxsize=1000)
def gcd(n,m):
    while n:
        m,n = [n,m%n]
    return m

su = 1
for b in B:
    su = su * b // gcd(su,b)

for b in B:
    if (su // b) % 2 == 0:
        print(0)
        exit()

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

Submission status: Time Limit Exceeded

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

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

a = sorted(list(set(a)))

owa = 0
saiko = a[0]//2

for i in range(1,len(a)):
    t1 = a[i]//2
    koe = gcd(saiko,t1)
    saiko = (saiko*t1)//koe

for i in range(len(a)):
    check = saiko//(a[i]//2)
    if check%2 == 0:
        owa = 1
        
if owa == 1:
    print(0)
else:
    if (M//saiko)%2 == 0:
        print((M//saiko)//2 )
    else:
        print(((M//saiko)+1)//2)

Submission status: Time Limit Exceeded

Solution code:
n,m=[int(i) for i in input().split()]
l=[int(i) for i in input().split()]

ll=[]
for i in range(1,m+1):
  for j in l:
    if i%j==j//2:
      ll.append(i)
lll=[i for i in ll if ll.count(i)==n]
print(len(set(lll)))

Submission status: Time Limit Exceeded

Solution code:

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

def gcd(a,b):
    if a < b:
        a, b = b, a
    while  a % b != 0:
        a, b = b, a % b
    return b
def lcm(c,d):
    return c*d // gcd(c,d)
# half all the array
A = set([a//2 for a in aa])
# calc lcm of all
LCM = 1
for each in A:
    LCM = lcm(LCM, each)
for each in A:
    if (LCM // each) % 2 == 0:
        print(0)
        break
else:
    print(m//LCM - m//(LCM*2))

Submission status: Time Limit Exceeded

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

count = 0
for i in range(1, m+1):
    for j in a:
        if i % j == j/2:
            pass
        else:
            break
    else:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

import sys
input = sys.stdin.readline

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

B = []
C = []

for a in A:
    c = 0
    while a%2 == 0:
        a //= 2
        c += 1
    B.append(a)
    C.append(c)

ok = True
for i in range(N-1):
    if C[i] != C[i+1]:
        ok = False
if not ok:
    print(0)
else:
    g = 1
    for b in B:
        l = gcd(g, b)
        g = g*b//l
    p = g*2**(c-1)
    ans = (M+p)//(2*p)
    print(ans)

Submission status: Time Limit Exceeded

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

for i in range(1,M+1):
   for s in range(N):
      x=i/A[s]
      if x%1!=0.5:
        break
      if s==N-1:
        a=a+1
print(a)

Submission status: Time Limit Exceeded

Solution code:
import math
import sys

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

def f(n):
    return int(n)//2

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


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


for i in range(n):
    if (tmp//a[i])%2==0:
        print(0)
        sys.exit()

ans=m//(tmp*2)
if m%(tmp*2)>=tmp: ans+=1
print(ans)

Submission status: Time Limit Exceeded

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

Asp = []
for a in As:
    Asp.append(a // 2)


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


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


import functools

l = functools.reduce(lcm, Asp)

fg = False
for a in Asp:
    if (l // a) % 2 == 0:
        fg = True
        break

if fg:
    print("0")
else:
    print(M // l - M // (l * 2))

Submission status: Time Limit Exceeded

Solution code:
n,h=map(int, input().split())

l=list(map(int, input().split()))
count=0
semicount=0
for i in range(h+1):
    if ((i/l[0])*10)%10==5:
        for x in l:
            if ((i / x) * 10) % 10 == 5:
                semicount+=1
            else:
                break

        if semicount==n:
            count+=1
        semicount=0

print(count)

Submission status: Time Limit Exceeded

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

def gcd(n,m):
    while n:
        m,n = [n,m%n]
    return m

su = 1
for b in B:
    su = su * b // gcd(su,b)

for b in B:
    if (su // b) % 2 == 0:
        print(0)
        exit()

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

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

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

maybe=set([i+1 for i in range(M)])

for ai in a:
    max=int(M/ai -0.5)+3
    maybe2=set([int(ai*(p+0.5)) for p in range(max)])
    maybe=maybe&maybe2

print(len(maybe))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

def calc_lcm(a, b):
	gcm = calc_gcm(a, b)
	return a * b // gcm

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

lcm = 1
for a in a_list:
	lcm = calc_lcm(lcm, a)

def check():
	for a in a_list:
		if (lcm // a) % 2 == 0:
			return False
	return True

if check():
	lcm //= 2
	count = M // lcm + 1
	print(count // 2)
else:
	print(0)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from fractions import gcd
def lcm(x,y):
    return x*y//gcd(x,y)
def lcmm(l):
    return reduce(lcm,l)
n,m=map(int,input().split())
A=list(map(int,input().split()))
l=lcmm(A)
if l%2==1:
    print(0)
    exit()
for a in A:
    if (l//a)%2==0:
        print(0)
        exit()
print(int(m/l+1/2))

Submission status: Time Limit Exceeded

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

def div2(n):
    count=0
    while n%2!=1:
        count+=1
        n//=2
    return count

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

b = [div2(a[i]) for i in range(N)]

flag = True

for i in range(1,N):
    if b[i]!=b[0]:
        flag=False
        break

if flag:
    l = a[0]//2
    for i in range(1,N):
        l = (l*a[i]//2)//gcd(l,a[i]//2)
    print((M+l)//(2*l))
else:
    print(0)

Submission status: Time Limit Exceeded

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

def lcm(a, b):
    g = gcd(a, b)
    g_a = a // g
    g_b = b // g
    return g_a * g_b * g

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



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

num = 1
for i in range(n):
    num = lcm(num, b[i])

for i in range(n):
    if (num // b[i]) % 2 == 0:
        print(0)
        exit()

if num > m:
    print(0)
    exit()

p = m // num
if p % 2 == 0:
    print(p//2)
else:
    print((p+1)//2)

Submission status: Time Limit Exceeded

Solution code:
def lcm(x, y):
    return x * y // gcd(x, y)
def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)

def twos(x):
    i = 0
    while x % 2 == 0:
        x //= 2
        i += 1
    return i

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

# check
p = twos(a[0])
for x in a:
    if twos(x) != p:
        print(0)
        exit()

l = lcm(b[0], b[0])
for x in b:
    l = lcm(l, x)

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

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
n,m = map(int,input().split())
a = list(map(int,input().split()))
cnt = 0
while(True):
  flg = 0
  for i in range(n):
    if a[i]%2 == 0:
      if flg == 0:
        flg = 1
    if flg and a[i]%2:
      print(0)
      exit()
  if flg:
    a = [i//2 for i in a]
  else:
    break
  cnt += 1
lcm = a[0]
for i in range(n-1):
  lcm =a[i+1]*lcm//gcd(a[i+1],lcm)
print((m//(lcm*2**(cnt-1))+1)//2)

Submission status: Time Limit Exceeded

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

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

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

s=div2(A[0])
chk=True

mul=A[0]
for i in range(1,n):
  if s!=div2(A[i]):
    chk=False
  mul=mul*A[i]//gcd(mul,A[i])
if not chk:
  print(0)
else:
  print(m//mul-m//(mul*2))

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
A = list(map(int,input().split()))
g = A[0]
l = A[0]
import fractions
for i in range(1,N):
    a = A[i]
    g = fractions.gcd(l,a)
    l = l*a//g
b = l//2
f = (M-b)//l + 1
for i in range(N):
    if b%A[i] == 0:
        f = 0
        break
if M < l//2:
    ans = 0
else:
    ans = f
print(ans)

Submission status: Time Limit Exceeded

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

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

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

dame=0

for i in range(n):
    if i==0:
        swit=0
        wal=0
        now=alist[0]
        while swit==0:
            if now%2==0:
                now=now//2
                wal+=1
            else:
                swit=1
        kobai=alist[0]
        ruijo=2**wal
    else:
        if kobai%alist[i]!=0:
            kobai=lcm(kobai, alist[i])
        if not(alist[i]%ruijo==0 and alist[i]%(2*ruijo)!=0):
            dame=1

if dame==0:
    answer=(m+kobai//2)//kobai
    print(answer)
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
import fractions

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

for i in range(N):
    A[i] //= 2
    
num = 1
for i in range(N):
    num = num*A[i]//fractions.gcd(num, A[i])
    
f = 0
for i in range(N):
    if (num//A[i])%2 == 0:
        f = 1
        break
        
if f == 0 and M >= num:
    ans = 1
    M -= num
    ans += M//(2*num)
    print(ans)
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
import fractions
import math
#gcd = math.gcd
gcd = fractions.gcd
n, m = [int(_) for _ in input().split()]
a = sorted([int(_) // 2 for _ in input().split()])
lcm = a[0]
for i in range(1, n):
    lcm = lcm * a[i] // gcd(lcm, a[i])
for b in a:
    if (lcm // b) % 2 == 0:
        print(0)
        exit()
ans = m // lcm
if ans % 2 == 0:
    ans -= 1
print(ans // 2 + 1)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]

from fractions import gcd
n, m = map(int, input().split())
a = list(map(int, input().split()))
m *= 2

if n == 1:
	print((m//a[0]+1)//2)
else:
	lcm = a[0]*a[1]//gcd(a[0], a[1])
	for i in range(2, n):
		lcm = lcm * a[i] // gcd(lcm, a[i])

	divs = 0
	for x in a:
		divs += (lcm//x)%2
	if divs < n:
		print(0)
	else:
		print((m//lcm+1)//2)

Submission status: Time Limit Exceeded

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



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

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

dame=0

for i in range(n):
    if i==0:
        swit=0
        wal=0
        now=alist[0]
        while swit==0:
            if now%2==0:
                now=now//2
                wal+=1
            else:
                swit=1
        kobai=alist[0]
    else:
        if kobai%alist[i]==0:
            if alist[i]%(2**wal)==0 and alist[i]%(2**(wal+1))!=0:
                pass
            else:
                dame=1
        else:
            kobai=lcm(kobai, alist[i])
            if alist[i]%(2**wal)==0 and alist[i]%(2**(wal+1))!=0:
                pass
            else:
                dame=1

#print(kobai, dame)
if dame==0:
    answer=(m+kobai//2)//kobai
    print(answer)
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
n, m = map(int, input().split())
a = list(map(int, input().split()))
m *= 2

if n == 1:
	print((m//a[0]+1)//2)
else:
	lcm = a[0]*a[1]//gcd(a[0], a[1])
	for i in range(2, n):
		lcm = lcm * a[i] // gcd(lcm, a[i])

	divs = sum([(lcm//x)%2 for x in a])
	if divs < n:
		print(0)
	else:
		print((m//lcm+1)//2)

Submission status: Time Limit Exceeded

Solution code:
def GCD(a: int, b: int) -> int:
    return a if b == 0 else GCD(b, a % b)


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


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

a_lcm = a[0]
for i in range(1, n):
    a_lcm = LCM(a_lcm, a[i])

flag = True
for i in range(n):
    if (a_lcm // a[i]) % 2 == 0:
        flag = False
        break

if flag:
    ans = ((m // a_lcm) + 1) // 2
else:
    ans = 0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
def main():
    N, M = [int(n) for n in input().split()]
    A = [int(n)//2 for n in input().split()]
    lcm = A[0]
    for a in A:
        lcm = lcm //gcd(lcm, a) * a
    # print(lcm)
    flg = False
    for a in A:
        if (lcm // a) % 2 == 0:
            flg = True
            break
    if flg:
        print(0)
    else:
        print((M // lcm+1)//2)
main()

Submission status: Time Limit Exceeded

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

import sys
sys.setrecursionlimit(300000)


def solve(N: int, M: int, a: "List[int]"):
    def gcd(a, b):
        return a if b == 0 else gcd(b, a % b)
    g = a[0]
    for v in a:
        tmp = gcd(g, v)
        g = g * v // tmp
    for v in a:
        if (g // v) % 2 == 0:
            print(0)
            return
    if M - (g // 2) < 0:
        print(0)
        return
    M -= g // 2
    ret = M // g + 1
    print(ret)
    return

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: Accepted

Solution code:
import math
N, M = map(int, input().split())
nums = list(map(int, input().split()))
lcm = 1
b_cnt = -1
for num in nums:
  lcm = lcm*(num//2)//math.gcd(lcm, num//2)
  count = 0
  while num%2 == 0:
    count += 1
    num //= 2
  if b_cnt < 0:
    b_cnt = count
  elif count != b_cnt:
    print(0)
    exit()
print((M+lcm)//(lcm*2))

Submission status: Accepted

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**6)
import itertools
import bisect
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    n,M = i_map()
    a = i_list()

    cd = []
    new_a = []
    for i in a:
        cd.append(i//2)
        new_a.append((i//2))

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

    P = []
    for a in new_a:
        P.append(pow2(a))

    if len(set(P)) != 1:
        print(0)
    else:
        m = 1
        for a in new_a:
            m = (m*a)//gcd(m,a)
        print(-(-(M//m)//2))









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, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
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()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = 10**6#float('inf')
#mod = 10 ** 9 + 7 
mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, M = MAP()
a = LIST()

A = sorted([x//2 for x in a], reverse=True)

lcm = A[-1]
for x in A:
	lcm = lcm*x//gcd(lcm, x)

r = lcm//A[0]
n = M//A[0]


for x in A:
	if lcm//x%2 == 0:
		print(0)
		exit()
#2p+1が1<=2p+1<=n の範囲で rの倍数となるpの個数
if r%2 == 0:
	print(0)
else:
	print(n//r - n//(2*r))