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

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])
        if tmp > M:
            print(0)
            return

    ans = M//(tmp*pow_two//2)
    if ans%2==0:
        ans -= 1
    ans -= ans//2
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()

a = LIST()

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

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


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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5)
def GCM(a, b):
  a, b = max(a,b), min(a, b)
  r = a % b
  if r == 0:
    return b
  else:
    return GCM(b, r)

def LCD(a, b):
  g = GCM(a, b)
  return (a//g)*b

N, M = map(int, input().split())
A = list(map(int, input().split()))
X = A[0]//2
for a in A[1:]:
  b = a//2
  newX = LCD(X, a//2)
  if (newX // b)%2 == 0:
    print(0)
    sys.exit(0)
  else:
    X = newX
X_2 = X*2
print(M//X-M//X_2)

Submission status: Accepted

Solution code:
import math
def main():

    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A = sorted([a // 2 for a in A])
    if max(A) > M: return 0

    pows = set()
    for a in A:
        b = a
        count = 0
        while b % 2 == 0:
            count += 1
            b = b  // 2
        pows.add(count)
    if len(pows) > 1: return 0

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

    prev = 1
    for i in range(len(A)):
        c = gcd(prev, A[i])
        prev = (prev // c) * A[i]

    return (M // prev  + 1) // 2

if __name__ == '__main__':
    print(main())

Submission status: Accepted

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 = 2
    ret = 1
    while i % t == 0:
        t *= 2
        ret += 1
    return ret - 1


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

all_lcm = 1
c2 = count2(A[0])
for a in A:
    all_lcm = lcm(all_lcm, a)
    if count2(a) != c2:
        print(0)
        exit()

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

Submission status: Accepted

Solution code:
import sys
import fractions
N,M=map(int, input().split())
A = [int(a) for a in input().split()]
A2 = [a>>1 for a in A]

lcm = A2[0]
for i in range(1, N):
    lcm = lcm * A2[i] // fractions.gcd(lcm, A2[i])
    if lcm>M:
        print(0)
        sys.exit()
    
B = sum([1 for a in A if lcm%a==0])
if B>0:
    print(0)
else:
    print((M//lcm+1)//2)

Submission status: Accepted

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)
            break
    if p <= m:
        m -= p
        print(m//(p*2)+1)

Submission status: Accepted

Solution code:
import fractions
n,m = map(int,input().split())
a = list(map(int,input().split()))
b = 1
c = 0
key = 1
key1 = 1
l = []
while key == 1:
    if a[0] % b == 0:
        b *= 2
        c += 1
    else:
        b //= 2
        c -= 0
        key = 0
for i in range(n):
    if a[i] % b == 0:
        if (a[i]//b) % 2 == 0:
            key1 = 0
            break
        else:
            l.append(a[i]//b)
    else:
        key1 = 0
        break
if key1 == 0 or c == 0:
    print(0)
else:
    d = l[0]
    for i in range(1,n):
        d = d*l[i]// fractions.gcd(d,l[i])
        if m < d:
            break
    d = d*b//2
    if (m//d)%2 == 0:
        print((m//d)//2)
    else:
        print((m//d)//2+1)

Submission status: Accepted

Solution code:
import fractions
import sys
import copy
def lcm(x, y):
    return (x*y)//fractions.gcd(x, y)

n,m=map(int,input().split())
a=list(map(int,input().split()))
b=copy.copy(a)
b=list(set(b))
n2=len(b)

count=n2
while count!=0:
  count=0
  for i in range(n2):
    if b[i]%2==0:
      b[i]=b[i]//2
      count+=1
  if len(set(b))!=n2:
    print(0)
    sys.exit()

for i in range(n):
  a[i]=a[i]//2
L=a[0]
for i in range(1,n):
  L=lcm(L,a[i])
  if L>=10**9+1:
    print(0)
    sys.exit()

if (m//L)%2==0:
  print((m//L)//2)
else:
  print(((m//L)//2)+1)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
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)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def gcd(a,b):
        if a == 0:
            return b
        return gcd(b%a,a)
    n,m = LI()
    a = LI()
    b = [i >> 1 for i in a]
    c = [i&1 for i in b]
    c.sort()
    while 1:
        if c[0] == 1:
            break
        if c[0] == 0 and c[-1] == 1:
            print(0)
            return
        b = [i >> 1 for i in b]
        c = [i&1 for i in b]
        c.sort()
        m >>= 1
    l = b[0]
    for i in b[1:]:
        if l&1 != i&1:
            print(0)
            return
        g = gcd(l,i)
        l = l*i//g
        if l > m:
            print(0)
            return
    L = l
    l = 0
    r = m+1
    while r-l > 1:
        x = (l+r) >> 1
        if (2*x-1)*L <= m:
            l = x
        else:
            r = x
    print(l)
    return

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

Submission status: Accepted

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 power(n,p):
    cnt = 0
    while n%p == 0:
        cnt += 1
        n //= p
    return cnt


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

for i in range(1,N):
    if power(A[i],2) != power(A[i-1], 2):
        print(0)
        exit()

g = A[0]
for i in range(1, N):
    g = lcm(g, A[i])

print((M + g)//(2*g))

Submission status: Accepted

Solution code:
# import fractions as math
import math

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

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

N, M = [int(i) for i in input().split()]
A = [int(i)//2 for i in input().split()]
lcm_A = 1
for a in A:
    lcm_A = lcm(lcm_A, a)
    if((lcm_A//a)%2==0):
        print(0)
        break
else:
    print(math.ceil((M//lcm_A)/2))

Submission status: Accepted

Solution code:
from fractions import gcd
from sys import exit

N, M = map(int, input().split())
A = [int(x) for x in input().split()]

p = -1
while True:
    tmp_2 = [x % 2 for x in A]
    if tmp_2 == [0] * N:
        A = [x // 2 for x in A]
    elif tmp_2 == [1] * N:
        break
    else:
        print(0)
        exit()
    p += 1

lcm = A[0]
for i in range(1, N):
    lcm = lcm * A[i] // gcd(lcm, A[i])
    if A[i] % 2 == 0 or lcm > M:
        print(0)
        exit()

print((M // (lcm*2**p) + 1) // 2)

Submission status: Accepted

Solution code:
import fractions
n,m = map(int,input().split())
a = list(map(int,input().split()))
g = a[0]
flag = 1
x = 0
y = 0

for i in range(n-1):
    z = fractions.gcd(g,a[i+1])
    x = g/z
    y = a[i+1]/z
    if x%2==1 and y%2==1:
        g = x*y*z
    else:
        print(0)
        flag = 0
        break

if flag==1:
    print(round((m+1)/g))

Submission status: Accepted

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])
        if (b // a[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: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()
import fractions
gcd=fractions.gcd
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=0

n,m=LI()
b=[int(i)//2 for i in input().split()]
#a=LI()

'''
s=time.time()
n=10**4
b=[random.randint(10,10**8) for i in range(n)]
t=time.time()
show(t-s)
'''

lcm=b[0]
for i in range(1,n):
    lcm=(lcm//gcd(b[i],lcm))*b[i]
    if lcm>3*m:
      break

ans=(1+m//lcm)//2

fl=False
for i in b:
    t=lcm//i
    if t%2==0:
        fl=True
    
if lcm%2==0 and fl:
    ans=0
    
    
print(ans)

Submission status: Accepted

Solution code:
import fractions
import math
#gcd = math.gcd
gcd = fractions.gcd
n, m = [int(_) for _ in input().split()]
a = sorted([int(_) // 2 for _ in input().split()])
lcm = a[0]
for i in range(1, n):
    lcm = lcm * a[i] // gcd(lcm, a[i])
    if lcm > 10**10:
        print(0)
        exit()
for b in a:
    if (lcm // b) % 2 == 0:
        print(0)
        exit()
ans = m // lcm
if ans % 2 == 0:
    ans -= 1
if ans < 0:
    print(0)
    exit()
print(ans // 2 + 1)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
A = list(map(int,input().split()))
B = []
from functools import reduce
import fractions
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
def gcd(*numbers):
    return reduce(fractions.gcd, numbers)
def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)


#odd and even
m1 = False
m2 = False
for e in A:
    if (e//2)%2 == 0:
        m1 = True
    else:
        m2 = True
    if m1 and m2:
        print(0)
        exit()
#even and even
if m1:
    l = gcd_list(A)
    for e in A:
        if (e//l)%2 == 0:
            print(0)
            exit()

s = lcm_list(A)
x = s//2
if x > M:
    print(0)
else:
    print((M-x)//s+1)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
import numpy as np

import math
#from math import gcd
from fractions import gcd




def main():
	n,m=map(int,input().split())
	a=list(map(int,input().split()))
	a=np.array(a)
	cnt=-2
	while True:
		cnt+=1
		b=a%2
		bsum=np.sum(b)
		if bsum==n:
			break
		elif 0<bsum<n:
			print(0)
			exit(0)
		a//=2
	
	l=1
	
	for i in a:
		l=l*i//gcd(l, i)
	
	
	base=(2**cnt)*l
	
	ans=math.floor((m)/(2*base)+0.5)
	
	print(ans)
	
	
	


if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import fractions

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

N, M = [int(x) for x in input().split()]
l = [int(x) // 2 for x in input().split()]
ans = l[0]
for i in reversed(range(30)):
  if ans % 2 ** i == 0:
    numof2 = 2 ** i
    break
for i in range(1, N):
  if l[i] % numof2 == 0 and (l[i] // numof2) % 2 == 1: 
    ans = lcm(ans, l[i])
  else:
    ans = M + 1
    break
ans2 = M // ans
print(ans2 // 2 + ans2 % 2)

Submission status: Accepted

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

mod = 1
while a[0] % 2 == 0:
  mod *= 2
  a[0] //= 2

flag = False
for i in range(1, n):
  if a[i] % mod == 0 and a[i] % (mod * 2) != 0:
    a[i] //= mod
  else:
    flag = True
    break

if flag:
  print(0)
else:
  lcm = a[0]
  for i in range(1, n):
    p = lcm
    q = a[i]
    r = p % q
    while r != 0:
      p, q = q, r
      r = p % q
    lcm = lcm * a[i] // q
  lcm *= mod
  print(m // lcm - m // (2 * lcm))

Submission status: Accepted

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


def main():
    N, M = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]
    ans = 1
    mi = float("inf")
    for a in A:
        if a & 1:
            print(0)
            exit()
        else:
            ans = (ans * (a // 2)) // fractions.gcd(ans, a // 2)
    for a in A:
        if a & 1:
            print(0)
            exit()
        else:
            if ans % a == 0:
                print(0)
                exit()

    print(-(-(M // ans) // 2))



    
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
import fractions

N, M = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) // 2 for x in stdin.readline().rstrip().split()]
ans = 0
g = 1

for i in range(len(A)):
    g = g * A[i] // fractions.gcd(g % A[i], A[i])
    if g > M:
        print(0)
        exit()

for i in range(len(A)):
    if (g // A[i]) % 2 == 0:
        print(0)
        exit()

ans = M // g
if ans % 2 == 0:
    print(ans // 2)
else:
    print((ans + 1) // 2)

Submission status: Accepted

Solution code:
import sys; readline = sys.stdin.readline
from collections import deque

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

if any(a % 2 == 1 for a in A):
    print(0)
    exit(0)

h = [a // 2 for a in A]

def gcd(x, y):
    if x < y:
        x, y = y, x
    
    while x % y != 0:
        r = x % y
        x, y = y, r
    
    return y

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

cum_g = h[0]

for i in range(1, len(A)):
    cum_g = gcp(cum_g, h[i])

rs = [cum_g // x for x in h]
if any(r % 2 == 0 for r in rs):
    print(0)
    exit(0)


if cum_g > M:
    print(0)
else:
    print(1 + (M - cum_g) // (2 * cum_g))

Submission status: Accepted

Solution code:
from functools import reduce
import fractions
n, m = map(int, input().split())
a = [int(x)//2 for x in input().split()]

y = a[0]

for i in range(1,n):
    y = y*a[i] // fractions.gcd(y,a[i])
    if y > m:
        print(0)
        exit()

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

x = m//y

if x % 2 == 0:
    print(x//2)
else:
    print((x+1)//2)

Submission status: Accepted

Solution code:
def gcd(a: int, b: int) -> int:
    """a, bの最大公約数(greatest common divisor:GCD)を求める
    計算量: O(log(min(a, b)))
    """
    if b == 0:
        return a
    return gcd(b, a%b)


def lcm(a, b):
    """a, bの最小公倍数(least common multiple:LCM)を求める
    計算量: O(log(min(a, b)))"""
    return (a * b) // gcd(a, b)

             
def multi_lcm(array, m):
    """arrayのLCMを求める"""
    ans = array[0] 
    for i in range(1, len(array)):
        ans = (ans * array[i]) // gcd(ans, array[i])
        if ans > 5*m:
            return 5*m
    return ans 

import sys
input = sys.stdin.readline

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

l = [0] * n
for i in range(n):
    cnt = 0
    tmp = a[i]
    while True:
        if tmp % 2 == 0:
            cnt += 1
            tmp //= 2
        else:
           break
    l[i] = cnt
if max(l) != min(l):
    print(0)
    exit()
    
div = multi_lcm(a, m)
ans = 0
if m - div // 2 >= 0:
    ans += 1
m = m - div // 2 
ans += m // div
if m < 0:
    print(0)
else:
    print(ans)

Submission status: Accepted

Solution code:
import fractions

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

pow2 = 2**50 #10**9 <= 2**30

p2 = set()

for i in range(n):
    tmp = fractions.gcd(pow2,a[i])
    p2.add(tmp)
    if len(p2)>1:###
        print(0)
        exit()
def lcd(x,y):
    tmp = fractions.gcd(x,y)
    x//=tmp 
    y//=tmp 
    return x*y*tmp
tmp = a[0]

for i in range(n):
    tmp = lcd(tmp,a[i])
    if tmp > m:
        print(0)
        exit()

tmp2 = tmp*2

ans = m//tmp 
ans2 = m//tmp2
ans -= ans2
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
#from math import gcd
N,M = map(int,input().split())
A = list(map(int,input().split()))
lcm = A[0]
lis = [[0] for _ in range(30)]
tmp = 0
while A[0]%2 == 0:
    A[0]//= 2
    tmp += 1
lis[tmp] = 1

for i in range(1,N):
    tmp = 0
    while A[i]%2 == 0:
        A[i]//= 2
        tmp += 1
    lis[tmp] = 1
    lcm = (lcm*A[i]) // gcd(lcm,A[i])
    if lcm > 2*M:
        print(0)
        exit()
jud = False
for l in lis:
    if l == 1:
        if jud == True:
            print(0)
            exit()
        else:
            jud = True


M -= lcm//2
ans = (M//lcm)+1
print(ans)

Submission status: Accepted

Solution code:
"""
for y in range(1, 32):
  for x in range(1, 32):
    ok = False
    for i in range(1, 10000):
      if i%y==0 and i/y%2!=0 and i%x==0 and i/x%2!=0:
        ok = True
        break
    print "#" if ok else ".",
  print
"""

"""
x = 1
for i in range(32):
  print x
  x = x*2+1
"""

from fractions import *

def check(x, y, d):
  #print x, y, d
  if x==y==d+1:
    return True
  if x==d+1 or y==d+1:
    return False
  return check(x%(d+1), y%(d+1), d/2)

N, M = map(int, raw_input().split())
a = [int(t)/2 for t in  raw_input().split()]

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

"""
 2: 1  3  5  7  9 11 13 15 17
 4: 2  6 10 14 18 22 26 30 34
 6: 3  9 15 21 27 33
 8: 4 12 20 28 36 44
10: 5 15 25 35 45 
12: 6 18 

  1 2 3 4 5 6
1 o x o x o x
2 x o x x x o
3 o x o x o 
4 x x x o
5 o x o
6 x o
"""

Submission status: Accepted

Solution code:
import sys
def gcd(x,y):
    if x<y:
        x,y=y,x
    if y==0:
        return x
    else:
        return gcd(y,x%y)

N,M=map(int,input().split())
A=list(map(int,input().split()))
B=[]
for i in range(N):
    A[i]//=2
    cnt=1
    while A[i]%2==0:
        A[i]//=2
        cnt+=1
    B.append(cnt)
B.sort()
if B[0]!=B[-1]:
    print(0)
    sys.exit()
num=A[0]
for i in range(1,N):
    num=num*A[i]//gcd(num,A[i])
num*=2**(B[0]-1)
ans=M//num
if ans%2==0:
    print(ans//2)
else:
    print(ans//2+1)

Submission status: Accepted

Solution code:
import copy
import fractions
import sys
n,m=map(int,input().split())
A=list(map(int,input().split()))
a=copy.copy(A[0])
c=0
while a%2==0:
  a=a//2
  c=c+1
d=2**c
for i in range(n):
  if A[i]//d!=float(A[i])/d or A[i]//(2*d)==float(A[i])/(2*d):
    print(0)
    sys.exit()
B=[]
for i in range(n):
  B.append(A[i]//2)
b=1
for i in range(n):
  b=b*B[i]//fractions.gcd(b,B[i])
  if b>m:
    print(0)
    sys.exit()
if b>m:
  print(0)
else:
  print(1+(m-b)//(2*b))

Submission status: Accepted

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

b = [i//2 for i in a]

t = b[0]
while t & 1 == 0:
    t //= 2
p2 = b[0]//t

odds = [1]*N
for i, n in enumerate(b):
    if n % p2 != 0 or (n//p2 & 1) == 0:
        print(0)
        exit()
    odds[i] = n//p2
def gcd(a,b):
    while b:
        a,b = b, a%b
    return a
def lcm(a,b):
    return a*b // gcd(a,b)
l = reduce(lcm,odds)

M = M//p2
print((M//l-1)//2 + 1)

Submission status: Accepted

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

odd = sum([ah % 2 for ah in ahs])
if odd!=0 and N-odd!=0:
    print(0)
else:
    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)

    lcm = lcm_list(ahs)

    result = True
    for ah in ahs:
        if (lcm // ah) % 2 == 0:
            result = False
            break

    if result == False:
        print(0)
    else:
        print((M//lcm-1)//2 + 1)

Submission status: Accepted

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

def main():
    _, m = map(int, input().split())
    a = list(map(int, input().split()))

    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
        if i == 1:
            if (int(x / a[0]) % 2 == 0) or (int(x / a[i]) % 2 == 0):
                print(0)
                return
        else:
            if (int(x / a[i]) % 2 == 0):
                print(0)
                return

    print(int((int(m * 2 / x) + 1) / 2))

if __name__ == '__main__':
    main()

Submission status: Accepted

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()))
lcm_a = a[0]
for i in a[1:]:
  lcm_a = lcm_a * i // fractions.gcd(lcm_a,i)
  if lcm_a > m * 2:
    print(0)
    exit()
if all([(lcm_a // i) % 2 for i in a]):
  ans = (m - lcm_a // 2) // lcm_a + 1
  print(ans)
else:
  print(0)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
n,m=map(int,input().split())
a=list(map(int,input().split()))
from fractions import gcd
ans=a[0]
flag=[0,0]
kou=a[0]
for i in range(1,n):
    kou=gcd(kou,a[i])
    ans = ans * a[i] // gcd(ans, a[i])
    if ans//2>m:
        print(0)
        quit()
# print(kou)
for i in range(n):
    if a[i]//kou%2==0:
        print(0)
        quit()
ans//=2
if ans>m:
    print(0)
else:
    print((m-ans)//(ans*2)+1)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
an = list(map(int, input().split()))
an = list(set(an))
bn = [a // 2 for a in an]

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

b0 = ln2(bn[0])
for b in bn:
  if ln2(b) != b0:
    print(0)
    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)

l = lcm(bn)
print(m // l - m // (2*l))

Submission status: Accepted

Solution code:
from functools import reduce
from math import ceil
n, m = map(int, input().split())
a = list(map(int, input().split()))
a = list(set(a))
a.sort()

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

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

start = 0
a_max = a[-1]
while a_max * (start + 0.5) <= m:
    flag = True
    for i in range(len(a)-1):
        num = (a_max * (start + 0.5) / a[i]) - 0.5
        if num.is_integer():
            continue
        else:
            flag = False
            break
    if flag:
        break
    else:
        start += 1

if a_max * (start + 0.5) > m:
    print(0)
    exit()

ans = 0
base_num = int(a_max * (start + 0.5))

d = reduce(lcm, a)
ans = int(1 + ((m - base_num) // d))
print(ans)

Submission status: Accepted

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])
    if l>M:
        break
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: Accepted

Solution code:
def a():
    N,M = map(int,input().split())
    B = list(map(lambda x: int(x)//2,input().split()))

    def gcd(n,m):
        while n:
            m,n = [n,m%n]
        return m

    su = 1
    for b in B:
        su *= b // gcd(su,b)
        if su > M:
            return 0

    for _ in filter(lambda x:(su//x)%2==0,B):
        return 0

    return M//su - M//(su*2)

print(a())

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
a = list(map(int,input().split()))
cnt = 0
while True:
  if a[0] % 2 == 0:
    a[0] //= 2
    cnt += 1
  else:
    break
div = 2 ** cnt
if div != 1:
  m //= (div//2)
for i in range(1,n):
  if a[i] % div == 0:
    a[i] //= div
    if a[i] % 2 == 0:
      print(0)
      break
  else:
    print(0)
    break
  if cnt == 0:
    print(0)
    break
else:
  #print(a)
  lcm = a[0]
  for i in range(1,n):
    big,sml = a[i],lcm
    while sml != 0:
      big,sml = sml,big%sml
    lcm *= a[i] // big
  #print(lcm)
  ans = m // (2*lcm)
  #print(ans)
  if m % (2*lcm) >= lcm:
    ans += 1
  print(ans)

Submission status: Accepted

Solution code:

from functools import lru_cache
n, m = map(int, input().split())
aa = set(list(map(int, input().split())))

@lru_cache(maxsize=4095)
def gcd(a,b):
    if a < b:
        a, b = b, a
    while  a % b != 0:
        a, b = b, a % b
    return b
@lru_cache(maxsize=4095)
def lcm(c,d):
    return c*d // gcd(c,d)
# half all the array
A = set([a//2 for a in aa])
# calc lcm of all
LCM = 1
for each in A:
    LCM = lcm(LCM, each)
    if LCM > m:
        print(0)
        break
else:
    for each in A:
        if (LCM // each) % 2 == 0:
            print(0)
            break
    else:
        print(m//LCM - m//(LCM*2))

Submission status: Accepted

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

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

a = sorted(list(set(a)))
b = [a[i]//2 for i in range(len(a))]

owa = 0
saiko = b[0]

for i in range(1,len(a)):
    t1 = b[i]
    koe = gcd(saiko,t1)
    saiko = (saiko*t1)//koe
    if (saiko//b[i])%2 == 0:
        break

for i in range(len(a)):
    check = saiko//(b[i])
    if check%2 == 0:
        owa = 1
        break

if owa == 1:
    print(0)
else:
    if (M//saiko)%2 == 0:
        print((M//saiko)//2 )
    else:
        print(((M//saiko)+1)//2)