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

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

        koubaisu = koubaisu * i // gcd(koubaisu, i)

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

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


    return


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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

count = 0
check = True
for k in range(0,N):
    if A[k] % 2 != 0:
        check = False
if check:
    for X in range(1,M+1):
        check = True
        for k in range(0,N):
            if not ((X-A[k]//2)%A[k] == 0 and (X - A[k]//2)//A[k] >= 0):
                check = False
                break
        if check:
            count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import math
import fractions
from functools import reduce

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

def lcm_list(numbers):
    return reduce(lcm, numbers)

n, m = map(int, input().split())
a_list = sorted(set(map(int, input().split())))
element = 0
for i in range(1, m + 1):
    if all(i / a - math.floor(i / a) == 0.5 for a in a_list):
        element = i
        break
lcm = lcm_list(a_list)
if element == 0:
    print(0)
else:
    print((m - element) // lcm + 1)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = []
for i in range(n):
	b.append(a[i]//2)

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

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

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

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

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

Submission status: Time Limit Exceeded

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

def con(l):
  ans = 0
  while l%2 == 0:
    ans += 1
    l = l//2
  return ans

lis = []    
for i in range(n):
  lis.append(con(a[i]))
  if i >= 1:
    if lis[i-1] != lis[i]:
      print(0)
      exit()

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)

aaa = lcm_list(a)//2
print(1+(m-aaa)//(aaa*2))

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


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)
i = 2
while l & (i - 1) == 0:
    i *= 2
i = i // 2 - 1

fg = False
if i > 0:
    for a in Asp:
        if a & i > 0:
            fg = True
            break

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri Jan 10 21:59:40 2020

@author: over-
"""

def SMC(A,X):
    bool=True
    for a in A:
        if X-int(a)/2 < 0: 
            bool=False
            break
        if (X-int(a)/2)%int(a) != 0: 
            bool=False
            break
    return bool

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

c=0
for n in range(1,M+1):
    if SMC(A,n): c+=1
    
print(c)

Submission status: Time Limit Exceeded

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return [int(x) for x in sys.stdin.readline().split()]

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

def calc(a,b):
    count_two_a = 0
    count_two_b = 0
    while(a%2==0):
        a //= 2
        count_two_a += 1
    while(b%2==0):
        b //= 2
        count_two_b += 1
    if count_two_a != count_two_b:
        return 0

    return pow(2,count_two_a) * a * b // GCM(a,b)





def main():
    N,M = LI()
    A = LI()

    count_two = 0
    while(A[0]%2==0):
        A[0] //= 2
        count_two += 1
    pow_two = pow(2,count_two)

    for i in range(1,N):
        if A[i]%pow_two != 0:
            print(0)
            return
        A[i] //= pow_two
        if A[i]%2 == 0:
            print(0)
            return

    gcm = A[0]

    for i in range(1,N):
        gcm = calc(gcm,A[i])

    ans = M//(gcm*pow_two//2)
    if ans%2==0:
        ans -= 1
    ans -= ans//2
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def extended_gcd(a, b):
    """returns gcd(a, b), s, r s.t. a * s + b * r == gcd(a, b)"""
    s, old_s = 0, 1
    r, old_r = b, a
    while r:
        q = old_r // r
        old_r, r = r, old_r - q * r
        old_s, s = s, old_s - q * s
    return old_r, old_s, (old_r - old_s * a) // b if b else 0


def gcd(x, y):
    """greatest common divisor of x and y"""
    while y:
        x, y = y, x % y
    return x


lcm = lambda a, b: a * b // gcd(a, b)


def main():
    n, m = map(int, input().split())
    a = [int(i) for i in input().split()]

    x = 0
    p = 1

    for i in a:
        g, s, _ = extended_gcd(p, i)
        if (((i // 2) % g) - (x % g)) % g:
            print(0)
            return
        x += ((i // 2) - x) // g * s * p
        p = lcm(p, i)

    x %= p

    if x <= m:
        print((m - x) // p + 1)
    else:
        print(0)


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
A=list(map(int,input().split()))
if n==1:
    ans=(m//(A[0]//2)+1)//2
    print(int(ans))
    exit()
from fractions import gcd
kou=A[0]*A[1]//gcd(A[0],A[1])
for a in A:
    kou=a*kou//gcd(a,kou)
for a in A:
    if (kou//a)%2==0:
        print(0)
        exit()
kou//=2
#print(kou)
ans=(m//kou+1)//2
print(int(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()))

bl = [i//2 for i in al]
from fractions import gcd
ans = 1
for b in bl:
   ans = (ans * b) // gcd(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:
import fractions

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

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

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

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

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

Submission status: Time Limit Exceeded

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

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

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


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

for a in A:
  if (now // a) % 2 == 0:
    now = 0
    print(0)
    break
else:
  cm_num = M // now
  print(cm_num // 2 + int(cm_num % 2 == 1))

Submission status: Time Limit Exceeded

Solution code:
import fractions
N,M=map(int, input().split())
A = [int(a) for a in input().split()]
A2 = [a//2 for a in A]

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

B = sum([1 for a in A if lcm%a==0])
if B>0:
    print(0)
else:
    print((M//lcm+1)//2)

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import Counter
N,M = map(int,input().split())
a = list(map(int,input().split()))
lcm = 0
flag = False
for i in range(1,M+1):
    if flag:
        break
    for j in range(N):
        if flag:
            break
        tmp = i/a[j]
        if int(tmp)+0.5 != tmp:
            break
        if int(tmp)+0.5 == tmp and j == N-1:
            lcm = i
            flag = True
if lcm == 0:
    print(0)
else:
    ans = M/lcm
    print(math.ceil(math.floor(ans)/2))

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
import sys
from fractions import gcd
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = True

def index(a,b):
    return str(min(a,b)) + "," +  str(max(a, b))

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

    koubaisu = 1
    for i in a:
        koubaisu = koubaisu * (i // 2) // gcd(koubaisu, i//2)

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

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




if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy

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 = numpy.array(list(map(int, input().split())))

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

a = a // (2 ** p)
l = a[0]
for x in a[1:]:
    l = lcm(l, x)

l *= (1 << (p - 1))

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

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]

def main():
    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

    def lcd(a):
        if len(a)==2:
            return (a[0]*a[1])//gcd(a[0],a[1])
        elif len(a)==1:
            return a[0]
        else:
            x = lcd(a[:len(a)//2])
            y = lcd(a[len(a)//2:])
            return (x*y)//gcd(x,y)


    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:
        for i in range(N):
            a[i]=a[i]//2
        l = lcd(a)
        print((M+l)//(2*l))
    else:
        print(0)



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


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


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


y = lcm_list(a)

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

x = m//y
if x % 2 == 0:
    print(x//2)
else:
    print((x+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()))




bl = [i//2 for i in al]
from fractions import gcd
ans = 1
for b in bl:
   ans = (ans * b) // gcd(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 fractions import gcd

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

def div2(a):
  n = 0
  while True:
    if a & 1 > 0:
      return n

    a = a >> 1
    n += 1

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

if len(set(map(div2, a))) != 1:
  print(0)
  exit(0)

m_lcm = lcm([i // 2 for i in a])
if m_lcm > m:
  print(0)
  exit(0)

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

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
def gcd( x, y ):
    while y != 0:
        x, y = y, x%y
    return x
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:
N, M = map(int, input().split())
As = list(map(int, input().split()))

Asp = []
for a in As:
    Asp.append(a >> 1)


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) & 1 == 0:
        fg = True
        break

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

Submission status: Time Limit Exceeded

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return [int(x) for x in sys.stdin.readline().split()]

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

def calc(a,b):
    count_two_a = 0
    count_two_b = 0
    while(a%2==0):
        a //= 2
        count_two_a += 1
    while(b%2==0):
        b //= 2
        count_two_b += 1
    if count_two_a != count_two_b:
        return 0

    return pow(2,count_two_a) * a * b // GCM(a,b)





def main():
    N,M = LI()
    A = LI()

    tmp = A[0]

    for i in range(1,N):
        tmp = calc(tmp,A[i])
        if tmp==0:
            print(0)
            return
    tmp = tmp//2

    ans = M//tmp
    if ans%2==0:
        ans -= 1
    ans -= ans//2
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
def gcm(a,b):
    if b == 0:
        return a
    if a<b:
        a,b=b,a
    return gcm(b, a%b)

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

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

l = reduce(lcm,b)

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

Submission status: 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], 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 math
import numpy as np
def is_makable(candidate, origin):
  judge = candidate/origin
  if round(judge - int(judge), 1) == 0.5:
    return 1
  else:
    return 0
 
last_candidate = int(input().split()[1])
num_q = input().split()
count = 0
for i in range(1, last_candidate+1, 1):
  if np.prod([is_makable(i, int(n)) for n in num_q]):
    count += 1
print(count)

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]
from fractions import gcd
ans = 1
for b in bl:
   ans = (ans * b) // gcd(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:
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

def lcd(a):
    if len(a)==2:
        return (a[0]*a[1])//gcd(a[0],a[1])
    elif len(a)==1:
        return a[0]
    else:
        x = lcd(a[:len(a)//2])
        y = lcd(a[len(a)//2:])
        return (x*y)//gcd(x,y)


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:
    for i in range(N):
        a[i]=a[i]//2
    l = lcd(a)
    print((M+l)//(2*l))
else:
    print(0)

Submission status: Time Limit Exceeded

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

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

        koubaisu = koubaisu * (i // 2) // gcd(koubaisu, i//2)

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

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


    return


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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,M = list(map(int,input().split()))
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

a = list(map(int,input().split()))
count2 = set()
for i in a:
    prime = prime_factorize(i)
    count2.add(prime.count(2))
if (len(count2) == 1) and (0 not in count2):
    a2 = [int(i//2) for i in a]
    if len(a2) == 1:
        div = M//a2[0]
        print((div+1)//2)
    else:
        gcda = a2[0]*a2[1]//gcd(a2[0],a2[1])
        for i in range(2,N):
            gcda = gcda*a2[i]//gcd(gcda,a2[i])
        div = M//gcda
        print((div+1)//2)
    
else:
    print(0)

Submission status: Time Limit Exceeded

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

hankobai = 0

for i in range(M):
  hasuu = 0
  for j in range(N):
    hasuu = hasuu + (((i+1)/a[j] - 0.5) % 1)
  if hasuu == 0:
    hankobai += 1

print(hankobai)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

R = lambda: map(int, input().split())

n, m = R()
a = [x // 2 for x in R()]
x = a[0]
for y in a:
  x = x * y // gcd(x, y)
  
print(m // x - m // (2 * x) if all(x // y % 2 for y in a) else 0)

Submission status: Time Limit Exceeded

Solution code:
inputs = input().split(" ")
n = int(inputs[0])
m = int(inputs[1])
a = input().split(" ")
for i in range(0, n):
    a[i] = int(a[i])
result = []
for i in range(1, m+1)[::2]:
    result.append(i)

for i in a:
    j = 0
    while j < len(result):
        tmp = result[j]/i-0.5
        if not float.is_integer(tmp) or tmp < 0:
            result.pop(j)
            j -= 1
        j += 1

print(len(result))

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
    a = A[0]
    c = 0
    while a%2 == 0:
        a //= 2
        c += 1
    
    p = 2**c

    for a in A:
        if a % p == 0 and a % (2*p) != 0:
            B.append(a//p)
        else:
            ok = False
            break
    if not ok:
        print(0)
    else:
        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 fractions import gcd
from functools import reduce

def gcd_list(numbers):
    return reduce(gcd, numbers)
  
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(lambda x: int(x)//2, input().split()))
g = gcd_list(A)
l = lcm_list(A)
if (l//g)%2 == 0:
  print(0)
else:
  print(((m//l)+1)//2)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
a = inpl()
b = list(map(lambda x: x//2, a))
L = 1
for c in b:
    g = gcd(L, c)
    L *= c//g
for c in b:
    if (L//c) % 2 == 0:
        print(0)
        exit()
z = M // L
print((z+1)//2)

Submission status: Time Limit Exceeded

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

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

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

    for _ in filter(lambda x:(su//x)%2==0,B):
        return 0

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

print(a())

Submission status: Time Limit Exceeded

Solution code:
import fractions
n,m = map(int,input().split())
a = list(map(int,input().split()))
b = 1
c = 0
key = 1
key1 = 1
l = []
while key == 1:
    if a[0] % b == 0:
        b *= 2
        c += 1
    else:
        b //= 2
        c -= 0
        key = 0
for i in range(n):
    if a[i] % b == 0:
        if (a[i]//b) % 2 == 0:
            key1 = 0
            break
        else:
            l.append(a[i]//b)
    else:
        key1 = 0
        break
if key1 == 0 or c == 0:
    print(0)
else:
    d = l[0]
    for i in range(1,n):
        d = d* l[i]// fractions.gcd(d,l[i])
    d = d*b//2
    if (m//d)%2 == 0:
        print((m//d)//2)
    else:
        print((m//d)//2+1)

Submission status: Time Limit Exceeded

Solution code:
import fractions

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

def main():
    n,m = map(int, input().split())
    A = list(map(int,input().split()))

    pool = set([])
    for i in range(n):
        tmp = [A[i]/2+A[i]*x for x in range(int((m-A[i]/2)//A[i])+1)]
        if i == 0:
            pool =  set(tmp)
            continue
        pool = pool & set(tmp)
    print(len(pool))


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

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

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

        koubaisu = lcm(koubaisu, i//2)

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

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


    return


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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def gcd(a: int, b: int) -> int:
    """a, bの最大公約数(greatest common divisor:GCD)を求める
    計算量: O(log(min(a, b)))
    """
    if b == 0:
        return a
    return gcd(b, a%b)


def lcm(a, b):
    """a, bの最小公倍数(least common multiple:LCM)を求める
    計算量: O(log(min(a, b)))"""
    return (a * b) // gcd(a, b)

             
def multi_lcm(array):
    """arrayのLCMを求める"""
    ans = array[0] 
    for i in range(1, len(array)):
        ans = (ans * array[i]) // gcd(ans, array[i])
    return ans 

import sys
input = sys.stdin.readline

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

l = [0] * n
for i in range(n):
    cnt = 0
    tmp = a[i]
    while True:
        if tmp % 2 == 0:
            cnt += 1
            tmp //= 2
        else:
           break
    l[i] = cnt
if max(l) != min(l):
    print(0)
    exit()
    
div = multi_lcm(a)
ans = 0
if m - div // 2 >= 0:
    ans += 1
m = m - div // 2 
ans += m // div
if m < 0:
    print(0)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
a = list(map(int,input().split()))
li=[]
for i in range(n):
    s = set()
    l = 1
    k = a[i]/2
    while True:
        if(k*l>m):
            break
        s.add(k*l)
        l+=2
    li.append(s)
for i in range(n):
    s = s & li[i]
print(len(s))