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:
import fractions


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


def calc(n, m):
    for i in range(cycle//m+1):
        X = m * (i + 0.5)
        flag = True
        for x in n:
            if (X - x // 2) % x != 0:
                flag = False
                break
        if flag:
            return int(X)
    return -1


N, M = map(int, input().split())
A = list(map(int, input().split()))
cycle = 1
ma = 0
for a in A:
    cycle = lcm(cycle, a)
    ma = max(ma, a)
start = calc(A, ma)

if start == -1:
    print(0)
else:
    print((M - start) // cycle + 1)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
def factorization(n):
    arr={}
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr[i]=cnt
    if temp!=1:
        arr[temp]=1
    if arr==[]:
        arr[n]=1
    return arr
b=factorization(a[0])[2]
for i in range(1,n):
  if b==factorization(a[i])[2]:
    continue
  else:
    print(0)
    exit(0)
from fractions import gcd
lcmn=a[0]//2
for i in range(1,n):
    lcmn=(lcmn*a[i]//2)//gcd(lcmn,a[i]//2)
print((1+m//lcmn)//2)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
import fractions

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


def first(A):
    for k in range(max(A)//2,M+1,max(A)):
        if set(map(lambda x: k%x == x//2, set(A))) == {True}:
            return k
    return -1

def lcm(numbers):
    if len(numbers) ==1:
        return numbers[0]
    return reduce(lambda x,y: (x*y)// fractions.gcd(x,y), numbers,1)

f = first(A)
ans = (M-f) // lcm(A) + 1
if f== -1:
    ans = 0

print(ans)

Submission status: Time Limit Exceeded

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

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

a.sort(reverse=True)


a_com=[int(a[0]*(i+0.5)) for i in range(m//a[0]+1) if a[0]*(i+0.5)<=m]


ans=1

for i in range(len(a)-1):
    a_i=[int(a[i+1]*(j+0.5)) for j in range(m//a[i+1]+1+1) if a[i+1]*(j+0.5)<=m]

    com=set(a_com)&set(a_i)
    a_com=list(com)

    
    if a_com==[]:
        print(0)

        ans=0
        break
        
if ans==1:
    print(len(a_com))

Submission status: Time Limit Exceeded

Solution code:

def factorization(n):
    arr = {}
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr[i] = cnt

    if temp!=1:
        arr[temp] = 1

    if not arr:
        arr[n] = 1

    return arr


n, m = map(int, input().split())
a = list(map(int, input().split()))
# a2 = [num//2 for num in a]
acount = [None]*n # aを2で割れる回数
anum = [None]*n # 割ったあとの残り(=奇数)
for i,num in enumerate(a):
    c = 0
    while num%2==0:
        num //=2
        c += 1
    acount[i] = c
    anum[i] = num
if all(item==acount[0] for item in acount):
    cc = {}
    for num in anum:
        tmp = factorization(num)
        for k,v in tmp.items():
            if k in cc:
                cc[k] = max(cc[k], v)
            else:
                cc[k] = v
    num = 1
    for k,v in cc.items():
        num *= pow(k,v)
    num0 = num * (pow(2, (acount[0]-1)))
    span = num0*2
    if m<num0:
        print(0)
    else:
        print(int((m-num0)//span + 1))
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:


def factorization(n):
    arr = {}
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr[i] = cnt

    if temp!=1:
        arr[temp] = 1

    if not arr:
        arr[n] = 1

    return arr


n, m = map(int, input().split())
a = list(map(int, input().split()))
# a2 = [num//2 for num in a]
acount = [None]*n # aを2で割れる回数
anum = [None]*n # 割ったあとの残り(=奇数)
for i,num in enumerate(a):
    c = 0
    while num%2==0:
        num //=2
        c += 1
    acount[i] = c
    anum[i] = num
if all(item==acount[0] for item in acount):
    cc = {}
    for num in anum:
        tmp = factorization(num)
        for k,v in tmp.items():
            if k in cc:
                cc[k] = max(cc[k], v)
            else:
                cc[k] = v
    num = 1
    for k,v in cc.items():
        num *= (k**v)
    num0 = num * (2**(acount[0]-1))
    span = num0*2
    if m<num0:
        print(0)
    else:
        print(int((m-num0)//span + 1))
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
a = [int(i) for i in input().split()]
a = sorted(list(set(a)))
from fractions import gcd
lc = a[0]
if n != 1:
  for num,i in enumerate(a[1:]):
    if lc == 0:
      break
    lc = lc * i // gcd(lc, i)
    if gcd(lc, i) == min(i,lc):
      for j in a[:num+1]:
        z = i//j
        if z == i/j and z%2 == 0:
          lc = 0
          break 
if lc == 0:
  print(0)
else:
  print((m+lc//2)//lc)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
a = [int(i) for i in input().split()]
a = sorted(list(set(a)))
from fractions import gcd
lc = a[0]
if n != 1:
  for num,i in enumerate(a[1:]):
    if lc == 0:
      break
    lc = lc * i // gcd(lc, i)
    if gcd(lc, i) == min(i,lc):
      for j in a[:num+1]:
        z = i//j
        if z == i/j and z%2 == 0:
          lc = 0
          break 
if lc == 0:
  print(0)
else:
  print((m+lc//2)//lc)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n,m=map(int,input().split())
l=set(map(int,input().split()))
l=[i/2 for i in l]

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

if len(l)==1:
  lcm=l.pop()
  if (m//lcm)%2==0:
    print(int((m//lcm)/2))
  else:
    print(int((m//lcm+1)/2))
  exit()
  
lcm=1
for a in l:
  d=gcd(lcm,a)
  lcm=d*(a/d)*(lcm/d)
  
if lcm>m:
  print(0)
  exit()
  
for a in l:
  if (lcm/a)%2==0:
    print(0)
    break
else:
  if (m//lcm)%2==0:
    print(int((m//lcm)/2))
  else:
    print(int((m//lcm+1)/2))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n,m=map(int,input().split())
l=list(map(int,input().split()))
l=[i/2 for i in l]
  
def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a

s=set(l)
l=set(l)

if len(l)==1:
  lcm=l.pop()
  if (m//lcm)%2==0:
    print(int((m//lcm)/2))
  else:
    print(int((m//lcm+1)/2))
  exit()
a1=l.pop()
a2=l.pop()
g=gcd(a1,a2)
lcm=g*(a1/g)*(a2/g)
d=1

while l:
  a=l.pop()
  d=gcd(lcm,a)
  lcm=d*(a/d)*(lcm/d)
  
if lcm>m:
  print(0)
  exit()
  
for a in s:
  if (lcm/a)%2==0:
    print(0)
    break
else:
  if (m//lcm)%2==0:
    print(int((m//lcm)/2))
  else:
    print(int((m//lcm+1)/2))

Submission status: Time Limit Exceeded

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

d=[]

def X(a,p):
  x=int(a*(p+0.5))
  return x

for i in A:
  p=0
  s=0
  dd=[]
  while s<=M:
    s=X(i,p)
    if s>M:
      continue
    else:
      dd.append(s)
      p+=1
  d.append(dd)

count=0

for i in d[-1]:
  c=0
  for j in d:
    if i not in j:
      c=1
      break
  if c==0:
    count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
a = list(map(int,input().split()))
from fractions import gcd
def lcm(x,y):
  return x*y // gcd(x, y)
q = a[0]//2
for i in range(n):
  a[i] = a[i]//2
  q = lcm(q,a[i])

cnt = 0
flag = 1
while flag:
  for i in range(n):
    if a[i] % 2 == 1:
      cnt += 1
    else:
      a[i]//1
    if cnt != 0:
      flag = 0
ans = (m//q) - (m//(2*q))
if cnt == n:
  print(ans)
else:
  print(0)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,M = map(int,input().split())

a = np.array( list(map(int,input().split())) )

count = 0

for c in range(1,M+1):
    b = c - a*0.5
    b = b % a
    if sum(b) == 0:
        count += 1

print(count)

Submission status: Time Limit Exceeded

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

X = [a / 2 for a in A]
c = 0
for m in range(1, M + 1):
    if [m % a for a in A] == X:
        c += 1
print(c)

Submission status: Time Limit Exceeded

Solution code:
n, m = (int(x) for x in input().split())
a = list(map(int, input().split()))
def culc_count(n, m , a):
    if a[0]%4==0:
        for i in range(1,n):
            if a[i]%4!=0:
                return 0
    if a[0]%4!=0:
        for i in range(1,n):
            if a[i]%4==0:
                return 0
    count=0
    for i in range(n):
        a[i]/=2
    k = 0
    while(a[0]*2*k + a[0]<=m):
        a_num = a[0]*2*k+a[0]
        bo = True
        for i in range(1,n):
            if (a_num + a[i] )%(2*a[i])!=0:
                bo =False
                break
        if bo==True:
            count+=1
        k+=1
    return count
    


print(culc_count(n, m ,a))

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):
    for j in range(n):
        if a[j]%a[i] == 0:
            if a[i] in b.keys():
                del b[a[i]]
            b[a[j]] = 0
c=list(b.keys())
for i in range(len(c)):
    c[i]=int(c[i])
sk = c[0]
for i in range(1,len(c)):
    sk = sk * c[i] // fractions.gcd(sk,c[i])

x = (m+(sk//2))//sk
print(x)

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):
    for j in range(n):
        if a[j]%a[i] == 0:
            if a[i] in b.keys():
                del b[a[i]]
            b[a[j]] = 0
c=list(b.keys())
for i in range(len(c)):
    c[i]=int(c[i])
sk = c[0]
for i in range(1,len(c)):
    sk = sk * c[i] // fractions.gcd(sk,c[i])

x = (m+(sk//2))//sk
y = (n)//sk
#print(sk)
#print(x)
#print(y)
print(x-y)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
a = list(map(int,input().split()))
d = {}
for i in range(n):
    j = 0
    while True:
        
        x = a[i] * (j + 0.5)
        j +=1
        if x <= m:
            if x in d.keys():
                d[x] +=1
            else:
                d[x] = 1
        else:
            break

ans = 0
for k in d:
    if d[k] == n:
        ans +=1
print(int(ans))

Submission status: Time Limit Exceeded

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

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

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

s = set()
for i in range(n):
    pow, cur = 0, a[i]
    while cur % 2 == 0:
        cur //= 2
        pow += 1
    s.add(pow)
if (len(s) > 1):
    print(0)
else:
    l = a[0] // 2
    for i in range(1, n):
        l = lcm(l, a[i] // 2)
    res, cur = 0, l
    while cur <= m:
        res += 1
        cur += 2 * l
    print(m // l - m // (2 * l))

Submission status: Time Limit Exceeded

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

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

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

s = set()
for i in range(n):
    pow, cur = 0, a[i]
    while cur % 2 == 0:
        cur //= 2
        pow += 1
    s.add(pow)
if (len(s) > 1):
    print(0)
else:
    l = a[0] // 2
    for i in range(1, n):
        l = lcm(l, a[i] // 2)
    res, cur = 0, l
    while cur <= m:
        res += 1
        cur += 2 * l
    print(res)

Submission status: Time Limit Exceeded

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

import fractions
from functools import reduce

def lcm_base(x,y):
    return (x*y)//fractions.gcd(x,y)
def lcm(*numbers):
    return reduce(lcm_base,numbers,1)

min = lcm(*list)

ans = 0
for i in range(min):
    if all((2*i/k-1)%2==0 for k in list):
        ans += i
        break
        
if ans:
    print(1+int((m-ans)/min))
    
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:

from fractions import gcd

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

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

ans = -1
b = [0] * n
for i in range(n):
    if a[i] % 2 != 0:
        print(0)
        exit()

    else:
        b[i] = a[i] // 2


    if i == 0:
        num = format(a[i], 'b')[::-1].find('1')

    else:
        if format(a[i], 'b')[::-1].find('1') != num:

            print(0)
            exit()
        else: num = format(a[i], 'b')[::-1].find('1')



g = b[0]

for i in range(1,n):

    g = (g*b[i]) // gcd(b[i],g)

if g > m: 
    print(0)
    exit()
    
ans = 1
g1 = g
while 1:
    g += 2*g1
    if g > m:
        break
    else:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:

from fractions import gcd

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

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

ans = -1
b = [0] * n
for i in range(n):
    if a[i] % 2 != 0:
        ans = 0
        break

    else:
        b[i] = a[i] // 2


    if i == 0:
        num = format(a[i], 'b')[::-1].find('1')

    else:
        if format(a[i], 'b')[::-1].find('1') != num:

            ans = 0
            break
        else: num = format(a[i], 'b')[::-1].find('1')


if ans != 0:
    g = b[0]
    for i in range(1,n):

        g = (g*b[i]) // gcd(b[i],g)

    if g > m: ans = 0
    else:
        ans = 1
        g1 = g
        while 1:
            g += 2*g1
            if g > m: break
            else: ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

if len(set([i&-i for i in a])) != 1:
  print(0)
else:
  x = a[0]/2
  for i in range(1, len(a)):
      x = x*(a[i]/2//gcd(x,a[i]/2))

  print(int(((M//x)+1)//2))

Submission status: Time Limit Exceeded

Solution code:
import sys,queue,math,copy
from functools import reduce
from fractions import gcd
input = sys.stdin.readline
LI = lambda : [int(x) for x in input().split()]
LI_2 = lambda : [int(x) / 2 for x in input().split()]

#lcm = lambda a : reduce(lambda x, y : x * y // gcd(x,y), a)
N,M = LI()
A = LI_2()

lcm = 1
for a in A:
    lcm *= a // gcd(lcm,a)

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

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

Submission status: Time Limit Exceeded

Solution code:
import math
import bisect
import heapq
from fractions import gcd #math in python 3.7
from collections import deque

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

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


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


def scm(a):
    for i in range(n-1):
        if format(a[i], 'b')[::-1].find('1') != format(a[i+1], 'b')[::-1].find('1'):
            return 0
        
    l = 1
    for i in range(n):
        a[i] = a[i] // 2
        l = lcm(l,a[i])

    count = 0
    lc = l
    if not 1 <= l <= m:
        return 0

    for i in range(l, m+1, 2*lc):
        count += 1

    return count

print(scm(a))

Submission status: Time Limit Exceeded

Solution code:
import sys
import fractions
from functools import reduce
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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())
a = [int(x) for x in input().split()]

ans = 0
half_lcm = lcm_list(a) // 2

a = set(a)
for i in range(half_lcm, M+1, half_lcm):
    if all(int((i / x * 2)) & 1 for x in set(a)):
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

list_ans = [list() for i in range(n)]

for i in range(n):
    a = list_score[i]
    j = 0.5
    b = list_ans[i]
    while True:
        if j*a > m:
            break
        if j*a == int(j*a):
            b.append(int(j*a))

        j += 1

l = []

for i in range(n):
    l += list_ans[i]

ans = [x for x in set(l) if l.count(x) == n]


print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
a = list(map(int,input().split()))
# a = [2*i for i in a]

ans = 0

for i in range(1,m+1):
    # print('i='+str(i))
    ok_all = True
    for aa in a:
        ok_tmp = False
        for j in range(1,m+1):
            # print(j)
            # print(aa,'*',(2*j-1), '=', aa * (2*j-1))

            if aa * (2*j-1) > i*2:
                break
            elif aa * (2*j-1) == i*2:
                ok_tmp = True
                break
        if not ok_tmp:
            ok_all = False
            break

    if ok_all:
        # print(i)
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
A = list(map(int,input().split()))
import fractions

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

def func(first,a,b):
  lcm = get_lcm(a,b)
  for i in range(lcm):
    if (b//2 + i*b - first) % a == 0:
      return b//2+i*b, lcm
  else:
    print(0)
    exit()
next_f = A[0]//2
lcm = 1
for a in A:
  next_f, lcm = func(next_f,lcm,a)
  
print((m - next_f)// lcm+1)

Submission status: Time Limit Exceeded

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

import fractions
import sys

lcm = a[0]//2

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

    
count_list = []
count = 0
for i in range(N):
    while a[i] % 2 == 0:
        count += 1
        a[i] = a[i] // 2
    count_list.append(count)
    count = 0
    
for i in range(N):
    if count_list[i] != sum(count_list)/N:
        print(0)
        sys.exit()
    

print(-(-(M//lcm) // 2))

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
A = list(map(int, input().split()))
X = []

for x in range(1, m+1):
  for i in range(n):
    if x % A[i] != A[i]/2:
      break
  else:
    X.append(x)
print(len(X))

Submission status: Time Limit Exceeded

Solution code:
import fractions

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

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

def lcm(X):
    ret = X[0]
    for i in range(1,len(X)):
        ret = ret * X[i] //fractions.gcd(ret,X[i])
        if ret > M:
            ret = M+1
            break
    return ret




count = 0
a = A[0]
while a % 2 == 0:
    a //= 2
    count += 1

det = 0
for i in range(1,N):
    x = A[i] / (2**count)
    if x % 2 == 0 or int(x) != x:
        det = -1
        break
#print(det)
if det == -1:
    print(0)
else:
    for i in range(N):
        A[i] //= 2**count
        min_l = lcm(A) * (2**(count-1))
    #print(min_l)
    t = M // min_l
    if t % 2 == 0:
        print(t//2)
    else:
        print((t+1)//2)

Submission status: Time Limit Exceeded

Solution code:
import fractions

def lcm(X):
    ret = X[0]
    for i in range(1,len(X)):
        ret = ret * X[i] //fractions.gcd(ret,X[i])
    return ret


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

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

count = 0
a = A[0]
while a % 2 == 0:
    a //= 2
    count += 1

det = 0
for i in range(1,N):
    x = A[i] / (2**count)
    if x % 2 == 0 or int(x) != x:
        det = -1
#print(det)
if det == -1:
    print(0)
else:
    for i in range(N):
        A[i] //= 2**count
        min_l = lcm(A) * (2**(count-1))
    #print(min_l)
    t = M // min_l
    if t % 2 == 0:
        print(t//2)
    else:
        print((t+1)//2)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math
from fractions import gcd
n,m = map(int,input().split())
a = np.array(input().split(),dtype=int)
a /= 2
a.sort()

def t_per2(k):
    num = 0
    while k%2 == 0:
        k = k//2
        num += 1
    return num

f = False
dcm = a[0]
t_2 = t_per2(a[0])
for i in a:
    dcm = (dcm*i)//gcd(dcm,i)
    if dcm > m or not t_per2(i) == t_2:
        f = True
        break

count = 0
if not f:
    count = math.ceil(int(m/dcm)/2)

print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math
from fractions import gcd
n,m = map(int,input().split())
a = np.array(input().split(),dtype=int)
a /= 2

def t_per2(k):
    num = 0
    while k%2 == 0:
        k = k//2
        num += 1
    return num

f = False
dcm = a[0]
t_2 = t_per2(a[0])
for i in a:
    dcm = (dcm*i)//gcd(dcm,i)
    if dcm > m or not t_per2(i) == t_2:
        f = True
        break

count = 0
if not f:
    count = math.ceil(int(m/dcm)/2)

print(count)

Submission status: Time Limit Exceeded

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict
from fractions import gcd

con = 10 ** 9 + 7
#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, M = getlist()
	A = getlist()
	B = [int(A[i] // 2) for i in range(N)]
	LCM = B[0]
	for i in range(N - 1):
		GCD = gcd(LCM, B[i + 1])
		LCM = int(LCM * B[i + 1] / GCD)
		if LCM >= 10 ** 10:
			break

	if LCM > M:
		print(0)
	else:
		ans = (M - LCM) // (2 * LCM) + 1
		D = defaultdict(int)
		for i in range(N):
			x = B[i]
			val = 0
			while True:
				if x % 2 == 0:
					val += 1
				else:
					break
			D[val] += 1

		if D[val] != N:
			ans = 0
			
		print(ans)


if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
s = input().split()
n = int(s[0])
m = int(s[1])
aa = [int(i) for i in input().split()]
a = list(set(aa))
count = 0
for i in range(m):
    for j in range(len(a)):
        if((float.is_integer((i+1)/a[j]-0.5))==False):
            break
        elif(((i+1)/a[j]>=0.5)==False):
            break
        if (j==n-1):
            count = count+1
print(count)

Submission status: Time Limit Exceeded

Solution code:
s = input().split()
n = int(s[0])
m = int(s[1])
a = [int(i) for i in input().split()]
def aaa(x,a):
    p = x - 0.5*a
    return(p>=0 and p%a==0)
count = 0
for i in range(m):
    for j in range(n):
        if (aaa(i+1,a[j])==False):
            break
        if (j==n-1):
            count = count+1
print(count)

Submission status: Time Limit Exceeded

Solution code:
a,b=map(int,input().split())
c=[int(i) for i in input().split()]
tot=0
for i in range(1,b+1):
    for i1 in range(a):
        d=i/c[i1]-0.5

        if d<0 or d!=int(d):
            break
        if i1==a-1:
            tot+=1
        
print(tot)

Submission status: Time Limit Exceeded

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def LOG(x):
    res = 0
    while x%2==0:
        res += 1
    return res
def main():
    N,X = MI()
    A=sorted(LI())
    lcm = 1
    count_2 = LOG(A[0]//2)
    for a in A:
        a//=2
        lcm = a*lcm//gcd(a,lcm)
        if count_2!=LOG(a) or X<lcm:
            print(0)
            return
    print(ceil(X//lcm,2))
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
A = list(map(int,input().split()))
 
def how_two(n):
    a = 0
    while n %2 ==0:
        a+=1
        n//=2
    return a
 
log2 = how_two(A[0])
for i in A:
    tmplog2 = how_two(i)
    if log2!=tmplog2:
        log2 =0
        break
        
        
if log2==0:
    print(0)
else:
    def p_prime(n): 
        prime = [2]
        for i in range(3,n+1):
            flag = 0
            for j in prime:
                if i%j == 0:
                    flag = 1
                    break
                if i**0.5 < j:
                    break
            if flag == 0:
                prime.append(i)
        return prime
 
    mod = 10**9+7
    prime = p_prime(int(mod**0.5+1))
    def soinsuu(M):
        a = {}
        for p in prime:
            count = 0
            while M%p ==0:
                count += 1
                M //= p
            if count > 0:
                a[p] = count
        if M != 1:
            a[M] = 1
        return a
 
    def LCM(A):
        from collections import defaultdict
        AA = defaultdict(int)
    
        for i in range(len(A)):
            tmp = soinsuu(A[i])
            for j in tmp:
                AA[j] = max(AA[j], tmp[j])
                
        L = 1
        for i in AA:
            L *= pow(i,AA[i])
        return L
 
    B = []
    twotwo = pow(2,log2)
    for i in A:
        B.append(i//twotwo)
    l = LCM(B)
    l *= pow(2,log2-1)
    ans =(M+l)//(2*l)
    
    print(ans)

Submission status: Time Limit Exceeded

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

def how_two(n):
    a = 0
    while n %2 ==0:
        a+=1
        n//=2
    return a

log2 = how_two(A[0])
for i in A:
    tmplog2 = how_two(i)
    if log2!=tmplog2:
        log2 =0
        break
        
        
if log2==0:
    print(0)
else:
    def p_prime(n): 
        prime = [2]
        for i in range(3,n+1):
            flag = 0
            for j in prime:
                if i%j == 0:
                    flag = 1
                    break
                if i**0.5 < j:
                    break
            if flag == 0:
                prime.append(i)
        return prime

    mod = 10**9+7
    prime = p_prime(int(mod**0.5+1))
    def soinsuu(M):
        a = {}
        for p in prime:
            count = 0
            while M%p ==0:
                count += 1
                M //= p
            if count > 0:
                a[p] = count
        if M != 1:
            a[M] = 1
        return a

    def LCM(A):
        from collections import defaultdict
        AA = defaultdict(int)
    
        for i in range(len(A)):
            tmp = soinsuu(A[i])
            for j in tmp:
                AA[j] = max(AA[j], tmp[j])
                
        L = 1
        for i in AA:
            L *= pow(i,AA[i])
        return L

    l = LCM(A)
    l //= 2
    ans =(M+l)//(2*l)
    
    print(ans)

Submission status: Time Limit Exceeded

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

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

def main():
    LCM=1

    for i in List:
        LCM*=i/gcd(LCM,i)

    for i in List:
        if LCM//i%2==0:
            print(0)
            exit()

    print(int(M/(LCM*2)+M%(LCM*2)//LCM))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

def main():
    LCM=1

    for i in List:
        LCM*=i/gcd(LCM,i)

    for i in List:
        if LCM//i%2==0:
            print(0)
            exit()

    print(int(M//(LCM*2)+M%(LCM*2)//LCM))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

def main():
    LCM=1

    for i in List:
        LCM*=i//gcd(LCM,i)

    for i in List:
        if LCM/i%2==0:
            print(0)
            exit()

    print(int(M//(LCM*2)+M%(LCM*2)//LCM))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

def main():
    LCM=1

    for i in List:
        LCM*=i/gcd(LCM,i)

    for i in List:
        if LCM/i%2==0:
            print(0)
            exit()

    print(int(M//(LCM*2)+M%(LCM*2)//LCM))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

def main():
    LCM=1
    
    for i in List:
        LCM*=i/gcd(LCM,i)

    for i in List:
        if LCM/i%2==0:
            print(0)
            exit()

    print(int(M//(LCM*2)+M%(LCM*2)//LCM))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

from fractions import gcd

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

def main():
    LCM=1
    cut2count=0
    a=List[0]/2
    while a%2==0:
        a/=2
        cut2count+=1

    for i in List:
        i/=2
        LCM*=i/gcd(LCM,i)
            
        cut2countb=0
        b=i
        while b%2==0:
            b/=2
            cut2countb+=1
        if cut2count!=cut2countb:
            print(0)
            exit()


    #for i in List:
    #   if LCM/i%2==0:
    #      print(0)
    #     exit()

    print(int(M//(LCM*2)+M%(LCM*2)//LCM))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

def main():
    LCM=1
    cut2count=0
    a=List[0]/2
    while a%2==0:
        a/=2
        cut2count+=1

    for i in List:
        i/=2
        LCM*=i/gcd(LCM,i)
            
        cut2countb=0
        b=i
        while b%2==0:
            b/=2
            cut2countb+=1
        if cut2count!=cut2countb:
            print(0)
            exit()


    #for i in List:
    #   if LCM/i%2==0:
    #      print(0)
    #     exit()

    print(int(M//(LCM*2)+M%(LCM*2)//LCM))


if __name__ == '__main__':
    main()