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:
def main():
    from fractions import gcd
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a = [i//2 for i in a]
    g = a[0]

    s = set()
    for i in a:
        j = i
        cnt = 0
        while j % 2 == 0:
            j //= 2
            cnt += 1
        s.add(cnt)
    if len(s) >= 1:
        if len(s) == 1:
            for i in range(n-1):
                g = (g*a[i+1])//gcd(g, a[i+1])
            print((m//g+1)//2)
            return
        else:
            print(0)
            return
    for i in range(n-1):
        g = (g*a[i+1])//gcd(g, a[i+1])

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


main()

Submission status: Accepted

Solution code:
import fractions


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


# 2で割れる回数を数える
def f(x):
    t = 0
    while (x % 2 == 0):
        x //= 2
        t += 1
    return t


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

cnt = f(a[0])
for i in range(n):
    # 割れる回数が一致しなければ不可
    if cnt != f(a[i]):
        print(0)
        exit()
    a[i] >>= cnt
m >>= cnt
num = 1
for i in range(n):
    num = lcm(num, a[i])
    if num > m:
        print(0)
        exit()
m //= num
ans = (m + 1) // 2
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:
#!/usr/bin/env python3
import sys
import fractions as f
from functools import reduce

def lcm2(x,y):
    return (x * y)//f.gcd(x,y)

def count2f(a):
    i=0
    while a%2==0:
        a//=2
        i+=1
    return i


def solve(N: int, M: int, a: "List[int]"):
    for i in range(N):
        a[i]//=2

    st=count2f(a[0])
    a[0]//=2**st
    for i in range(1, N):
        sti=count2f(a[i])
        a[i]//=2**st
        if st!=sti:
            print(0)
            return
    M//=2**st

    l=1
    for i in range(N):
        l=lcm2(l, a[i])
        if l>10**9:
            print(0)
            return

    print((M+l)//l//2)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, a)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def d_semi_common_multiple():
    from fractions import gcd
    from functools import reduce
    N, M = [int(i) for i in input().split()]
    A = [int(i) // 2 for i in input().split()]  # 先に2で割っておく

    def count_divide_2(n):
        ret = 0
        while n % 2 == 0:
            ret += 1
            n //= 2
        return ret

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

    # A の全要素について、2で割れる回数は等しいか？
    tmp = count_divide_2(A[0])
    for a in A:
        if count_divide_2(a) != tmp:
            return 0

    t = reduce(lambda x, y: lcm(x, y), A)
    return M // t - M // (2 * t)

print(d_semi_common_multiple())

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

#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 = map(int,readline().split())
A = list(map(int,readline().split()))

B = [A[i]//2 for i in range(N)]
ans = 1

dev_c = 0
while A[0]%2 != 1:
    A[0] = A[0]//2
    dev_c += 1
#print(dev_c)

for i in range(1,N):
    dev_c2 = 0
    while A[i]%2 != 1:
        A[i] = A[i]//2
        dev_c2 += 1
    if dev_c != dev_c2:
        ans = 0
        break

l = B[0]
if ans == 1:
    for i in range(N):
        l = lcm(l,B[i])

#print(l)

if ans != 0:
    ans = (M//l+1)//2

print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

#a,bの最大公約数
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
#a,bの最小公倍数
def lcm(a,b):
    return a*b//gcd(a,b)

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

B = [A[i]//2 for i in range(N)]
ans = 1

dev_c = 0
while A[0]%2 != 1:
    A[0] = A[0]//2
    dev_c += 1
#print(dev_c)

for i in range(1,N):
    dev_c2 = 0
    while A[i]%2 != 1:
        A[i] = A[i]//2
        dev_c2 += 1
    if dev_c != dev_c2:
        ans = 0
        break

l = B[0]
if ans == 1:
    for i in range(N):
        l = lcm(l,B[i])

#print(l)

if ans != 0:
    ans = (M//l+1)//2

print(ans)

Submission status: Accepted

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

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


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


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


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


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


def listdivide(list):
    numpy = np.array(list)
    numpy = numpy//2
    return numpy.tolist()


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


# while gcd_list(an) % 2 == 0:
#     print(gcd_list(an))
an = listdivide(an)

t = divide2(an[0])
for i in range(1, N):
    if divide2(an[i]) != t:
        print(0)
        sys.exit()

for i in range(t):
    an = listdivide(an)
    M = M // 2

LCM = lcm_list(an)

if LCM > M == 0:
    print(0)
else:
    print(-(-(M // LCM)//2))

Submission status: Accepted

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

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


def main():
    N,M = map(int, input().split())
    a = [int(i) for i in input().split()]
    A = np.array(a)
    m = A // 2

    while np.all(A % 2 == 0):
        A //= 2
    
    c = np.count_nonzero(A % 2 == 1)
    if c != N:
        print(0)
        exit()

    lcm = reduce(lcm_base, m, 1)
    #print(lcm)

    print(int((M / lcm + 1) // 2))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

N, M, *A = map(int, open(0).read().split())

Y = reduce(lambda a, b: a * b // gcd(a, b), A)

print(M // (Y // 2) - (M // Y) if all((Y // a) % 2 for a in A) else 0)

Submission status: Accepted

Solution code:
from fractions import gcd

def lcm(a):
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

def f(x):
    cnt = 0
    for c in reversed(bin(x)):
        if c == '0':
            cnt += 1
        else:
            return cnt
    return cnt

n, m = map(int, input().split())
ai = list(map(lambda x: x//2 , list(map(int, input().split()))))

t = f(ai[0])
for i, a in enumerate(ai):
    if f(a) != t:
        print('0')
        exit()
    ai[i] = a >> t

m = m >> t

l = lcm(ai)
i = m // l
ans = (i + 1) // 2

print(ans)

Submission status: Accepted

Solution code:
import fractions

n, m = map(int, input().split())
a = list(map(int, input().split()))
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

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

now = a[0]
for i in range(1, n):
	now = lcm(now, a[i])
	if now > 2 * m:
		print(0)
		exit(0)

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

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

Submission status: Accepted

Solution code:
import fractions #math.gcdは非対応なので解答にはfractions.gcdを使う
n,m = list(map(int,input().split()))
a = list(map(int,input().split()))
lcm = 1
for i in range(n):
    a[i]//=2
    lcm = lcm*a[i]//fractions.gcd(lcm,a[i])
flag = False
loopf = True
while loopf:
    tmp = a[0]%2
    for i in range(1,n):
        if a[i]%2!=tmp:
            flag = True
            loopf = False
            break
    if tmp==1 and loopf:
        loopf = False
    if tmp==0:
        for i in range(n):
            a[i]//=2
        
if flag:
    print(0)
else:
    tmp = m//lcm
    print((tmp+1)//2)

Submission status: Accepted

Solution code:
import fractions
import math
n,m = map(int,input().split())
a = list(map(int, input().split()))
a = set(a)
c = set()
l = 1
for i in a:
    l = l * i // fractions.gcd(l,i)
    if l // 2 > m:
        ans = 0
        break
    count = 0
    while True:
        if (i>>count) % 2 == 0:
            count += 1
        else:
            c.add(count)
            break
    if len(c) > 1:
        ans = 0
        break
else:
    ans = (m + l // 2) // l

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

N, M, *A = map(int, open(0).read().split())

Y = reduce(lambda a, b: a * b // gcd(a, b), A)

if any((Y // a) % 2 == 0 for a in A):
    print(0)
    quit()

print(M // (Y // 2) - (M // Y))

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce
N,M = map(int, input().split())
A = list(set(map(lambda x: int(x)//2, input().split())))
lcm = A[0]
for a in A[1:]:
  l = lcm*a//gcd(lcm,a)
  if not (l//lcm%2 and l//a%2):
    print(0)
    exit()
  lcm = l
print((M//lcm+1)//2)

Submission status: Accepted

Solution code:
import fractions
from functools import reduce
n,m = map(int,input().split())
a = list(map(int,input().split()))
for i in range(n):
    a[i] = a[i]//2
wa=[]
for i in range(n):
    p=a[i]
    f=0
    while p%2==0:
        p=p//2
        f+=1
    wa.append(f)
if max(wa)!=min(wa):
    print(0)
    exit()
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

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

lcm = lcm_list(a)#aの要素をすべて2で割った数列の最小公倍数
#にぶんたんさく(lcmをｘ倍してｍを超えないようなギリギリのｘ)
bottom = 0
top = m+1#m//2くらいで十分だけど大きめにとる
while top - bottom > 1:
    middle = (top+bottom )//2
    if lcm * middle <= m:
        bottom = middle
    else:
        top = middle



print(( bottom+1)//2)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


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 StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['No', 'Yes']
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


show_flg = True
show_flg = False


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


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


def lcm_n(A, N):
    # A = sorted(A)
    ans = A[0]
    # for i in range(1, N):
    #     ans = fractions.gcd(A[i], ans)
    for i in range(1, N):
        ans = lcm(ans, A[i])
    return ans


def main():
    N, M = MI()
    a = LI()

    if any([i % 2 for i in a]):
        print(0)
        return

    n = lcm_n(a, N)
    n = n // 2

    if not all([(2 * n // x) % 2 for x in a]):
        print(0)
        return

    if n > M:
        print(0)
    else:
        t = M // n
        if t % 2 == 0:
            t -= 1
        print(t // 2 + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

lcm = lambda a, b: a * b // gcd(a, b)

N, M, *A = map(int, open(0).read().split())

Y = reduce(lcm, A)

if any((Y // a) % 2 == 0 for a in A):
    print(0)
    quit()

print(M // (Y // 2) - (M // Y))

Submission status: Accepted

Solution code:
import fractions


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


def div_count_by_2(x):
    count = 0
    while x % 2 == 0:
        count += 1
        x //= 2

    return count


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

num = A[0]
count = div_count_by_2(num)
for a in A:
    if count == div_count_by_2(a):
        continue
    else:
        print(0)
        exit()

x = A[0]//2
for a in A:
    x = lcm(x, a//2)

ans = m//x - m//(2*x)
print(ans)

Submission status: Accepted

Solution code:
import fractions
import math
n,m = map(int,input().split())
a = list(map(int, input().split()))
s = set(a)
c = set()
l = 1
k = (a[0] // 2) % 2
for i in a:
    l = l * i // fractions.gcd(l,i)
    if l // 2 > m:
        ans = 0
        break
    count = 0
    while True:
        if (i>>count) % 2 == 0:
            count += 1
        else:
            c.add(count)
            break
    if len(c) > 1:
        ans = 0
        break
else:
    ans = (m + l // 2) // l

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

lcm = lambda a, b: a * b // gcd(a, b)

N, M, *A = map(int, open(0).read().split())

Y = A[0]
for a in A[1:]:
    Y = lcm(a, Y)

if any((Y // a) % 2 == 0 for a in A):
    print(0)
    quit()

print(M // (Y // 2) - (M // Y))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


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 StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['No', 'Yes']
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


show_flg = True
show_flg = False


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


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


def good(A, N):
    # A = sorted(A)
    ans = A[0]
    # for i in range(1, N):
    #     ans = fractions.gcd(A[i], ans)
    for i in range(1, N):
        ans = lcm(ans, A[i])
    return ans


def main():
    N, M = MI()
    a = LI()

    if any([i % 2 for i in a]):
        print(0)
        return

    # ha = [x//2 for x in a]
    # n = good([x//2 for x in a], N)
    # # print(n)

    # if not all([(n // x) % 2 for x in ha]):
    #     print(0)
    #     return

    n = good(a, N)
    n = n // 2
    # n = n * 2

    if not all([(2 * n // x) % 2 for x in a]):
        print(0)
        return

    if n > M:
        print(0)
    else:
        t = M // n
        if t % 2 == 0:
            t -= 1
        print(t // 2 + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# D - Semi Common Multiple

import fractions
from functools import reduce

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

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

l = reduce(lcm, a_d)

for i in a_d:
    if (l//i) % 2 == 0: # 含まれる因数2の個数が異なるa_i, a_jがあるとき
        print(0)
        break
else:
    if (M//l) % 2 == 0:
        print((M//l)//2)
    else:
        print((M//l)//2 + 1)

Submission status: Accepted

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


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

    t = 1
    for a in A:
        if a & 1:
            print(0)
            return
        else:
            t = lcm(t, a//2)
    for a in A:
        if t % a == 0:
            print(0)
            exit()

    print(-(-(M//t)//2))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions import gcd
n,m=map(int,input().split())
a=list(map(int,input().split()))
wa=[]
for i in range(n):
    p=a[i]
    f=0
    while p%2==0:
        p=p//2
        f+=1
    wa.append(f)
if max(wa)!=min(wa):
    print(0)
    exit()
ans = a[0]
for i in range(1, n):
    ans = ans * a[i] // gcd(ans, a[i])
g=ans//2
kai=m//g
kai=-(-kai//2)
print(kai)

Submission status: Accepted

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


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

    t = 1
    for a in A:
        if a & 1:
            print(0)
            return
        else:
            t = lcm(t, a//2)
    for a in A:
        if t % a == 0:
            print(0)
            exit()

    ans = M//t/2
    ans = -(-ans//1)
    print(int(ans))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


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 StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['No', 'Yes']
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


show_flg = True
show_flg = False


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


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


def good(A, N):
    # A = sorted(A)
    ans = A[0]
    # for i in range(1, N):
    #     ans = fractions.gcd(A[i], ans)
    for i in range(1, N):
        ans = lcm(ans, A[i])
    return ans


def main():
    N, M = MI()
    a = LI()

    if any([i % 2 for i in a]):
        print(0)
        return

    ha = [x//2 for x in a]
    n = good([x//2 for x in a], N)
    # print(n)

    if not all([(n // x) % 2 for x in ha]):
        print(0)
        return

    # print(n, n // 2, M)
    if n > M:
        print(0)
    else:
        t = M // n
        if t % 2 == 0:
            t -= 1
        print(t // 2 + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

from sys import stdin
from math import floor

N, M = (int(wd) for wd in stdin.readline().split())
a = [int(wd) for wd in stdin.readline().split()]

def kouyakusuu(g1, g2):
    if g1 < g2:
        return kouyakusuu(g2, g1)
    if g2 == 0:
        return g1
    return kouyakusuu(g2, g1 % g2)

def koubaisuu(g1, g2):
    return (g1 * g2) // kouyakusuu(g1, g2)




def solve2(N, M, a):
    ret = 1
    cnt2 = 1
    while a[0] % (2**cnt2) == 0: cnt2 += 1
    ng = 2 ** cnt2
    cnt2 -= 1
    ok = 2 ** cnt2
    for aa in a:
        if aa % ng == 0:
            return 0
        if aa % ok != 0:
            return 0
        ret = koubaisuu(ret, aa // 2)
    return int(floor((M - ret) / (ret * 2)) + 1)

print(solve2(N, M, a))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
from fractions import gcd

n, m = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]
fact2 = 0
tmp = a[0]
while tmp > 0 and tmp % 2 == 0:
    tmp //= 2
    fact2 += 1

for item in a:
    cnt = 0
    while item > 0 and item % 2 == 0:
        item //= 2
        cnt += 1
    if cnt != fact2:
        print("0")
        exit()

lcm = 1
for item in a:
    lcm = (item//2) * lcm // gcd(item//2, lcm)
print((m + lcm) // (2 * lcm))

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

def lcm(x, y):
  g = gcd(x, y)
  x //= g
  y //= g
  if x&y&1:
    l = x*y*g
    if l > 10**9:
      return 0
    return l
  return 0
n, m = map(int, input().split())
A = list(map(lambda x: int(x)//2, input().split()))
k = reduce(lcm, A)
if k == 0:
  print(0)
else:
  print(((m//k)+1)//2)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys

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

# lcm & gcd not math
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

from functools import reduce
def lcm_multi(num_list):
    return reduce(lcm, num_list, 1)

# number of being able to divide by 2 in all of list
def get_num_can_divide_two(num_list):
    bin_num_or = 0
    for now_num in num_list:
        bin_num_or |= now_num

    num_can_divide_two = 0
    while bin_num_or > 0:
        can_divede_two = bin_num_or & 1
        if can_divede_two:
            break
        bin_num_or >>= 1
        num_can_divide_two += 1

    return(num_can_divide_two)

num_can_divide_two = get_num_can_divide_two(a_list)

for i in range(N):
    if (a_list[i] // (2 ** num_can_divide_two)) % 2 == 0:
        print(0)
        sys.exit()
        

lcm_num =  lcm_multi(a_list)

print((M - lcm_num // 2) // lcm_num + 1)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

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

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

def sub_by_2(n):
    cnt = 0
    while n % 2 == 0:
        cnt += 1
        n //= 2
    return cnt

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

lcm_2 = [sub_by_2(v // 2) for v in A]
if all(lcm_2[0] == v for v in lcm_2):
    num = lcm_list([v // 2 for v in A])
    ans = M // num
    print(ans // 2 + ans % 2)
else:
    print(0)

Submission status: Accepted

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

n, m = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]

num = [0] * n

count = None
for i, v in enumerate(a):
    num[i] = v // 2

    _v = num[i]
    _count = 0
    while True:
        if _v % 2 == 0:
            _v = _v // 2
            _count += 1
        else:
            break
    if count is None:
        count = _count
    elif count != _count:
        print(0)
        sys.exit(0)

import fractions
import functools
# FYI: https://note.nkmk.me/python-gcd-lcm/
def lcm(numbers):
    return functools.reduce(lambda x, y: (x * y) // fractions.gcd(x, y), numbers, 1)

point = lcm(num)
print(int((m // point) / 2 + 0.5))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read

n,m = [int(i) for i in readline().split()]
a = [int(i)//2 for i in read().split()]

#2で割れる回数
def num_of_2(x):
    c = 0
    while x%2 == 0:
        c  += 1
        x //= 2
    return c

#最小公倍数
from fractions import gcd
def lcm(x,y):
    return x//(gcd(x,y))*y

#2で割れる回数が違ったらアウト
a0 = num_of_2(a[0])
if any([num_of_2(i) != a0 for i in a]):
    print(0)
else:
    #最小公倍数が c のとき、c,3c,5c,... が条件をみたす
    c = 1
    for i in a:
        c = lcm(c,i)
        if c > m: break #mを超えたらもう無意味
    print((m//c+1)//2)

Submission status: Accepted

Solution code:
def lcm(a,m):
    from fractions import gcd
    x = a[0]
    for i in range(1, len(a)):
        
        x = (x * a[i]) // gcd(x, a[i])
        if x > m:
            return m+1
    return x

def count2div(n):
    count=0
    while not n%2:
        n/=2
        count+=1
    return count

n,m = map(int, input().split())
a = list(map(int, input().split()))
b = [i//2 for i in a]
c = [0 for i in a]
b_f = True
for i in range(n):
    c[i] = count2div(b[i])
for i in range(n-1):
    if c[i] != c[i+1]:
        b_f = False
lcm = lcm(b,m)
i=1
count=0
if m >= lcm:
    m-=lcm
    count = m//(lcm*2) + 1
if b_f:
    print(count)
else:
    print(0)

Submission status: Accepted

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


T=1
for b in B:
    if not (Mb//b)%2==1:
        T=0
if T==1:
    gmp=Mb




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

Submission status: Accepted

Solution code:
import fractions
import functools

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

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


n, m = map(int, input().split())
aset = set(map(int, input().split()))
aset = list(x // 2 for x in aset)

llcm = lcm(*aset)

for a in aset:
    if (llcm // a) % 2 == 0:
        ans = 0
        break
else:
    ans = (m // llcm + 1) // 2

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
def lcm(p,q):
    return p*q//gcd(p,q)
N, M = map(int, input().split())
a = [int(i)//2 for i in input().split()]
x = 1
for i in range(N):
  x = lcm(x, a[i])
for i in range(N):
  if (x//a[i])%2==0:
    print(0)
    exit()
num = M//x
print(num//2 if num%2==0 else num//2+1)

Submission status: Accepted

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

def lcm(a, b):
    return a*b//gcd(a,b)
#import sys
#input = sys.stdin.readline
def main():
    N, M = map( int, input().split())
    A = list( map( int, input().split()))
    B = [a for a in A]
    T = 1
    L = 1
    C = [0]*N
    for i in range(N):
        for _ in range(30):
            if B[i]%2 == 0:
                B[i] //= 2
                C[i] += 1
            else:
                break
    p = C[0]
    for i in range(N-1):
        if p != C[i+1]:
            print(0)
            return
    q = pow(2,p)
    t = 1
    for i in range(N):
        t = lcm(t,A[i]//2)
    if t > M:
        print(0)
        return

    print((M-t)//(t*2) + 1)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def count_2(x):
    count = 0
    while x%2 == 0:
        count += 1
        x /= 2
    return count

flag = True

for i in range(N-1):
    if count_2(a[i]) != count_2(a[i+1]):
        flag = False
        break
    
if not flag:
    print(0)
    exit()

lcm=1
for i in range(N):
    lcm = lcm*a[i]//gcd(a[i],lcm)

ans=0
if lcm//2<=M:
    ans=(M-lcm//2)//lcm+1

print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
import fractions
B=[]
C=[]
for i in A:
  B.append(i//2)
cnt=0
for i in A:
  C.append(cnt)
  cnt=0
  while i%2==0:
    i/=2
    cnt+=1
cnt=0
y=A[-1]
while y%2==0:
  y/=2
  cnt+=1
C.append(cnt)
D=C[1:]
if len(set(D))!=1:
  print(0)
else:

  ans = B[0]
  for i in range(1, N):
    ans=ans*B[i] // fractions.gcd(ans,B[i])

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

Submission status: Accepted

Solution code:
def ng(a):
    b = []
    for x in a:
        two = 0
        while x%2 == 0:
            x //= 2
            two += 1
        b.append(two)
    return sum(b) != b[0]*len(b)

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

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

def fail():
    print(0)
    exit(0)

n, m = map(int, input().split())
a = [int(x)//2 for x in input().split()]

if ng(a):
    fail()

lc = 1
for x in a:
    lc = lcm(lc, x)
    if lc > m:
        fail()

ret = 1
m -= lc
ret += m//(2*lc)
print(ret)

Submission status: Accepted

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

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

N, M = map(int, input().split())
A = list(map(int, input().split()))
res = 1
for a in A:
    res = lcm(res, a)

cnt = 0
while A[0] % 2 == 0:
    A[0] //= 2;
    cnt += 1

ok = True
for i in range(1, N):
    c = 0
    while A[i] % 2 == 0:
        A[i] //= 2;
        c+= 1
    if cnt != c :ok = False
    
if res // 2 > M or ok == False: print(0)
else: print((M + res//2 ) // res)

Submission status: Accepted

Solution code:
import sys
import fractions

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

def div_count(n):
    count=0
    for i in range(1,100):
        if n%2**i!=0:
            count=i
            break
    return count
    

for i in range(len(a)):
    a[i]//=2

for i in range(1,len(a)):
    if div_count(a[i-1])!=div_count(a[i]):
        print(0)
        sys.exit()

_min=a[0]
for i in range(1, n):
    _min = _min * a[i] // fractions.gcd(_min, a[i])

print(m//_min-(m//_min)//2)

Submission status: Accepted

Solution code:
from functools import reduce

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

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

def div_ceil(x, y): return (x + y - 1) // y

N, M = map(int, input().split())
*A, = map(int, input().split())
A = list(set([a // 2 for a in A]))
L = reduce(lcm, A)
for a in A:
    if (L // a) % 2 == 0:
        ans = 0
        break
else:
    ans = div_ceil(M // L, 2)
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
import sys

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

cnt = 1
min_a = min(a)
while min_a % 2 == 0:
    cnt *= 2
    min_a = min_a // 2

ans = 1
for i in a:
    if (i // cnt) % 2 == 0:
        print(0)
        sys.exit()
    ans = (ans * i) // gcd(ans, i)

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