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

def calc(x, a):
    p = x / a - 0.5
    if p == int(p):
        return True
    else:
        return False

def resolve():
    N, M = map(int, input().split())
    A = list(set(map(int, input().split())))
    A_sorted = sorted(A, reverse=True)

    lcm = lcm_list(A)
    # print(lcm)

    max_a = A_sorted[0]
    find_x = 0
    for j in range(0, lcm*2):
        x = max_a * (j + 0.5)
        # print("x", x)
        find_flg = True
        for a in A_sorted[1:]:
            if not calc(x, a):
                find_flg = False
                # print("not found")
                break
        if find_flg:
            find_x = x
            break
            
    # print("find_x", x)
    if find_x == 0:
        print(0)
        return
    res = M - find_x
    count_c = int(res // lcm) + 1

    print(count_c)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
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)

def calc(x, a):
    for p in range(100):
        v = a * (p + 0.5)  # binary search
        if v == x:
            return True
        elif v >= x:
            return False

def resolve():
    N, M = map(int, input().split())
    A = list(set(map(int, input().split())))
    A_sorted = sorted(A, reverse=True)

    lcm = lcm_list(A)
    # print(lcm)

    max_a = A_sorted[0]
    find_x = 0
    for j in range(0, lcm*2):
        x = max_a * (j + 0.5)
        # print("x", x)
        find_flg = True
        for a in A_sorted[1:]:
            if not calc(x, a):
                find_flg = False
                # print("not found")
                break
        if find_flg:
            find_x = x
            break
            
    # print("find_x", x)
    if find_x == 0:
        print(0)
        return
    res = M - find_x
    count_c = int(res // lcm) + 1

    print(count_c)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import math
#! //Users/daigofujiwara/anaconda3/bin python3

#h行で列和がyかy+1であるかどうかとサンプルを出力

input1=input()

input2=input()

x,y=input1.split(" ")
N,M=int(x),int(y)

A=input2.split(" ")

A=[int(a) for a in A ]

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

gmp=None

for i in range(1,M+1):
    T=1
    for b in B:
        if not ((i//b)%2==1 and i%b==0):
            T=0
    if T==1:
        gmp=i
        break

if gmp is None:
    print(0)
else:
    print(int(math.floor(M/gmp+1.0)/2.0))

Submission status: Time Limit Exceeded

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

st = set()

for i in range(1,m+1):
    lst = [i%x==x/2 for x in a]
    if all(lst):
        st.add(i)
        break
            
f = (((m // i) - 1) //2)
print(len(st) + f)

Submission status: Time Limit Exceeded

Solution code:
N,M = list(map(int,input().split()))
A = list(map(int,input().split()))
a = [A[i] // 2 for i in range(N)]
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

lcm = 1
for i in range(len(a)):
    lcm = calc_lcm(lcm,a[i])
    if lcm > 2 * M:
        lcm = 0
        break
b = lcm
if lcm != 0:
    flag = False
else:
    flag = True

while flag == False:
    flag = True
    for i in range(N):
        if (b // a[i]) % 2 == 0:
            flag = False
    if flag == False:
        b += b
if lcm == 0:
    ans = 0
elif M >= b:
    ans = (M - b) // (2*lcm) + 1
else:
    ans = 0
print(ans)

Submission status: Time Limit Exceeded

Solution code:

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

for j in range(1,M+1):
  for i in range(N):
    p = float(j/a[i])-0.5
    if p < 0:
      break
    else:
      if (p).is_integer():
        if i == N-1:
          cnt += 1
      else:
        break

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# for rejudge
import sys
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, sys.stdin.readline().rstrip().split())
a = list(map(int, sys.stdin.readline().rstrip().split()))
 
if len(set(map(div2, a))) != 1:
  print(0)
  exit(0)
 
m_lcm = lcm(a) // 2
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 fractions import gcd
def lcm(p,q):
    return p*q//gcd(p,q)
n,m = map(int, input().split())
a = list(map(int, input().split()))
x = 1
for i in range(n):
    a[i] = a[i]//2
    x = lcm(x,a[i])
for i in range(n):
    if (x//a[i])%2==0:
        print(0)
        exit()
p = m//x
print(p//2 if p%2==0 else p//2+1)

Submission status: Time Limit Exceeded

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def gcd(n,m):
    if m == 0:
        return n
    else:
        return gcd(m,n%m)

def lcm(n,m):
    return n*m // gcd(n,m)


n,m = LI()
a = LI()
b = [i//2 for i in a]

if n == 1:
    lb = b[0]
else:
    lb = lcm(b[0],b[1])

for i in b[2:]:
    lb = lcm(lb,i)

for i in b:
    if lb//i % 2 == 0:
        ans = 0
        break
else:
    if lb > m:
        ans = 0
    else:
        ans = (m//lb + 1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce
import collections

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

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

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

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

v=[]

x=lcm_list(a)

for i in range(n1):
    for j in range(x//a[i]):
        v.append(a[i]*j+a[i]//2)

v = collections.Counter(v)
v=v.most_common()

if v[0][1]!=n1:
    print(0)
else:
    print((m-v[0][0])//x+1)

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

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()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()

a = LIST()

for i in range(1, N):
	if abs(a[0]//2-a[i]//2) % gcd(a[0], a[i]) != 0:
		print(0)
		sys.exit()
tmp = 1
for x in a:
	tmp = x*tmp//gcd(x, tmp)
tmp = tmp//2
print((M-tmp)//(tmp*2)+1)

Submission status: Time Limit Exceeded

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
from fractions import gcd

def lcm(n,m):
    return n*m // gcd(n,m)


n,m = LI()
a = LI()
b = [i//2 for i in a]

lb = 1
for i in b:
    lb = lcm(lb,i)

for i in b:
    if lb//i % 2 == 0:
        print(0)
        quit()
 
if lb > m:
    print(0)
    quit()

ans = m//lb//2 + (m // lb) % 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:

#! //Users/daigofujiwara/anaconda3/bin python3

#h行で列和がyかy+1であるかどうかとサンプルを出力

input1=input()

input2=input()

x,y=input1.split(" ")
N,M=int(x),int(y)

A=input2.split(" ")

A=[int(a) for a in A ]

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

count=0

for i in range(1,M+1):
    T=1
    for b in B:
        if not ((i//b)%2==1 and i%b==0):
            T=0
    if T==1:
        count+=1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

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()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()

a = LIST()

# a = [x//2 for x in a]
# if a[0] % 2 == 0:  # 偶数の時
# 	for x in a:
# 		if x % 2 == 1:
# 			print(0)
# 			sys.exit(0)
# 	for x in a:
# 		if a[0] != x and abs(a[0]-x)%gcd(2*a[0], 2*x) != 0:
# 			print(0)
# 			sys.exit()

# 	tmp = 1
# 	for x in a:
# 		tmp = x*tmp//gcd(x, tmp)
# 	print((M-tmp)//(tmp*2)+1)

# else:
# 	for x in a:
# 		if x % 2 == 0:
# 			print(0)
# 			sys.exit(0)
# 	tmp = 1
# 	for x in a:  # 奇数の時
# 		tmp = x*tmp//gcd(x, tmp)
# 	print((M-tmp)//(tmp*2)+1)

for i in range(1, N):
	if abs(a[0]//2-a[i]//2) % gcd(a[0], a[i]) != 0:
		print(0)
		sys.exit()
tmp = 1
for x in a:
	tmp = x*tmp//gcd(x, tmp)
tmp = tmp//2
print((M-tmp)//(tmp*2)+1)

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce
import collections

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

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

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

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

x=lcm_list(a)


for i in range(n):
    for j in range(x//a[i]):
        v.append(a[i]*j+a[i]//2)

v = collections.Counter(v)
v=v.most_common()

if v[0][1]!=n:
    print(0)
else:
    print((m-v[0][0])//x+1)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
def lcm(a, b):
    return a * b // gcd(a, b)
N, M = map(int, input().split())
B = set(map(lambda x: int(x)//2, input().split()))
power = 1
for b in B:
    power = lcm(power, b)

mn = min(B)
p2 = power // mn

if p2 % 2 == 0:
    print(0)
    exit()
ans1 = M // mn // p2
ans2 = M // mn // (p2 * 2)
print(ans1-ans2)

Submission status: Time Limit Exceeded

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

from fractions import gcd
from functools import reduce
l = As[0]
for a in As:
    l = l * a // gcd(l, a)

i = 2
while l & (i - 1) == 0:
    i <<= 1
i = (i >> 1) - 1

fg = False
if i > 0:
    for a in As:
        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:
import numpy as np
from fractions import gcd
from functools import reduce
from math import floor
  
def lcm_base(x, y):
    return (x * y) // gcd(x, y)

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

def count_bin(n):
  res = 0
  while n > 0:
    if n % 2 == 0:
      res += 1
      n = n // 2
    else:
      return res
  return res

def main():
  N ,M = map(int, input().split())
  A = list(set(list(map(int, input().split()))))
  last = count_bin(A[0])
  last_a = A[0]
  for a in A[1:]:
    target = count_bin(a)
    if target == last:
      last_a = lcm_base(last_a, a)
    else:
      print(0)
      exit()
  least_lcm = last_a // 2
  print(max(floor( (M - least_lcm) // last_a + 1), 0))

main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
def lcm(a, b):
    return a * b // gcd(a, b)
N, M = map(int, input().split())
B = set(map(lambda x: int(x)//2, input().split()))
power = 1
for b in B:
    power = lcm(power, b)

mn = min(B)

mn2 = mn
p2 = power // mn2

if p2 % 2 == 0:
    print(0)
    exit()
ans1 = M // mn2 // p2
ans2 = M // mn2 // (p2*2)
print(ans1-ans2)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
def lcm(p,q):
    return p*q//gcd(p,q)

n,m = map(int, input().split())
a = list(map(int, input().split()))
x = 1
for i in range(n):
    a[i] = a[i]//2
    x = lcm(x,a[i])
for i in range(n):
    if (x//a[i])%2==0:
        print(0)
        exit()
p = m//x
if p%2==0:
    ans = p//2
else:
    ans = p//2 +1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
As = set(map(lambda a: int(a) >> 1, input().split()))

from fractions import gcd
from functools import reduce

l = reduce(lambda a, b: a * b // gcd(a, b), As)

i = 2
while l & (i - 1) == 0:
    i <<= 1
i = (i >> 1) - 1

fg = False
if i > 0:
    for a in As:
        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:
from fractions import gcd
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
a.reverse()
g=a[0]
for i in range(1,n):
  g=(g*a[i])//gcd(g,a[i])

p=0
flag=0
cnt=0
while (a[0]*(p+0.5)<=m) and flag==0:
  #print("p",p)
  for i in range(1,n):
    if (a[0]*(p+0.5)-a[i]//2)%a[i]==0:
      continue
    else:
      flag=1
  if flag==0:
    break
  p+=1
  flag=0
print((int(m-a[0]*(p+0.5))//g+1))

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import reduce
sys.setrecursionlimit(10**6)


def main():

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

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

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

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

    a0 = a[0]
    p = 0
    while a0 % 2 == 0:
        a0 //= 2
        p += 1
    elm = 2**p

    for ai in a:
        if (ai/elm) % 2 != 1:
            print(0)
            return

    lcm = lcm(*a)
    ans = (2*m+lcm) // (lcm*2)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

def main():
    """"ここに今までのコード"""
    import sys
    input = sys.stdin.readline
    n,m=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()
    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])
    from bisect import bisect_right as br
    c=br(A,A[-1]//2)
    for a in A:
        kou=a*kou//gcd(a,kou)
    if (kou//A[0])%2==0:
            print(0)
            exit()
    kou//=2
    #print(kou)
    ans=(m//kou+1)//2
    print(int(ans))
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

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)

GCD = 1
t = a[0]
cond = 0
while t%2 == 0:
	t //= 2
	cond += 1
	
mod = 2**cond
for i in range(len(a)):
	t = a[i]
	t_cond = 0
	while t%2 == 0:
		t //= 2
		t_cond += 1
	if t_cond != cond:
		print(0)
		sys.exit()


	GCD = GCD*a[i] // gcd(GCD,a[i])
	
A = (2*m) // GCD
if A%2 == 1:
	A+=1

print(A//2)

Submission status: Time Limit Exceeded

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

A = list(set(A))

ans = 0
num = 0
a_max = max(A)
i_max = int(M/a_max)

if True:
  for i in range(0,i_max+1):
    x = a_max * i + int(a_max/2)
    if x>M:
      break
    else:
      flag = True
      for a in A:
        if x%a == int(a/2):
          pass
        else:
          flag = False
          break
      if flag:
        num = x
        break
    
if num>0:
  maximum = 1
  for j in range(1,int(M/num)+1):
      if num*(2*j-1) <= M:
        maximum = j
      else:
        break
  ans = maximum
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce
import numpy as np

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)
A = np.array(A)
A //= g
A = A.tolist()
l = lcm_list(A)
if l%2 == 0:
  print(0)
else:
  print(((m//(l*g))+1)//2)

Submission status: Time Limit Exceeded

Solution code:
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)


# def lcm_list(numbers):
#     if len(numbers) == 1:
#         return numbers[0]
#     if len(numbers) == 2:
#         return lcm_base(numbers[0], numbers[1])
    
#     return lcm_base(lcm_list(numbers[:len(numbers)//2]), lcm_list(numbers[len(numbers)//2:]))


N, M = map(int, input().split())
Bs = list(map(lambda x: int(x) // 2, input().split()))
X = Bs[0]
for i in range(1, N):
    X = X * Bs[i] // fractions.gcd(X, Bs[i])
for b in Bs:
    if (X // b) % 2 == 0:
        print(0)
        break
else:
    print((M // X + 1) // 2)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
def lcm(a, b):
    return a * b // gcd(a, b)
N, M = map(int, input().split())
B = set(map(int, input().split()))
power = 1
for b in B:
    if b == 2:
        continue
    power = lcm(power, b//2)

mn = min(B)

mn2 = mn // 2
p2 = power // mn2

if p2 % 2 == 0:
    print(0)
    exit()
ans1 = M // mn2 // p2
ans2 = M // mn2 // (p2*2)
print(ans1-ans2)

Submission status: Time Limit Exceeded

Solution code:
def f(n):
    a=0
    while n%2==0:
        n//=2
        a+=1
    return a    
n,m,*a=map(int,open(0).read().split())
c=[f(i) for i in a]
if sum(c)!=c[0]*n:
    print(0)
    exit()
import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
a=list(set(a))
a=[i//(2**c[0]) for i in a]
b=a[0]
for i in a:
    b=lcm(i,b)
b*=(2**c[0])    
print(0 if b//2>m else (m-b//2)//b+1)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
lst = list(map(int,input().split()))
#m_lst = [i+1 for i in range(M)]
ans=[]
for i in lst:
    for j in range(M):
        num = int(i*(j+0.5))
        if num<=M:
        #if num in m_lst:
            ans.append(num)
answer = [x for x in set(ans) if ans.count(x) > N-1]
print(len(answer))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce
N, M = map(int, input().split())
A = list(map(int, input().split()))
AA = list(map(lambda x: x//2, A))
def lcm(x, y):
    return x * y // gcd(x, y)
B = list(map(lambda x:x&-x, A))
if all(map(lambda x:x==B[0], B[1:])):
    a = reduce(lcm, AA)
    print(M//a - M//(2*a))
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int, input().split())
an=[int(i)//2 for i in input().split()]
ma=max(an)
count=0
q=1
while m>=ma*q:
    for ak in an:
        if (ma*q)%ak==0 and ((ma*q)//ak)%2==1:
            plus=1
        else:
            plus=0
            break
    q+=2
    if plus==1:
        count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import fractions
import sys


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


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

all_lcm = 1

for a in list(set(l)):
    all_lcm = lcm(a, all_lcm)

    if all_lcm > 2 * M:
        print(0)
        sys.exit()

minimum = None
for b in range(1, all_lcm * 2):
    minimum = b
    for a in l:
        if (b - a/2) % a != 0:
            minimum = None
            break

    if minimum is not None:
        break

if minimum is None:
    print(0)
    sys.exit()


print(1 + int((M - minimum) / all_lcm))

Submission status: Time Limit Exceeded

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

N, M = map(int, input().split())
B = set(map(int, input().split()))
power = 1
for b in B:
    power = lcm(power, b//2)

mn = min(B)

mn2 = mn // 2
p2 = power // mn2

if p2 % 2 == 0:
    print(0)
    exit()
ans1 = M // mn2 // p2
ans2 = M // mn2 // (p2*2)
print(ans1-ans2)

Submission status: Time Limit Exceeded

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def gcd(n,m):
    if m == 0:
        return n
    else:
        return gcd(m,n%m)

def lcm(n,m):
    return n*m // gcd(n,m)


n,m = LI()
a = LI()
b = [i//2 for i in a]

if n == 1:
    lb = b[0]
else:
    lb = lcm(b[0],b[1])

for i in b[2:]:
    lb = lcm(lb,i)

for i in b:
    if lb//i % 2 == 0:
        print(0)
        quit()
 
if lb > m:
    print(0)
    quit()

ans = m//lb//2 + (m // lb) %2
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()))
A = list(set(A))
AA = [a//2 for a in A]
K = [1 for i in range(len(AA))]
'''
def gcd(x, y):
    if x < y:
        x, y = y, x
    while x % y != 0:
        x, y = y, x % y
    return(y)
'''
def lcm(x, y):
    ans = (x * y) // gcd(x, y)
    return(ans)
l = 1
g = AA[0]

for i in range(len(AA)):
    g = gcd(g, AA[i])
    l = lcm(l, AA[i])
AAA = [a // g for a in AA]
C = [a % 2 for a in AAA]

if C == K:
    ans = M // l
    print((ans+1)//2)
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
def main():
    """"ここに今までのコード"""
    import sys
    input = sys.stdin.readline
    n,m=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()
    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])
    from bisect import bisect_right as br
    c=br(A,A[-1]//2)
    for a in A:
        kou=a*kou//gcd(a,kou)
    for a in range(min(c+1,n)):
        if (kou//A[a])%2==0:
            print(0)
            exit()
    kou//=2
    #print(kou)
    ans=(m//kou+1)//2
    print(int(ans))
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n, m = [int(x) for x in input().strip().split()]
a = sorted(list(set([int(x)//2 for x in input().strip().split()])), reverse=True)
lcm_d = {}
gcd_d = {}
def lcm(a, b, d, dd):
    if (a, b) in d:
        return d[(a, b)]
    ret = a * b // gcd(a, b, dd)
    ret_ = ret
    if gcd(a, b, dd) != 1:
        while (ret // a) % 2 == 0 or (ret // b) % 2 == 0:
            ret += ret_
    d[(a, b)] = ret
    return ret

def gcd(a, b, d):
    if (a, b) in d:
        return d[(a, b)]
    if b == 0:
        return a
    d[(a, b)] = gcd(b, a % b, d)
    return d[(a, b)]

lcm_ = a[0]
for aa in a[1:]:
    lcm_ = lcm(aa, lcm_, lcm_d, gcd_d)

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

Submission status: Time Limit Exceeded

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

A = list(set(A))

ans = 0
num = 0
a_max = max(A)
i_max = int(M/a_max)

if True:
  for i in range(0,i_max+1):
    x = a_max * i + int(a_max/2)
    if x<=M:
      flag = True
      for a in A:
        if x%a == int(a/2):
          pass
        else:
          flag = False
          break
      if flag:
        num = x
        break
    
if num>0:
  maximum = 1
  for j in range(1,int(M/num)+1):
      if num*(2*j-1) <= M:
        maximum = j
      else:
        break
  ans = maximum
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce
N, M = map(int, input().split())
A = list(map(int, input().split()))
AA = list(map(lambda x: x//2, A))
def lcm(x, y):
    return x * y // gcd(x, y)
B = list(map(lambda x:len(bin(x&-x)), A))
if all(map(lambda x:x==B[0], B[1:])):
    a = reduce(lcm, AA)
    print(M//a - M//(2*a))
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
a = [int(x) for x in input().split()]

count = 0
x = int(max(a) * 0.5)
d = x * 2
while x <= m:
   b = [x % ak for ak in a]
   check = [1 if (bk * 2) == ak else 0 for ak, bk in zip(a, b)]
   if (sum(check)==len(a)):
      if (count == 0):
         start = x
         count += 1
      elif (count == 1):
         diff = x - start
         break
   x += d

an = x
n = 3
while an <= m:
   an = start + (n - 1) * diff
   n += 1
   count += 1
print(count)

Submission status: Time Limit Exceeded

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

import fractions
from functools import reduce
def gcd(*numbers):
    return reduce(fractions.gcd, numbers)
def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

while not 1 in [i % 2 for i in tmparr]:
    tmparr = [i // 2 for i in tmparr]
if sum([i % 2 -1 for i in tmparr]) != 0:
    print(0)
else:    
    gcdnum = gcd_list(arr)
    lcmnum = 1
    for i in arr:
        if lcmnum == 1:
            lcmnum = i
        lcmnum = i * lcmnum // gcd(lcmnum,i)
    print(max((m-lcmnum//2)//lcmnum+1,0))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from fractions import gcd
from functools import reduce
from math import floor

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

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

def count_bin(n):
  res = 0
  while n > 0:
    if n % 2 == 0:
      res += 1
      n = n // 2
    else:
      return res
  return res

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

last = count_bin(A[0])
bins = True
for a in A[1:]:
  target = count_bin(a)
  if target == last:
    continue
  else:
    bins = False

if bins:
  lcm = lcm_list(A)
  least_lcm = lcm // 2
  print(max(floor( (M - least_lcm) // lcm + 1), 0))
else:
  print(0)

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)

def invalid(a, b):
    if a > b:
        a, b = b, a
    return (b % a == 0 and ((b - a) // 2) % a != 0)

def main():
    N, M = map(int, input().split())
    A = list(set(map(int, input().split())))
    A.sort(reverse=True)
    if len(A) == 1:
        l = A[0]
    else:
        if invalid(A[0], A[1]):
            return 0
        l = lcm(A[0], A[1])
        for i in A[2:]:
            if invalid(l, i):
                return 0
            if l % i == 0:
                continue
            l = lcm(l, i)
    return (M + l // 2) // l

print(main())

Submission status: Time Limit Exceeded

Solution code:
import collections as c
ip = lambda : map(int, input().split())
# ##############
N,M = ip()
a = list(ip())
from fractions import gcd
g = a[0]//2
for i in range(1,N):
    g = g*(a[i]//2)//gcd(g,a[i]//2)
#print((M-g)//(2*g)+1)
for i in a:
    if g%i!=i//2:
        print(0)
        exit()
print((M-g)//(2*g)+1)

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)

def invalid(a, b):
    if a > b:
        a, b = b, a
    return (b % a == 0 and ((b - a) // 2) % a != 0)

def main():
    N, M = map(int, input().split())
    A = list(set(map(int, input().split())))
    A.sort()
    if len(A) == 1:
        l = A[0]
    else:
        if invalid(A[0], A[1]):
            return 0
        l = lcm(A[0], A[1])
        for i in A[2:]:
            if invalid(l, i):
                return 0
            if l % i == 0:
                continue
            l = lcm(l, i)
    return (M + l // 2) // l

print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n, m = [int(x) for x in input().strip().split()]
a = sorted(list(set([int(x)//2 for x in input().strip().split()])))
lcm_d = {}
gcd_d = {}
def lcm(a, b, d, dd):
    if (a, b) in d:
        return d[(a, b)]
    ret = a * b // gcd(a, b, dd)
    ret_ = ret
    if gcd(a, b, dd) != 1:
        while (ret // a) % 2 == 0 or (ret // b) % 2 == 0:
            ret += ret_
    d[(a, b)] = ret
    return ret

def gcd(a, b, d):
    if (a, b) in d:
        return d[(a, b)]
    if b == 0:
        return a
    d[(a, b)] = gcd(b, a % b, d)
    return d[(a, b)]

lcm_ = a[0]
for aa in a[1:]:
    lcm_ = lcm(aa, lcm_, lcm_d, gcd_d)

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

Submission status: Time Limit Exceeded

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

def is_scm(x, a):
  if ((x/a)-0.5) == int((x/a)-0.5):
    return True
  else:
    return False

count = 0
for x in range(1, m+1):
  scm_num = 0
  for ak in a:
    if is_scm(x, ak):
      scm_num += 1

  if scm_num == len(a):
    count += 1

print(count)