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: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
def gcd(a,b):
  while b:a,b=b,a%b
  return a
def lcm(a,b):return a*b//gcd(a,b)
l=a[0]//2
ll=a[0]
for i in range(1,n):
  l=lcm(l,a[i]//2)
  ll=lcm(ll,a[i])
n=max(n-l,0)
f=l<m+1
m=max(m-l,0)
print(m//ll-n//ll+f)

Submission status: Wrong Answer

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)


N,M = map(int, input().split())
xs = map(int, input().split())
r = 1
for x in xs:
    r = lcm(x,r)
if r//2 > M:
    print(0)
else:
    print((M-r//2)//r+1)

Submission status: Wrong Answer

Solution code:
from fractions import *

N, M = map(int, raw_input().split())
a = map(int, raw_input().split())

g = a[0]/2
for i in range(1, N):
  g = g*(a[i]/2)/(gcd(g, a[i]/2))
  if g>M:
    print 0
    exit(0)
print (M+g)/(2*g)

Submission status: Wrong Answer

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

#import sys
#input = sys.stdin.readline
def main():
    N, M = map( int, input().split())
    A = list( map( int, input().split()))
    T = 1
    for i in range(N):
        T = T*(A[i]//2)//( gcd(T, A[i]//2))
        if T > M:
            print(0)
            return
    print( (M-T)//(2*T) + 1)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from math import ceil
N, M = map(int, input().split())
A = list(map(int, input().split()))
A = [a // 2 for a in A]


# 最大公約数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


# 最小公倍数
def lcm(a, b):
    return a * b // gcd(a, b)


while len(A) > 1:
    A.append(lcm(A.pop(), A.pop()))

X = A[0]
print(ceil((M // X) / 2))

Submission status: Wrong Answer

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

def gcd(x, y):
    while x != 0 and y != 0:
        x, y = max(x, y), min(x, y)
        x %= y
    return y

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

a = 0
for i in range(n):
    if A[i]%2==1:
        a = 1
if a==1:
    print(0)
else:
    for i in range(n):
        A[i] //= 2
    b = A[0]
    for i in range(1,n):
        b = lcm(b,A[i])
    # print(b)

    ans = m//(b*2)
    if m//(b*2)+b<=m:
        ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
write = sys.stdout.write
from fractions import gcd
from functools import reduce
def ii(): return int(readline())
def mi(): return map(int, readline().rstrip().split())
def li(): return list(readline().rstrip())
def lmi(): return list(map(int, readline().rstrip().split()))
def end(*arg): print(*arg); sys.exit()
# template

def lcm_base(x, y):
    return (x * y) // gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def main():
    n, m = mi()
    a = lmi()
    a = list(map(lambda x: x // 2, a))
    la = lcm_list(a)
    x = m // la
    print(-(-x // 2))
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import fractions
#fractions.gcd(x,y)
def lcm(a,b): return a*b//fractions.gcd(a,b)

n,m=map(int,input().split())
a=[int(i) for i in input().split()]
w=a[0]
for i in range(n):
    w=lcm(a[i],w)
print(m//w)

Submission status: Wrong Answer

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

from fractions import gcd

def lcm(a, b):
    """
    aとbの最小公倍数を計算します。
    """
    return a * b // gcd(a, b)


v = 1
for a in A:
    v = lcm(v, a)
if M // v == 0:
    print(0)
else:
    print(M // v + 1)

Submission status: Wrong Answer

Solution code:
import sys
from math import ceil
n, m = [int(i) for i in sys.stdin.readline().split()]
a_ls = [int(i) // 2 for i in sys.stdin.readline().split()]

def gcd(a, b):
    while a and b:
        if a < b:
            b %= a
        else:
            a %= b
    return max(a, b)

def scm(a, b):
    _gcd = gcd(a, b)
    return a * b // _gcd

flg = True
res = a_ls[0]
for a in a_ls[1:]:
    res = scm(res, a)
    if res > m:
        flg = False
        break

if flg:
    print(ceil(m // res / 2))
else:
    print(0)

Submission status: Wrong Answer

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]

tmp = 1
for x in a:
	tmp = x*tmp//gcd(x, tmp)
if tmp >= M:
	print(0)
else:
	print(ceil(M/(tmp*2)))

Submission status: Wrong Answer

Solution code:
N, M = [int(i) for i in input().split()]
a = list(set([int(i)//2 for i in input().split()]))
c = 1
for n in a:
    c *= n
print(M//c - M//(c*2))

Submission status: Wrong Answer

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

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

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

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

k=1

for a in A:
    k=lcm(k,a)

if k%2!=0:
    print(0)
    sys.exit()

l=k//2

print(M//l-M//k)

Submission status: Wrong Answer

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

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)


b = []
for _a in a:
    b.append(_a // 2)
l = lcm_list(b)


mmax = (m - l) // (2 * l)
print(mmax + 1)

Submission status: Wrong Answer

Solution code:
import fractions as f
n,m=map(int,input().split())
a=list(map(int,input().split()))
g=1
for i in range(n):
  g=g*(a[i]//2)//(f.gcd(g,a[i]//2))
  if g>m:print(0);exit()
print(m//g-m//(2*g))

Submission status: Wrong Answer

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

n,m = map(int, input().split())
a = list(map(int, input().split()))
b = [i//2 for i in a]
g = lcm_list(b)
ans = (m//g+1)//2
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from fractions import gcd


def solve(n, m, aaa):
    lcm = 1
    for a in aaa:
        lcm *= a // gcd(lcm, a)
        if lcm > m:
            return 0
    ans = (2 * m // lcm + 1) // 2
    return ans


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

print(solve(n, m, aaa))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal
from argparse import ArgumentParser

args=ArgumentParser()
args.add_argument('-loc', '--local', type=bool,default=False)
LOCAL=args.parse_args().local

def input(): 
    x=sys.stdin.readline(); 
    if x[-1]=="\n": 
        return x.rstrip() 
    return x
    
def printe(*x):_=print("## ",*x,file=sys.stderr) if LOCAL else 0
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def primes(n):
    a = Counter()
    while n % 2 == 0:
        a[2]+=1
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a[f]+=1
            n //= f
        else:
            f += 2
    if n != 1:
        a[n]+=1
    return a

def lcm(A,M,f=0):
    tc=Counter()
    for a in A:
        c=primes(a)
        for p in c:
            tc[p]=max(c[p],tc[p])
    tot=1
    for p in tc:
        tot*=p**tc[p]
        if tot>M:
            return -1
    if f:
        for a in A:
            if tot//a%2==0:
                return -1
        
    return tot

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, M = map(int, input().split())
    A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    m1=lcm(tuple(a//2 for a in A),M,1)
    if m1==-1:
        print(0)
        return
    m2=lcm(A,M)
    if m2==-1:
        print(1)
        return
    ans=1+(M-m1)//m2
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce

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

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

def all_the_same(elements):
    return elements[1:] == elements[:-1]

n, m = map(int, input().split())
A = list(map(int, input().split()))
modA = [A[i] // 2 for i in range(n)]

l = lcm_list(A)
flag = False
while max(modA) <= m:
  if all_the_same(modA):
    flag = True
    break
  P = [i for i, v in enumerate(modA) if v == min(modA)]
  for p in P:
    modA[p] += A[p]
    
if not flag:
  print(0)
  exit()
ans = (m - modA[0]) // l + 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
a = list(map(int, input().split()))
for k in range(N):
  a[k] //= 2

foo = 1
while a[0]%2 == 0:
  foo *= 2
  a[0] // 2
for k in range(1, N):
  if a[k] % foo == 0 and a[k]%(2*foo) !=0:
    a[k] //= foo
    continue
  else:
    print(0)
    exit()
ans = 0

import math
lcm = a.pop()
for k in range(1, N):
  b = a.pop()
  lcm = lcm * b // math.gcd(lcm, b)
  if lcm* foo > M:
    print(0)
    exit()
lcm *= foo
ans = int((M / lcm -1)//2 + 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
a = list(map(int, input().split()))
s = list(set(a))
N = len(a)
for k in range(N):
  a[k] //= 2


count = 0
foo = 1

while a[0]%2 == 0:
  foo *= 2
  a[0] // 2
for k in range(1, N):
  if a[k] % foo == 0 and a[k]%(2*foo) !=0:
    a[k] //= foo
    continue
  else:
    print(0)
    exit()
ans = 0

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

lcm = a.pop()
for k in range(1, N):
  b = a.pop()
  lcm = lcm * b // euclid(lcm, b)
  if lcm* foo > M:
    print(0)
    exit()
lcm *= foo
ans = int((M / lcm -1)//2 + 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
a = list(map(int, input().split()))
for k in range(N):
  a[k] //= 2


count = 0
foo = 1

while a[0]%2 == 0:
  foo *= 2
  a[0] // 2
for k in range(1, N):
  if a[k] % foo == 0 and a[k]%(2*foo) !=0:
    a[k] //= foo
    continue
  else:
    print(0)
    exit()
ans = 0

for odd in [3, 5, 7, 11]:
  flag = False
  for k in range(N):
    if a[k]%odd == 0:
      a[k] //= odd
      flag = True
  if flag:
    foo *= odd

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

lcm = a[0]
for k in range(1, N):
  lcm = lcm * a[k] // euclid(lcm, a[k])
  if lcm* foo > M:
    print(0)
    exit()
lcm *= foo
ans = int((M / lcm -1)//2 + 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
a = list(map(int, input().split()))
a = list(set(a))
N = len(a)
for k in range(N):
  a[k] //= 2


count = 0
foo = 1

while a[0]%2 == 0:
  foo *= 2
  a[0] // 2
for k in range(1, N):
  if a[k] % foo == 0 and a[k]%(2*foo) !=0:
    a[k] //= foo
    continue
  else:
    print(0)
    exit()
ans = 0

for odd in [3, 5, 7, 11]:
  flag = False
  for k in range(N):
    if a[k]%odd == 0:
      a[k] //= odd
      flag = True
  if flag:
    foo *= odd
 

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

lcm = a[0]
for k in range(1, N):
  lcm = lcm * a[k] // euclid(lcm, a[k])
  if lcm* foo > M:
    print(0)
    exit()
lcm *= foo
ans = int((M / lcm -1)//2 + 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
a = list(map(int, input().split()))
a = list(set(a))
N = len(a)
for k in range(N):
  a[k] //= 2


count = 0
foo = 1

while a[0]%2 == 0:
  foo *= 2
  a[0] // 2
for k in range(1, N):
  if a[k] % foo == 0 and a[k]%(2*foo) !=0:
    a[k] //= foo
    continue
  else:
    print(0)
    exit()
ans = 0

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

a.sort()
lcm = a[0]
for k in range(1, N):
  lcm = lcm * a[k] // euclid(lcm, a[k])
  if lcm* foo > M:
    print(0)
    exit()
lcm *= foo
ans = int((M / lcm -1)//2 + 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
a = list(map(int, input().split()))
a = list(set(a))
N = len(a)
for k in range(N):
  a[k] //= 2


count = 0
foo = 1

while a[0]%2 == 0:
  foo *= 2
  a[0] // 2
for k in range(1, N):
  if a[k] % foo == 0 and a[k]%(2*foo) !=0:
    a[k] //= foo
    continue
  else:
    print(0)
    exit()
ans = 0

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

a.sort(reverse=True)
lcm = a[0]
for k in range(1, N):
  lcm = lcm * a[k] // euclid(lcm, a[k])
  if lcm* foo > M:
    print(0)
    exit()
lcm *= foo
ans = int((M / lcm -1)//2 + 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
a = list(map(int, input().split()))
a = list(set(a))
N = len(a)
for k in range(N):
  a[k] //= 2


count = 0
foo = 1

while a[0]%2 == 0:
  foo *= 2
  a[0] // 2
for k in range(1, N):
  if a[k] % foo == 0 and a[k]%(2*foo) !=0:
    a[k] //= foo
    continue
  else:
    print(0)
    exit()
ans = 0

baisu = []

a.sort(reverse=True)



import math
lcm = a[0]
for k in range(1, N):
  lcm = lcm * a[k] // math.gcd(lcm, a[k])
  if lcm*foo  > M:
    print(0)
    exit()
lcm *= foo
ans = int((M / lcm -1)//2 + 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
a = list(map(int, input().split()))
a = list(set(a))
N = len(a)
for k in range(N):
  a[k] //= 2


count = 0
foo = 1

while a[0]%2 == 0:
  foo *= 2
  a[0] // 2
for k in range(1, N):
  if a[k] % foo == 0 and a[k]%(2*foo) !=0:
    a[k] //= foo
    continue
  else:
    print(0)
    exit()
ans = 0




import math
lcm = a[0]
for k in range(1, N):
  lcm = lcm * a[k] // math.gcd(lcm, a[k])
lcm *= foo
ans = int((M / lcm -1)//2 + 1)
print(ans)

Submission status: Time Limit Exceeded

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

max_a = max(a)
min_a = min(a)
max_i = int(m / min_a + 0.5)
#print(max_a,min_a,max_i)
dic = {}
for i in range(n):
    for p in range(int(m / a[i] + 0.5)):
        x = int(a[i] * (p + 0.5))
        dic.setdefault(x,0)
        dic[x] += 1
cnt = 0
for dic_item in dic.items():
    if dic_item[1] == n:
        cnt += 1
        #print(dic_item[0])
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect

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

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""
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

# 素因数分解に基づくlcm
def fact_lcm(numbers):
    d = defaultdict(int)
    for a in numbers:
        b = factorization(a)
        for bb in b:
            d[bb[0]] = max(d[bb[0]],bb[1])
    return(dict(d))

d = fact_lcm(a)
c = 1

for dd in d.items():
    c *= dd[0]**dd[1]

cc = c // 2

for aa in a:
    if cc % aa == 0:
        print(0)
        sys.exit()

print((M-cc) // c + 1)

Submission status: Time Limit Exceeded

Solution code:
from math import gcd

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

def lcm2(array):
    a0 = array[0]
    for a in array[1:]:
        a0 = lcm(a,a0)
    return a0
        

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

temp = lcm2(A)
i = 1
while temp* i <= M:
    if sum(x%2==1 for x in map(lambda x: temp*i//x, A))==N:
        break
    i += 2

print((M//(temp*i)+1)//2)

Submission status: Time Limit Exceeded

Solution code:
_ = input()
# _ = "2 50"
n, m = [int(x) for x in _.split()]
_ = input()
# _ = "6 10"
an = [int(x) for x in _.split()]

store = {}
for x in range(int(m / min(an)) + 1):
    for a in an:
        xx = int(a * (x + 0.5))
        if xx <= m:
            store[xx] = (store.get(xx) or 0) + 1

z = sum(1 if x == len(an) else 0 for x in store.values())
print(z)

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(*numbers):
    return reduce(lcm_base, numbers, 1)
def evencount(n):
  cnt=0
  while n%1==0:
    cnt+=1
    n//=2
  return cnt
n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):
  a[i]//=2
if all(evencount(i) == evencount(a[i]) for i in a):
  d=lcm(*a)
  print((m+d)//2//d)
else:print(0)

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(*numbers):
    return reduce(lcm_base, numbers, 1)
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=[]
for i in a:
  cnt=0
  while i&1==0:
    cnt+=1
    i>>1
  b.append(cnt)
if len(set(b))!=1:
  print(0)
  exit()
for i in range(n):
  a[i]//=2
d=lcm(*a)
print((m+d)//2//d)

Submission status: Time Limit Exceeded

Solution code:
# ANSHUL GAUTAM
# IIIT-D

from math import *
from copy import *					# ll = deepcopy(l)
from heapq import *					# heappush(hp,x)
from string import *				# alpha = ascii_lowercase
from random import *				# l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from bisect import *				# bisect_left(arr,x,start,end)  => start and end parameters are temporary
from sys import stdin				# bisect_left return leftmost position where x should be inserted to keep sorted
from sys import maxsize				# minn = -maxsize
from operator import *				# d = sorted(d.items(), key=itemgetter(1))
from itertools import *				# pre = [0] + list(accumulate(l))
from decimal import Decimal 		# a = Decimal(a)	# use this for math questions
from collections import Counter		# d = dict(Counter(l))
from collections import defaultdict # d = defaultdict(list)

'''
5 1000000000
6 6 2 6 2
'''

def solve(l,m):
	l = list(set(l))
	n = len(l)
	d = defaultdict(int)
	for i in l:
		zz = 0
		while(1 <= i*(zz+0.5) <= m):
			d[i*(zz+0.5)] += 1
			zz += 1
	ans = 0
	for i in d:
		if(d[i] == n):
			ans += 1
	return ans

N,M = list(map(int, stdin.readline().rstrip().split()))
l = list(map(int, stdin.readline().rstrip().split()))
ans = solve(l,M)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, M = (int(i) for i in input().split())
    from math import gcd

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

    def prime_factorize(n):
        res = {2: 0}
        for i in range(2, n+1):
            if i*i > n:
                break
            if n % i != 0:
                continue
            ex = 0
            while n % i == 0:
                ex += 1
                n //= i
            res[i] = ex
        if n != 1:
            res[n] = 1
        return res

    B = [int(i)//2 for i in input().split()]
    c = set()
    L = 1
    for b in B:
        L = lcm(L, b)
        c.add(prime_factorize(b)[2])

    if len(c) != 1:
        print(0)
    else:
        ans = 0
        i = 1
        while L*i <= M:
            ans += 1
            i += 2
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce
N,M=map(int,input().split())
A=list(map(int,input().split()))
A_r=sorted(A,reverse=True)
def judge(n):
    Ai=0
    j=0
    while(Ai<len(A_r) and j==0):
        if (n-A_r[Ai]//2)%A_r[Ai]==0:
            j+=0
        else:
            j+=1
        Ai+=1
    if j==0:
        return True
    else:
        return False
jud=False
aa=A_r[0]/2
while (jud ==(False) and aa<=M):
    jud=judge(aa)
    aa+=A_r[0]
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
lcm=lcm_list(A_r)
if jud==(False):
    print(int(0))
else:
    print(int((M-(aa-A_r[0]))//lcm+1))

Submission status: Time Limit Exceeded

Solution code:
def cal_minX(A,N,M):
    """
    hit A内の数全てでXが割り切れ、かつ商が奇数だったらTrue
    """
    modA=list(map(lambda x:x%2,A))
    max_A=max(A)
    #A内に偶奇が混在する場合は解が存在しない
    if len(set(modA))==2:
        no_ans=True
        minX=0
    else:
        fin=False
        no_ans=False
        i=0
        while fin==False:
            coef=2*i+1
            if max_A*coef>M:
                fin=True
                no_ans=True
            else:
                hit=True
                for n in range(N):
                    if max_A*coef%A[n]==0:
                        if (max_A*coef//A[n])%2==1:
                            pass
                        else:
                            hit=False
                            break
                    else:
                        hit=False
                        break

                if hit==False:
                    i+=1
                else:
                    fin=True
        minX=max_A*coef
    return no_ans,minX

def main():
    #input
    N,M=map(int,input().strip().split())
    A=list(map(int,input().strip().split()))
    A=list(map(lambda x:x//2,A))
    
    #題意を満たす最小のXを求める。
    no_ans,minX=cal_minX(A,N,M)
    #1-Mの中にminXの奇数倍数がいくつあるか調べる
    if minX>M or no_ans:
        return 0
    else:
        if M//minX%2==1:
            return M//minX//2+1
        else:
            return M//minX//2
if __name__=="__main__":
    print(main())

Submission status: Time Limit Exceeded

Solution code:
def cal_minX(A,N,M):
    """
    hit A内の数全てでXが割り切れ、かつ商が奇数だったらTrue
    """
    max_A=max(A)
    i=0
    fin=False
    no_ans=False
    while fin==False:
        coef=2*i+1
        hit=True
        if max_A*coef>M:
            fin=True
            no_ans=True
        else:
            for n in range(N):
                if max_A*coef%A[n]==0:
                    if (max_A*coef//A[n])%2==1:
                        pass
                    else:
                        hit=False
                        break
                else:
                    hit=False
                    break

            if hit==False:
                i+=1
            else:
                fin=True
    return no_ans,max_A*coef

def main():
    #input
    N,M=map(int,input().strip().split())
    A=list(map(int,input().strip().split()))
    A=list(map(lambda x:x//2,A))
    
    #題意を満たす最小のXを求める。
    no_ans,minX=cal_minX(A,N,M)
    #1-Mの中にminXの奇数倍数がいくつあるか調べる
    if minX>M or no_ans:
        return 0
    else:
        if M//minX%2==1:
            return M//minX//2+1
        else:
            return M//minX//2
if __name__=="__main__":
    print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math

MOD = 10 ** 9 + 7
# MOD = 998244353
# sys.setrecursionlimit(10**8)


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


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


total = Counter()
two_count = None
for a in A:
    primes = Counter(prime_factorize(a))
    if not two_count:
        two_count = primes[2]
    elif two_count != primes[2]:
        print(0)
        exit()

    for k, v in primes.items():
        total[k] = max(total[k], primes[k])

ans = 1
for k, v in total.items():
    ans *= pow(k, v)
    if ans > 2*m:
        print(0)
        exit()
# print(ans)

print((m - ans//2)//ans + 1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math

MOD = 10 ** 9 + 7
# MOD = 998244353
# sys.setrecursionlimit(10**8)


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


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


total = Counter()
two_count = None
for a in A:
    primes = Counter(prime_factorize(a))
    if not two_count:
        two_count = primes[2]
    elif two_count != primes[2]:
        print(0)
        exit()

    for k, v in primes.items():
        total[k] = max(total[k], primes[k])

ans = 1
for k, v in total.items():
    ans *= pow(k, v)
# print(ans)

print((m - ans//2)//ans + 1)

Submission status: Time Limit Exceeded

Solution code:
def prime_factor(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


try:
    from math import gcd
except ImportError:
    from fractions import gcd

n, m = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]

n = 1
c = prime_factor(A[0])[0][1]
for a in A:
    if c != prime_factor(a)[0][1]:
        print(0)
        exit()
    n = (n*a)//gcd(n, a)

n //= 2

if n > m:
    ans = 0
else:
    ans = m//n
    ans = (ans+1)//2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions, sys
input = sys.stdin.buffer.readline


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


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


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

print((M - start) // cycle + 1)