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 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 = lcm_list(Bs)
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:
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))
    
def lcm_list(numbers):
    return reduce(fractions.lcm, numbers)

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())
A = list(map(int, input().split()))
B = set(A)
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:
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):
        if b>a:
            a,b = b,a
        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:
#!/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:

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])
    for a in A:
        kou=a*kou//gcd(a,kou)
        if (kou//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:
from fractions import gcd
from math import ceil
n,m=map(int,input().split())
a=list(map(int,input().split()))
c=len(bin(a[0]))-bin(a[0]).rfind("1")
for i in range(1,n):
  if c!=len(bin(a[i]))-bin(a[i]).rfind("1"):
    print(0)
    exit()
g=a[0]
for i in range(n-1):
   g=(g//gcd(g,a[i+1]))*(a[i+1]//gcd(g,a[i+1]))*gcd(g,a[i+1])
g//=2
print(ceil((m//g)/2))

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

    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:
        B.sort()
        g = 1
        for b in B:
            l = gcd(b, g)
            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:
n, m = map(int,input().split())
a = list(set(map(int, input().split())))
n = len(a)

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 = list(map(int,input().split()))
A = list(map(int,input().split()))
a = [A[i] // 2 for i in range(N)]
    
def lcm(a):
    from fractions import gcd
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x
flag = False
b = lcm(a)
while flag == False:
    flag = True
    for i in range(N):
        if (b // a[i]) % 2 == 0:
            flag = False
    if flag == False:
        b += b
if M >= b:
    ans = (M - b) // (2*lcm(a)) + 1
else:
    ans = 0
print(ans)

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])
    for a in A:
        kou=a*kou//gcd(a,kou)
        if (kou//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:
#!/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 range(2,n):
    lb = lcm(lb,b[i])

for i in range(n):
    if lb//b[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:
import fractions # version 3.4
from functools import reduce

def lcm(*numbers):
    ans = numbers[0]
    for a in numbers:
        ans = ans * a // fractions.gcd(ans, a)
    # return reduce(lambda x,y: (x * y) // fractions.gcd(x, y), numbers, 1)

    return ans


def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))


N, M = l_in()
A = l_in()

B = [a//2 for a in A]
L = lcm(*B)

if any((L//b)%2 == 0 for b in B):
    print(0)
else:
    print((M//L + 1)//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

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

if bins == 1:
  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:
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()])))
def lcm(a, b):
    ret = a * b // gcd(a, b)
    ret_ = ret
    if gcd(a, b) != 1:
        while (ret // a) % 2 == 0 or (ret // b) % 2 == 0:
            ret += ret_

    return ret

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

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

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

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])
    for a in range(n):
        kou=A[a]*kou//gcd(A[a],kou)
        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:
#!/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 range(2,n):
    lb = lcm(lb,b[i])

for i in range(n):
    if lb//b[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:
import math
from collections import Counter
N,M = map(int,input().split())
a = list(map(int,input().split()))
maxa = max(a)
i = 1
p = 1
while True:
    tmp = (i+0.5)*maxa
    if math.ceil(tmp) == math.floor(tmp):
        p = i
        break
    i += 1
lcm = 0
flag = False
for i in range(p,M+1,p):
    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:
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
            l = lcm(l, i)
    return (M + l // 2) // l

print(main())

Submission status: Time Limit Exceeded

Solution code:
import fractions

n, m = map(int, input().split())
a = list(map(int, input().split()))
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 = a[0]
for i in range(1, n):
	now = lcm(now, a[i])

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

print(((m//(now//2))+1)//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 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

    tmp = A[0]

    for i in range(1,N):
        tmp = tmp * A[i] // GCM(tmp,A[i])

    ans = M//(tmp*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:
#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 = sys.stdin.readline

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

    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:

def main():
    """"ここに今までのコード"""
    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 range(n):
        kou=A[a]*kou//gcd(A[a],kou)
        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:

def main():
    """"ここに今までのコード"""
    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 range(n):
        kou=A[a]*kou//gcd(A[a],kou)
    for a in range(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:
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:
n, m = map(int, input().split())
a = list(map(int, input().split()))

a.sort(reverse=True)
ans = [i for i in range(m + 1)]

for j in a:
    n_ans = []
    for i in ans:
        if ((i / j - 0.5) % 1 == 0):
            n_ans.append(i)
    ans = n_ans[:]

print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
import fractions # version 3.4
from collections import defaultdict
from functools import reduce

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

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


def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

N, M = l_in()
A = l_in()

B = [a//2 for a in A]
L = lcm(*B)

if any([(L//b)%2 == 0 for b in B]):
    print(0)
else:
    print((M//L + 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()))
maxa = max(a)
i = 1
p = 1
while True:
    tmp = (i+0.5)*maxa
    if math.ceil(tmp) == math.floor(tmp):
        p = i
        break
    i += 1
lcm = 0
flag = False
for i in range(p,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:
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)):
      count += 1
   x += d
print(count)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from math import ceil
n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n-1):
  if len(bin(a[i]))-bin(a[i]).rfind("1")!=len(bin(a[i+1]))-bin(a[i+1]).rfind("1"):
    print(0)
    exit()
g=a[0]
for i in range(n-1):
   g=(g//gcd(g,a[i+1]))*(a[i+1]//gcd(g,a[i+1]))*gcd(g,a[i+1])
g//=2
print(ceil((m//g)/2))

Submission status: Time Limit Exceeded

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

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

def lcm_l(l):
  ans = l[0]
  for i in range(1, len(l)):
    ans = ans * l[i] // fractions.gcd(ans, l[i])
  return ans

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

Submission status: Time Limit Exceeded

Solution code:
import itertools

n, m = map(int, input().split())
a_list = list(map(int, input().split()))
# n, m = 2, 50
# a_list = [6, 10]

x_list = []
for a in a_list:
    p = 0
    x_tmp_list = []
    while True:
        x = a * (p + 0.5)
        if x > m:
            break
        x_tmp_list.append(x)
        p += 1
    x_list.append(x_tmp_list)

x_flat_list = list(itertools.chain.from_iterable(x_list))
num_list = []
for num in x_list[0]:
    if x_flat_list.count(num) == n:
        num_list.append(num)

print(len(num_list))

Submission status: Time Limit Exceeded

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

def gcd(a,b):
    if a < b:
        a, b = b, a
    while b >= 1:
        a, b = b, a % b
    return a
def lcm(a,b):
	return a * b // gcd(a,b)

def p2(x):
    ans = 0
    while x % 2 == 0:
        ans += 1
        x //= 2
    return ans

n = len(a_list)

p2_list = [p2(i) for i in a_list]

p2_set = set(p2_list)
if len(p2_set) != 1:
    print(0)
else:
    p = 1
    for i in a_list:
        p = lcm(p, i//2)

    if p > m:
        print(0)
    else:
        m -= p
        print(m//(p*2)+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
lists=list(map(int,input().split()))
uselist=[0 for i in range(n)]
for i in range(n):
	uselist[i]=lists[i]//2           
import fractions
import math
ans = uselist[0]
for i in range(1, n):
    ans = ans* uselist[i] // fractions.gcd(ans, uselist[i])

flags=True
for some in uselist:
    a=ans//some
    if a%2==0:
        flags=False
        break
if flags:
    p=math.floor(m/ans)
    if p%2==0:
      print(p//2)
    elif p%2!=0:
      print(p//2+1)
    
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
def lcm(nums):
    ret = 1
    for i in nums:
        ret = ret*i//gcd(ret, i)
    return ret

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

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce


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 != 0:
            print(0)
            return
        if ai % (2*elm) == 0:
            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:
import fractions
import math
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)

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

x = lcm(*A)
for a in A:
    if((x//a)%2==0):
        print(0)
        break
else:
    print(math.ceil((M//x)/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)

from fractions import gcd
import functools

l = functools.reduce(lambda a, b: a * b // gcd(a, b), 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:
"""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))"""
def main():
    """"ここに今までのコード"""
    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))
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce


def inpl():
    return list(map(int, input().split()))


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


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


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


def count2(i, t=0):
    if i % 2 == 0:
        return count2(i // 2, t + 1)
    else:
        return t


N, M = inpl()
A = inpl()
A = [a // 2 for a in A]

all_lcm = lcm_list(A)
c_2 = count2(A[0])
for a in A:
    if c_2 != count2(a):
        print(0)
        exit()

print(((M // all_lcm) + 1) // 2)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import bisect
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop


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


def I(): return int(sys.stdin.readline())


def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res


def IR(n):
    return [I() for i in range(n)]


# A
def A():
    K, X = LI()
    if K * 500 >= X:
        print("Yes")
    else:
        print("No")
    return


# B
def B():
    n = I()
    s = S()
    cnt = 0
    for i in range(n - 2):
        if s[i] == "A":
            if s[i + 1] == "B" and s[i + 2] == "C":
                cnt += 1
    print(cnt)
    return


# C
def C():
    n = I()
    p = LI()
    q = LI()
    a_cnt = [1] * n
    b_cnt = [1] * n
    a = 0
    b = 0
    for i in range(1, n + 1):
        num = 1
        for j in range(1, n + 1 - i):
            num *= j
        a += sum(a_cnt[:p[i - 1]]) * num
        b += sum(b_cnt[:q[i - 1]]) * num
        a_cnt[p[i - 1] - 1] = 0
        b_cnt[q[i - 1] - 1] = 0
    print(abs(a - b))
    return


# D
def D():
    def GCD(a, b):
        if (b == 0):
            return a
        else:
            return GCD(b, a % b)

    n, m = LI()
    a = list(int(x) // 2 for x in sys.stdin.readline().split())
    b = a[0]
    for i in range(1, n):
        b = b * a[i] // GCD(b, a[i])
    for i in a:
        if (b // i) % 2 == 0:
            print(0)
            return
    if b > m:
        print(0)
    else:
        print((m - b) // (b * 2) + 1)
    return


# E
def E():
    return


# F
def F():
    return


# Solve
if __name__ == "__main__":
    D()

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

a2 = [int(i//2) for i in map(int,input().split())]
count2 = set()
for i in a2:
    prime = prime_factorize(i)
    count2.add(prime.count(2))
if len(count2) == 1:

    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:
import sys
def gcd(a,b):
  if a==0:return b
  else:return gcd(b%a,a)
def lcm(a,b):
  return a//gcd(a,b)*b
n,m=map(int,input().split())
a=list(map(int,input().split()))
l=1;c=-1
for i in a:
  l=lcm(l,i)
  memo=i;cnt=0
  while memo%2==0:
    memo/=2
    cnt+=1
  if c==-1:c=cnt
  elif c!=cnt:
    print(0)
    sys.exit(0)
if l%2==1:print(0)
else:print((m - l // 2 + l) // l)

Submission status: Time Limit Exceeded

Solution code:
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:
n, m = [ int(v) for v in input().split() ]
a_list = list(set([ int(v) for v in input().split() ]))

def gcd(a,b):
    if a < b:
        a, b = b, a
    while b >= 1:
        a, b = b, a % b
    return a
def lcm(a,b):
	return a * b // gcd(a,b)

def p2(x):
    ans = 0
    while x % 2 == 0:
        ans += 1
        x //= 2
    return ans

n = len(a_list)

p2_list = [p2(i) for i in a_list]

p2_set = set(p2_list)
if len(p2_set) != 1:
    print(0)
else:
    p = 1
    for i in a_list:
        p = lcm(p, i//2)

    if p > m:
        print(0)
    else:
        m -= p
        print(m//(p*2)+1)

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