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


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

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

LCM=1
cut2count=0
a=List[0]
while a%2==0:
    a/=2
    cut2count+=1

for i in List:
    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))

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

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

Submission status: Time Limit Exceeded

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

def binarySearch (arr, l, r, x): 
  if r >= l: 
    mid = l + (r - l)//2
    if arr[mid] == x: 
      return mid 
    elif arr[mid] > x: 
      return binarySearch(arr, l, mid-1, x)  
    else: 
      return binarySearch(arr, mid+1, r, x) 
  else: 
    return -1


n , m = list(map(int , input().split()))
arr = list(map(int , input().split()))
lcm = arr[0]
hash = [0]*n
for i in range(1,n):
  hcf = gcd(lcm, arr[i])
  lcm = (lcm*arr[i])//hcf 
arr.sort()
k=0
for i in range(0,n):
  j=2
  while(j<=100000):
    if(binarySearch(arr , 0 , n-1 , arr[i]*j)!=-1):
      k=1
      break
    else:
      j=j*2
  if k==1:
    break   
if k==1:
  print(0)
else:
  lcm = lcm//2
  sum = m//lcm
  if(sum%2==0):
    print(sum//2)
  else:
    print(int(sum//2+1))

Submission status: Time Limit Exceeded

Solution code:
import math
import fractions
from functools import reduce


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


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


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


if __name__ == '__main__':
    n, m = list(map(int, input().split()))
    a = list(map(lambda x: int(x) // 2, input().split()))
    a = list(set(a))

    while True:
        odd_flag = 0
        even_flag = 0
        for i in range(len(a)):
            if a[i] % 2 == 0:
                a[i] = a[i] / 2
                even_flag = 1
                if odd_flag == 1:
                    print(0)
                    exit()
            else:
                odd_flag = 1
                if even_flag == 1:
                    print(0)
                    exit()

        if even_flag == 0:
            break
        elif odd_flag == 0:
            m = m // 2

    lcm = lcm_list(a)

    # lcm = a[0]
    # for i in a:
    #     lcm = calc_lcm(lcm, i)

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

Submission status: Time Limit Exceeded

Solution code:
import math
import fractions
 
 
def calc_lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
 
 
if __name__ == '__main__':
    n, m = list(map(int, input().split()))
    a = list(map(lambda x: int(x)//2, input().split()))
    a = list(set(a))
 
    while True:
        odd_flag = 0
        even_flag = 0
        for i in range(len(a)):
            if a[i] % 2 == 0:
                a[i] = a[i] / 2
                even_flag = 1
                if odd_flag == 1:
                    print(0)
                    exit()
            else:
                odd_flag = 1
                if even_flag == 1:
                    print(0)
                    exit()
 
        if even_flag == 0:
            break
        elif odd_flag == 0:
            m = m // 2
 
    lcm = a[0]
    for i in a:
        lcm = calc_lcm(lcm, i)
 
    print(math.ceil((m//lcm)/2))

Submission status: Time Limit Exceeded

Solution code:
import math
import fractions


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


if __name__ == '__main__':
    n, m = list(map(int, input().split()))
    a = list(map(lambda x: int(x)//2, input().split()))
    a = list(set(a))

    while True:
        odd_flag = 0
        even_flag = 0

        even_list = [num for num in a if num % 2 == 0]
        if len(even_list) == 0:
            break
        elif len(even_list) == len(a):
            a = even_list
            m = m // 2
        else:
            print(0)
            exit()

    lcm = a[0]
    for i in a:
        lcm = calc_lcm(lcm, i)

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import fractions
import sys
input = sys.stdin.readline


def f(x):
    res = 0
    while x % 2 == 0:
        x /= 2
        res += 1
    return res


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


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

    A = np.array(A) // 2

    t = f(A[0])
    for i in range(len(A)):
        if f(A[i]) != t:
            print(0)
            return 0
        A[i] >>= t
    M >>= t

    l = 1
    for i in range(N):
        l = lcm(l, A[i])
        if l > M:
            print(0)
            return 0

    M /= l
    ans = (M + 1) // 2
    print(int(ans))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
import fractions


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


if __name__ == '__main__':
    n, m = list(map(int, input().split()))
    a = list(map(lambda x: int(x)//2, input().split()))
    a = list(set(a))

    while True:
        odd_flag = 0
        even_flag = 0
        for i in range(len(a)):
            if a[i] % 2 == 0:
                a[i] = a[i] / 2
                even_flag = 1
                if odd_flag == 1:
                    print(0)
                    exit()
            else:
                odd_flag = 1
                if even_flag == 1:
                    print(0)
                    exit()

        if even_flag == 0:
            break
        elif odd_flag == 0:
            m = m // 2

    lcm = a[0]
    for i in a:
        lcm = calc_lcm(lcm, i)

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

Submission status: Time Limit Exceeded

Solution code:
import math
import fractions


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


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

    while True:
        odd_flag = 0
        even_flag = 0
        for i in range(len(a)):
            if a[i] % 2 == 0:
                a[i] = a[i] / 2
                even_flag = 1
                if odd_flag == 1:
                    print(0)
                    exit()
            else:
                odd_flag = 1
                if even_flag == 1:
                    print(0)
                    exit()

        if even_flag == 0:
            break
        elif odd_flag == 0:
            m = m // 2

    a = list(set(a))
    # print(a)

    lcm = a[0]
    for i in a:
        lcm = calc_lcm(lcm, i)

    # print(lcm)

    # print(m, lcm)
    print(math.ceil((m//lcm)/2))

Submission status: Time Limit Exceeded

Solution code:
import math
import fractions


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


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

    while True:
        odd_flag = 0
        even_flag = 0
        for i in range(len(a)):
            if a[i] % 2 == 0:
                a[i] = a[i] / 2
                even_flag = 1
            else:
                odd_flag = 1

        if odd_flag > 0 and even_flag > 0:
            print(0)
            exit()
        elif even_flag == 0:
            break
        elif odd_flag == 0:
            m = m // 2

    a = list(set(a))
    # print(a)

    lcm = a[0]
    for i in a:
        lcm = calc_lcm(lcm, i)

    # print(lcm)

    # print(m, lcm)
    print(math.ceil((m//lcm)/2))

Submission status: Time Limit Exceeded

Solution code:
from fractions import*
n,m,*a=map(int,open(0).read().split())
s=1
d=set()
for i in a:
  i//=2
  s*=i//gcd(s,i)
  t=0
  while i%2<1:t+=1
  d|={t}
print((0--(m//s)//2)*(len(d)<2))

Submission status: Time Limit Exceeded

Solution code:

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

count = 0
for m in range(1, M+1):
    same_count = 0
    for a in a_list:
        if int(m * 2 / a) == (m * 2 / a):
            if int(m / a) != (m / a):
                same_count += 1
    # print()
    if same_count == len(a_list):
        count += 1
        # print(m/a)

print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import math
import numpy as np

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

a = np.array(a)
a = a // 2

import fractions
from functools import reduce

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

def f(x):
    cnt = 0
    while x%2 == 0:
        x //= 2
        cnt += 1
    return cnt

cnt = f(a[0])
for i in range(1, len(a)):
    if cnt != f(a[i]):
        print(0)
        break
else:
    lcm = reduce(lambda x, y: getLCM(x, y), a)
    ans = (m-lcm) // (lcm*2) + 1 if m >= lcm else 0
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import math
import numpy as np

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

a = np.array(a)
tmp = (a/2).astype(np.int)

import fractions

def f(x):
    cnt = 0
    while x%2 == 0:
        x //= 2
        cnt += 1
    return cnt

cnt = f(a[0])
for i in range(1, len(a)):
    if cnt != f(a[i]):
        print(0)
        break
else:
    lcm = tmp[0]
    for i in range(1, n):
        lcm = lcm * tmp[i] // fractions.gcd(lcm, tmp[i])
    ans = (m-lcm) // (lcm*2) + 1 if m >= lcm else 0
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import math
import numpy as np

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

a = np.array(a)
tmp = (a/2).astype(np.int)

import fractions
lcm = tmp[0]
for i in range(1, n):
    lcm = lcm * tmp[i] // fractions.gcd(lcm, tmp[i])


def f(x):
    cnt = 0
    while x%2 == 0:
        x //= 2
        cnt += 1
    return cnt

cnt = f(a[0])
for i in range(0, len(a)):
    if cnt != f(a[i]):
        print(0)
        break
else:
    ans = (m-lcm) // (lcm*2) + 1 if m >= lcm else 0
    print(ans)

Submission status: Time Limit Exceeded

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

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

LCM = A[0]
for a in A:
    LCM = LCM * a // gcd(LCM, a)

K = max(A)
for X in range(K // 2, M + 1, K):
    for a in A:
        if (X - a // 2) % a != 0:
            break
    else:
        print((M - X) // LCM + 1)
        exit()
print(0)

Submission status: Time Limit Exceeded

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

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

LCM = A[0]
for a in A:
    LCM = LCM * a // gcd(LCM, a)

step = max(A)

if step == 1:
    print(M // 2 + 1)
    exit()

X = step // 2
while X <= M:
    for a in A:
        if (X - a // 2) % a != 0:
            break
    else:
        cnt = X // LCM + (M - X) // LCM + 1
        print(cnt)
        exit()
    X += step
print(0)

Submission status: Time Limit Exceeded

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

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

LCM = A[0]
for a in A:
    LCM = LCM * a // gcd(LCM, a)

step = max(A)
X = step // 2
while X <= M:
    for a in A:
        if (X - a // 2) % a != 0:
            break
    else:
        cnt = X // LCM + (M - X) // LCM + 1
        print(cnt)
        exit()
    X += step
print(0)

Submission status: Time Limit Exceeded

Solution code:
import fractions
N,M=map(int,input().split())
a=list(map(int,input().split()))
c=0
ans = a[0]//2
for i in range(1, N):
  ans = ans * (a[i]//2) // fractions.gcd(ans, a[i]//2)
S=ans
S1=S
S2=S
t=0
t1=0
while t != N and S1 <= M:
  t=0
  for i in range(N):
    if (S1//(a[i]//2))%2 == 1:
      t=t+1
  if t != N:
    S1 = S1 + S
while t1 != N and S2 <= M:
  t1=0
  for i in range(N):
    if (S2//(a[i]//2))%2 == 0:
      t1=t1+1
  if t1 != N:
    S2 = S2 + S
if S1>M:
  print(0)
else:
  print((M-S1)//S2+1)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = set(i//2 for i in map(int, input().split()))
m = max(A)
A.remove(m)
base = 0
for i in range(m,M+1,2*m):
	semi = True
	for j in A:
		if i % j != 0 or (i // j) % 2 == 0:
			semi = False
			break
	if semi:
		base = i
		break
if base == 0:
	print(0)
else:
	print(((M // base) + 1)//2)

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce

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

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

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
    
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.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


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

#if gcd(*A) % 2 != 0:
    #print(0)
    #exit(0)

#sisu_2 = factorization(A[0])[0][1] 
sisu_2 = min([factorization(A[i])[0][1] for i in range(N)])

#lcm_a = lcm(*A)
#lcm_a_half = lcm_a // 2
lcm_a = lcm(*A) // 2
'''
l = []
sisu_a0 = 0
for i in range(N):
    sisu = 0
    while A[i]%2==0:
        A[i] //= 2
        sisu += 1
    
    if sisu_a0==0:
        sisu_a0 = sisu
    else:
        if sisu_a0!=sisu:
            print(0)
            exit()
'''
if (lcm_a % (2**sisu_2) == 0) or lcm_a > M:
#factorization(lcm_a)[0][1] != sisu_2 or lcm_a_half > M:
#if lcm_a > M:
    print(0)
    exit(0)
else:
    print(int((M-lcm_a) // (lcm_a*2) + 1))

Submission status: Time Limit Exceeded

Solution code:
import fractions
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
ans = 0
lcm_half = A[0]//2
flag = 0
numofdiv2 = 0
for s in range(A[0]):
    if A[0] % 2 == 0:
        numofdiv2 += 1
        A[0] //= 2
    else:
        break
for i in range(1, N):
    for k in range(A[i]):
        if A[i] % (2**numofdiv2) != 0 or A[i] % (2**(numofdiv2+1)) == 0:
            flag = 1
            break
    gcd = fractions.gcd((A[i] // 2), lcm_half)
    lcm_half = (lcm_half * (A[i] // 2)) // gcd
    if lcm_half > M:
        flag = 1
        break
if flag == 1:
    ans = 0
else:
    M -= lcm_half
    ans = 1+M//(lcm_half*2)
# print(lcm_half)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
ans = 0
lcm_half = A[0]//2
flag = 0
numofdiv2 = 0
for s in range(A[0]):
    if A[0] % 2 == 0:
        numofdiv2 += 1
        A[0] //= 2
    else:
        break
for i in range(1, N):
    numofdiv2_new = 0
    kari = A[i]
    for k in range(A[i]):
        if kari % 2 == 0:
            numofdiv2_new += 1
            kari //= 2
        else:
            if numofdiv2 != numofdiv2_new:
                flag = 1
                break
    gcd = fractions.gcd((A[i] // 2), lcm_half)
    lcm_half = (lcm_half * (A[i] // 2)) // gcd
    if lcm_half > M:
        flag = 1
        break
if flag == 1:
    ans = 0
else:
    M -= lcm_half
    ans = 1+M//(lcm_half*2)
# print(lcm_half)
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()))
hA = list(map(lambda x:x//2,A))
def lcm_of_list(nums):
    lcm = nums[0]
    for i in range(1,len(nums)):
        lcm = (lcm * nums[i])//gcd(lcm,nums[i])
    return lcm


def calc_2dewareru(num):
    temp = 0
    cnt = 0
    while num%2 == 0:
        num /= 2
        cnt += 1
    return cnt
wareru2 = calc_2dewareru(A[0])
for i in range(1,N):
    if calc_2dewareru(A[i]) != wareru2:
        print(0)
        exit()
#ans = M //lcm_of_list(hA)
#print(lcm_of_list(hA))
# if ans%2 !=0:
#     ans = ans//2+1
# print(ans)
ans = 0
cur = lcm_of_list(hA)
odd = 1
while True:

    if cur*odd <= M:
        ans += 1
    else:break
    odd += 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = set(i//2 for i in map(int, input().split()))
m = max(A)
A.remove(m)
base = 0
for i in range(m,M+1,2*m):
	semi = True
	for j in A:
		if i not in range(j,M+1,2*j):
			semi = False
			break
	if semi:
		base = i
		break
if base == 0:
	print(0)
else:
	print(((M // base) + 1)//2)

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(i//2 for i in map(int, input().split()))
m = max(A)
A.remove(m)
base = 0
for i in range(m,M+1,2*m):
	semi = True
	for j in A:
		if i not in range(j,M+1,2*j):
			semi = False
			break
	if semi:
		base = i
		break
if base == 0:
	print(0)
else:
	print(((M // base) + 1)//2)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = list(int(i/2) for i in map(int, input().split()))
m = max(A)
A.remove(m)
cnt = 0
for i in range(m,M+1,2*m):
	semi = True
	for j in A:
		if i not in range(j,M+1,2*j):
			semi = False
			break
	if semi:
		cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = list(int(i/2) for i in map(int, input().split()))
A.sort(reverse = True)
m = max(A)
A.remove(m)
cnt = 0
for i in range(m,M+1,2*m):
	semi = True
	for j in A:
		if i % j != 0 or (i // j) % 2 == 0:
			semi = False
	if semi:
		cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

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

cnt = 0
for i in range(M):
	semi = True
	for j in A:
		if ((i+1) * 2 / j) % 2 != 1:
			semi = False
			break
	if semi:
		cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
N, M = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
a_num = np.array(a)
x = a_num // 2
count_even = np.count_nonzero(x % 2 == 0)
if count_even != 0 and count_even != N:
    print(0)
    sys.exit()
c = []
from collections import Counter
if count_even == N:
    for i in x:
        cnt = 0
        while i % 2 == 0:
            cnt += 1
            i //= 2
        c.append(cnt)
    c = Counter(c)
    if len(c.keys()) != 1:
        print(0)
        sys.exit()
    
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)

minmulti = lcm(* x)
temp = M // minmulti
if temp % 2 == 0:
    print(temp // 2)
else:
    print(1 + temp // 2)

Submission status: Time Limit Exceeded

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

p=0
U=[]
for i in range(N):
    while A[i]*(p+0.5) <= M:
        U.append(A[i]*(p+0.5))
        p += 1
    p=0
dup = [x for x in set(U) if U.count(x) == N]
print(len(dup))

Submission status: Time Limit Exceeded

Solution code:
import sys
from fractions import gcd
from operator import mul
from functools import reduce
inputs = sys.stdin.readlines()

n, m = map(int, inputs[0].split())
A = list(map(int, inputs[1].split()))
if all((a // reduce(gcd, A)) % 2 for a in A):
    print(round((m+1) / reduce(lambda x, y: x*y // gcd(x, y), A)))
else:
    print(0)

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

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.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

p = set()

flag = 0



ans = 0
q = 2
tmp = factorization(A[0])
tmp2 = tmp[0][1]
for i in range(N):
    tmp = factorization(A[i])
    if tmp[0][1] != tmp2:
        flag = 1
        break
    q = (q*A[i])//fractions.gcd(q, A[i])
if flag==0:
    minans = 1
    maxans = M
    cnt = 0
    i = M  //2
    while(cnt < 30):
        cnt += 1
        if q * (i * 2 + 1) // 2 > M :
            maxans = i
            i -= (maxans-minans) // 2
        else:
            minans = i
            i += (maxans-minans) // 2

    for j in range(4):

        if q*((i-2+j)*2 + 1) // 2 <= M:
            ans = (i-2+j)+1
        

print(ans)

Submission status: Time Limit Exceeded

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

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

# c = [ i for i in a if i%2!=0 ]
# if len(c)!=0:
#     print(0)
#     exit()

b = list(map( lambda x : x//2 , a ))

# print(a)
# print(b)

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.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

chls = []
for i in range(n):
    f = factorization(a[i])
    num2 = f[0][1]
    chls.append(num2)
if len(list(set(chls)))!=1:
    print(0)
    exit()

from fractions import gcd
from functools import reduce

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

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

l = lcm_list(b)
# print(l)
# if l>m:
#     print(0)
#     exit()

pmax = (m-l) // (2*l)
# print(pmax)

ans = pmax + 1

print(ans)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
import fractions
n,m = list(map(int,input().split()))
a = list(map(int,input().split()))
cnt = 0
lcm = 1
for i in range(n):
    a[i]//=2
    lcm = lcm*a[i]//fractions.gcd(lcm,a[i])
c = [0]*n
flag = False
for i in range(n):
    while a[i]%2==0:
        a[i]//=2
        c[i]+=1
    for j in range(i):
        if c[i]!=c[j]:
            flag = True
            break
    if flag:
        break
if flag:
    print(0)
else:
    tmp = m//lcm
    print((tmp+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 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)
    if lcm//2 > M:
        print(0)
        return

    max_a = A_sorted[0]
    find_x = 0
    for p in range(0, lcm//2):
        x = max_a * (p + 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):
    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)
    #if lcm/2 > M:
    #    print(0)
    #    return

    max_a = A_sorted[0]
    find_x = 0
    for p in range(0, lcm//2):
        x = max_a * (p + 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
n,m = list(map(int,input().split()))
a = list(map(int,input().split()))
cnt = 0
lcm = 1
for i in range(n):
    a[i]//=2
    lcm = lcm*a[i]//fractions.gcd(lcm,a[i])
c = [0]*n
flag = False
for i in range(n):
    while a[i]%2==0:
        a[i]//=2
        c[i]+=1
    for j in range(i):
        if c[i]!=c[j]:
            flag = True
            break
if flag:
    print(0)
else:
    tmp = m//lcm
    print((tmp+1)//2)

Submission status: Time Limit Exceeded

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

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

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
#! //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)


Mb=lcm_list(B)
gmp=None

i=1
while True:
    m=Mb*i
    if m>M:
        break
    T=1
    for b in B:
        if not ((m//b)%2==1):
            T=0
    if T==1:
        gmp=m
        break
    
    i+=1


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

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)


Mb=max(B)
gmp=None

i=1
while True:
    m=Mb*i
    if m>M:
        break
    T=1
    for b in B:
        if not ((m//b)%2==1 and m%b==0):
            T=0
    if T==1:
        gmp=m
        break
    
    i+=1


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