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:

# 最小公倍数(mathは3.5以降) fractions
from functools import reduce
import fractions #(2020-0405  fractions→math)
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y) # 「//」はフロートにせずにintにする
def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

N,M = (int(x) for x in input().split())
A = list(map(int, input().split()))
lcm         =lcm_list(A)
han_lcm     =lcm//2
han_lcm_num =M//han_lcm
han_lcm_num =(han_lcm_num +1)//2 #偶数を除く

#半公倍数がA自身の中にある時は✖
if han_lcm in A:
    han_lcm_num =0
#半公倍数がaiで割り切れるときは✖
for a in A:
    if han_lcm % a ==0:
        han_lcm_num =0
print(han_lcm_num)

Submission status: Accepted

Solution code:
from fractions import gcd

n, m = map(int, input().split())
a = list(map(int, input().split()))
b = [a[i]//2 for i in range(n)]
lcm_a = 1
for i in range(n):
    lcm_a = (lcm_a * b[i]) // gcd(lcm_a, b[i])
for i in range(n):
    if (lcm_a//b[i]) % 2 == 0:
        print(0)
        exit()
if m < lcm_a:
    print(0)
else:
    m -= lcm_a
    print(1 + m // (lcm_a*2))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

##### 進数の変換 #####
# bin_str = bin(i)
# oct_str = oct(i)
# hex_str = hex(i)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,M = inputMap()
	A = inputList()

	lcm_A = 1
	for i in A:
		ii = i // 2
		lcm_A = lcm(lcm_A,ii)

	if lcm_A > M:
		print(0)
		sys.exit()

	wareru2 = shino(A[0])
	for i in A:
		tmp = shino(i)
		if tmp == wareru2:
			pass
		else:
			print(0)
			sys.exit()

	ans = M // lcm_A
	ans = -((-1 * ans) // 2)
	print(ans)


def shino(x):
	ret = 0
	while True:
		if x % 2 == 0:
			ret += 1
			x = x // 2
		else:
			return ret


# a と b の最大公約数を求めるユークリッドの互除法
def gcd(a, b):
	if a > b:
		a, b = b, a

	while a > 0:
		a, b = b % a, a
	return b

# a と b の最小公倍数を求める。以下の公式を使用
# a x b == (a と b の最大公約数) x (a と b の最小公売数)
def lcm(a, b):
	g = gcd(a, b)
	return a // g * b

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# N 個のボールを K グループに分ける場合のパターン数
def sunuke(N, K, mod=10**9+7):
	if N < K or K-1 < 0:
		return 0
	else:
		return combination(N-1, K-1, mod)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:

def resolve():
    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())
    A = list(map(int, input().split()))
    # Aは偶数。2*Bと書ける。少数をなくすため, B*(2p + 1)と式変形
    # 2を使用した為、2で割る
    B = [a//2 for a in A]

    # X = B[k] * (2p + 1)
    # これを見てみると、B[k]の奇数倍の数が作られることになる。
    # 公倍数は最小公倍数の倍数となるという性質がある。
    # 全部の数の最小公倍数を取って、M÷最小公倍数をすると答えが得られる。
    def solve():
        lc = 1
        for i in range(N):
            lc = lcm(lc, B[i])

        # 変形式より、XはB*奇数倍されないといけないX//B[k] == (2p+1)
        # なので、偶数になるとダメ
        for i in range(N):
            if (lc//B[i]) % 2 == 0:
                return 0
        ans = M//lc
        ans = (ans+1)//2
        return ans

    print(solve())

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys
import fractions
sys.setrecursionlimit(10**9)

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

n=len(alist)


def sks(n):
	global alist
	if n == 1:
		return alist[0]
	else:
		tmp=sks(n-1)
		return tmp*alist[n-1]//fractions.gcd(tmp,alist[n-1])

sk = sks(n)
gomi=sk//2

for a in alist:
	if (gomi-a//2)%a != 0:
		print(0)
		sys.exit()

print(int((m+gomi)//sk))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from fractions import gcd
import math

def main():
    N, M = map(int, input().split())
    a = list(map(int, input().split()))
    tmp = 1
    count = None
    for i in range(N):
      tmp = (tmp * a[i]//2) // gcd(tmp,a[i]//2)
      c = 0
      n = a[i]//2
      while n % 2 == 0:
        c += 1
        n //= 2
      if i == 0:
        count = c
      elif count != c:
        print(0)
        exit()
    print((M//tmp +1)//2)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions import gcd
import math

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

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = [0]*N
cnt = [0]*N

for i in range(N):
  a = A[i]
  B[i] = a//2
  while a % 2 == 0:
    a /= 2
    cnt[i] += 1

cnt = set(cnt)
if len(cnt) != 1:
  print(0)
  exit()

x = lcm(B)
ans = 0

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

Submission status: Accepted

Solution code:
import math

def makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]

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

# 最小公倍数
# ユークリッドの互除法
def lcm(a, b): 
    def gcd(a, b):  # a >= b
        if b == 0:
            return a
        else:
            return gcd(b, a % b)
    
    return a * b // gcd(a, b)

c = 1
for e in a:
    c = lcm(c, e // 2)
hoge = [ (c // (e // 2)) % 2 == 1 for e in a ]

if all(hoge):
    ans = 0
    if c <= M:
        ans += 1
        M -= c
    ans += M // (c * 2)
    print(ans)
else:
    print(0)

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit


def gcd(x, y):
    if x % y == 0:
        return y
    return gcd(y, x % y)


def main():
    input = stdin.buffer.readline
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a = [a[i] // 2 for i in range(n)]
    a = list(set(a))
    n = len(a)
    lcm = 1
    for i in range(n):
        lcm = lcm * a[i] // gcd(lcm, a[i])
    for i in range(n):
        if (lcm // a[i] % 2) == 0:
            print(0)
            exit()
    ans = m // lcm
    print(ans - ans // 2)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    from fractions import gcd

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

    l = 1
    div2_count = count_div2(A[0])

    for a in A:
        l = l*a // gcd(l, a)
        c = count_div2(a)
        if div2_count != count_div2(a):
            print(0)
            exit()
    #     div2_count.append(max(count_div2(a), 1))
    # print(div2_count)
    # l *= min(div2_count)
    # print(l)
    # l の奇数倍が1より大きくM以下にいくつあるか

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


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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from collections import defaultdict
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import numpy as np
INF = float("inf")
#d = defaultdict(int)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
N,M = map(int,input().split())
a = list(map(int,input().split()))
cnt = 0
flag = 0
order = 0
while True:
    for i in range(N):
        if a[i] % 2 == 0:
            a[i] = a[i] // 2
        else:
            cnt += 1
    if cnt == 0:
        order += 1
        continue
    elif cnt == N:
        break
    else:
        print(0)
        flag = 1
        break
if flag == 0:
    S = a[0]
    for i in range(1,N):
        p = fractions.gcd(S,a[i])
        S = (S*a[i]) // p
    q = S*(2**(order-1))
    loc = M // q
    if loc % 2 == 1:
        loc += 1
    print(loc // 2)

Submission status: Accepted

Solution code:
import fractions
from functools import reduce

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

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

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

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

def count_factorize(n):
    counter = 0
    while n % 2 == 0:
        counter += 1
        n //= 2
    return counter

mod = count_factorize(a[0])
for i in range(1, n):
    if count_factorize(a[i]) != mod:
        print(0)
        exit()
lcm_a = lcm(*a)
print(m // (lcm_a//2) - m // lcm_a)

Submission status: Accepted

Solution code:
"""
x = ai(p+0.5)
0.5が入っていると整数として扱いづらいので、aiが偶数であることを利用して以下のように変形
x = ai'(2p+1)
ai' = 2ai
ここで2p+1が奇数であることから、xおよびai'が2で割れる回数は同じでなければならない。
2で割れる回数をtとすると、
x' = ai''(2p+1)
x' = x/(2^t)
ai'' = ai'/(2^t)
Mも2^tで割っておく。
M' = M/(2^t)
Xとして何が考えられるかは、まずai''の最小公倍数Lが考えられる
lcm(ai'') = L
さらに、Lの奇数倍も考えられる
したがって答えは、M'/2Lの小数点以下切り上げたもの
"""

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

def func(x):
    """2で何回割れるか"""
    res = 0
    while x%2 == 0:
        x //= 2
        res += 1
    return res

#from math import gcd # v3.5以降
from fractions import gcd # v3.4以前
from functools import reduce

def lcm_base(x, y):
    """2つの値の最小公倍数"""
    return (x * y) // gcd(x, y)

def lcm(*numbers):
    """3つ以上の値の最小公倍数"""
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    """3つ以上の値の最小公倍数"""
    return reduce(lcm_base, numbers, 1)

def main(n,m,a):
    ans = 0
    # a -> a'
    for i in range(n):
        if a[i]%2 == 1:
            print(0)
            return
        a[i] //= 2

    # a' -> a''
    t = func(a[0])
    for i in range(n):
        if func(a[i]) != t:
            print(0)
            return
        a[i] >>= t # a[i] //= 2^t
    m >>= t

    l = 1
    for i in range(n):
        l = lcm(l, a[i])
        if l > m:
            print(0)
            return

    m //= l
    ans += (m+1)//2
    print(ans)
    
main(n,m,a)

Submission status: Accepted

Solution code:
from fractions import gcd


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


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

lcm, div2 = a[0], count(a[0])
flag = True

for i in range(1, N):
    lcm = lcm // gcd(lcm, a[i]) * a[i]
    if count(a[i]) != div2:
        flag = False

if flag:
    print((M // lcm + 1) // 2)
else:
    print(0)

Submission status: Accepted

Solution code:
import fractions
import numpy as np

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

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

bef = 1
LCM = 1
ans = []
for i,a in enumerate(A):
    LCM = lcm(LCM,a)
    if bef !=1:
        c, d = bef, a//2
        while c % 2 == 0 and d % 2 == 0:
            c //= 2
            d //= 2
        if c%2 != d%2:
            print(0)
            exit()
    
    b = a//2
    bef = lcm(bef,b)
    ans.append(bef)

print((M-bef)//LCM+1)

Submission status: Accepted

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

def lcm(a, b):
    return a*b // gcd(a, b)
"""
akが偶数だから、bk=2akとして、
bk × (2p + 1)を満たすpが存在すれば良い
2p+1は奇数のため、Xとbkの2の素因数は一致しなければならない
akに含まれる最大の2^kを探す。
"""
if len(a) == 1: lcm_all = a[0]//2
else: lcm_all = lcm(a[0]//2, a[1]//2)
amax = 0
for i in range(1, n):
    lcm_all = lcm(lcm_all, a[i]//2)
    amax = max(amax, a[i]//2)

f = True
if lcm_all > m:
    f = False
for i in range(n):
    if n == 1: break
    if (lcm_all//(a[i]//2))%2 == 0:
        # akの2の約数の数がそろわないので、どんな奇数を掛けても共通のXを作れない
        f = False
if f:
    # amaxの奇数倍でmを超えないもの
    ans = (m // lcm_all + 1)//2
    print(ans)
else:
    print(0)

Submission status: Accepted

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

A = list(set(map(int, input().split(" "))))
G = A.copy()
 
while not any(x % 2 for x in G):
    G = [i // 2 for i in G]
 
if not all(x % 2 for x in G):
    print(0)
    exit(0)
    
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
    
def lcm(a, b):
    return a * b // gcd(a, b)
    
total = 1

for x in A:
    total = lcm(total, x // 2)

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split(" "))
 
a = list(set(map(int, input().split(" "))))
g = a.copy()
 
while not any(x%2 for x in g): g = [i //2 for i in g]
 
if not all(x%2 for x in g): print(0); exit(0)
 
def gcd(a, b):
 
    while b:
 
        a, b = b, a % b
    return a
 
def lcm(a, b):
    return a * b // gcd(a, b)
 
 
tot = 1
 
for x in a: tot = lcm(tot, x//2)
print((M//tot+1)//2)

Submission status: Accepted

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

df = l[0]
#print("df", df)

s = len(bin(df)) - 2
#print("s", s)

count = 0
for i in range(s):
    if df % 2:
        break
    df //= 2
    count += 1
    
#print("count", count)

l = tuple(map(lambda x:x // (2**count), l))
#print("l", l)

for i in l:
    if i % 2 == 0:
        print(0)
        exit()

def gcd(a, k):
    if k:
        return gcd(k, a % k)
    return a

ans = l[0]
for i in l:
    ans = ans * i // gcd(ans, i)

print(-(-(M // (ans * 2**(count - 1))) // 2))

Submission status: Accepted

Solution code:
import sys
N,M=map(int,input().split())
A=list(set(map(int,input().split())))
N=len(A)
A=[a//2 for a in A]
 
def f(x):
    cnt=0
    while x%2==0:
        x//=2
        cnt+=1
    return cnt
C=f(A[0])
for a in A:
    if f(a)!=C:
        print(0)
        sys.exit()
def lcm(x,y):
    xy=x*y
    while y!=0:
        x,y=y,x%y
    return xy//x
LCM=A[0]
for i in range(1,N):
    LCM=lcm(LCM,A[i])
if LCM>M:
    ans=0
else:
    M//=LCM
    ans=(M+1)//2
print(ans)

Submission status: Accepted

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

def lcm(a,b):
    return a * b // gcd(a,b)
def ls_lcm(A):
    return reduce(lcm ,A)
def ls_gcd(A):
    return reduce (gcd, A)

def count_two(n): # 2で割れる回数を取得
    cnt = 0
    while(n & 1 == 0):
        cnt += 1
        n = n >> 1
    return cnt

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

if len(set([count_two(a) for a in A])) != 1:
    print (0)
    exit()
A = [a//2 for a in A]
half = ls_lcm(A)
print ((M + half) // (2*half))

Submission status: Accepted

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

def lcm(a,b):
    return a * b // gcd(a,b)
def ls_lcm(A):
    return reduce(lcm ,A)
def ls_gcd(A):
    return reduce (gcd, A)

def check_two(A):
    old = None
    for n in A:
        cnt = 0
        while(n & 1 == 0):
            cnt += 1
            n = n >> 1
        if old is None:
            old = cnt
        else:
            if old!=cnt:
                return False
    return True

N, M = map(int, input().split())
A = list(map(int, input().split()))
if not check_two(A):
    print (0)
    exit()
A = [a//2 for a in A]
half = ls_lcm(A)
print ((M + half) // (2*half))

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] = a[i] //2
def count_2(k):
  c = 0
  while k % 2 == 0:
    k = k // 2
    c+=1
  return c
count = count_2(a[0])
for i in range(n):
  if count != count_2(a[i]):
    print(0)
    exit()
ans = a[0]
for i in range(1, n):
    ans = ans * a[i] // fractions.gcd(ans, a[i])
print((m // ans +1)//2)

Submission status: Accepted

Solution code:
from fractions import gcd

def calc_half(n):
    return n//2

def lcm(L):
    ret=1
    for i in range(len(L)):
        ret=(ret*L[i])//gcd(ret,L[i])
    return ret

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

def g(L):
    l=[]
    for i in L:
        l.append(f(i))
    if len(set(l))==1:
        return False
    else:
        return True

n,m=map(int,input().split())
A=list(map(int,input().split()))
Auniq=list(set(A))
Ahalf=list(map(calc_half,Auniq))
lcm_ori=lcm(Auniq)
lcm_half=lcm(Ahalf)

if m<lcm_half or g(Auniq):
    print("0")
else:
    print(1+(m-lcm_half)//lcm_ori)

Submission status: Accepted

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

from fractions import gcd
from math import ceil

cnt = 1
flg = True
while 1:
    num = 2**cnt
    lis = [1 if x%num==0 else 0 for x in As]
    s = sum(lis)
    if s==N:
        cnt+=1
        continue
    elif s==0:
        break
    else:
        flg = False
        break

if flg:
    lcm = As[0]
    for i in range(1, N):
        a = As[i]
        lcm = a*lcm//gcd(lcm, a)
    
    print(ceil((M//lcm)/2))
else:
    print(0)

Submission status: Accepted

Solution code:
import sys
from fractions import gcd

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


def merge(a, b):
    g = gcd(a, b)
    a //= g
    b //= g
    if a % 2 == 0:
        return 0
    if b % 2 == 0:
        return 0
    n = a * b * g
    if n > 10 ** 9:
        return 0
    return n


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

a = [x >> 1 for x in a]

for i in range(n-1):
    a[i+1] = merge(a[i], a[i+1])

z = a[n-1]

if z == 0:
    print("0")
else:
    ans = (m//z) - (m//(z+z))
    print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
N, M, *A = map(int, read().split())
 
# 「奇数倍」に帰着
A = [x >> 1 for x in A]
 

def merge(a, b):
    g = gcd(a, b)
    a //= g
    b //= g
    if a % 2 == 0:
        return 0
    if b % 2 == 0:
        return 0
    n = a * b * g
    if n > 10 ** 9:
        return 0
    return n


x = reduce(merge, A)

if x == 0:
    answer = 0
else:
    answer = (M//x) - (M//(x+x))
 
print(answer)

Submission status: Accepted

Solution code:
import fractions
n,num=map(int,input().split())
num_set=set(map(lambda x:int(x),input().split()))
two_times_set=set()

for i in num_set:
    for j in range(1,30):
        i//=2
        if i%2!=0:
            two_times_set.add(j)
            break

    if len(two_times_set)!=1:
        print(0)
        break
else:
    num_list=list(num_set)
    lcm=num_list[0]
    for i in range(1,len(num_list)):
        lcm = lcm * num_list[i] // fractions.gcd(lcm, num_list[i])    
    #print((num-lcm//2)//(lcm)+1)

    lcm//=2
    print(int(((num/lcm)+1)/2))

Submission status: Accepted

Solution code:
import fractions
import math
n,num=map(int,input().split())
num_set=set(map(lambda x:int(x),input().split()))
two_times_set=set()

for i in num_set:
    for j in range(1,30):
        i//=2
        if i%2!=0:
            two_times_set.add(j)
            break

    if len(two_times_set)!=1:
        print(0)
        break
else:
    num_list=list(num_set)
    lcm=num_list[0]
    for i in range(1,len(num_list)):
        
        lcm = lcm * num_list[i] // fractions.gcd(lcm, num_list[i])
        
    print((num-lcm//2)//(lcm)+1)

Submission status: Accepted

Solution code:
import unittest
from io import StringIO
import sys
sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():

    n, m = map(int, input().split())
    if n==1:
        a=int(input())
        print(-(-(m//(a//2)) // 2))

    else:
        A = list(map(int, input().split()))
        B = [0]*n
        for i in range(n):
            B[i] = A[i]//2

        for i in range(n):
            cnt = 0
            val = B[i]
            while val % 2 == 0:
                val //= 2
                cnt += 1
            if i == 0:
                temp = cnt
            else:
                if cnt != temp:
                    ok = False
                    break
                if i == n-1:
                    ok = True

        if ok:
            from functools import reduce
            from fractions import gcd

            def lcm(A, B):
                return A * B // gcd(A, B)

            # リストを引数にとる
            l = reduce(lcm, B)
            print(-(-(m//l) // 2))

        else:
            print(0)


resolve()

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):
        """n に含まれる因数 2 の指数"""
        return (n & -n).bit_length()

    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 fractions
N,M = map(int,input().split())
A = list(map(int,input().split()))
t=1
while A:
 b=0
 for i in range(N):
  A[i]=int(A[i]/2)
  if A[i]%2==1:
   b+=1
 if b==N:
  break
 elif 0<b<N:
  t=0
  break
 else:
  t+=1
if t==0:
 print(0)
else:
 ans = A[0]
 for i in range(1, N):
  ans = ans * A[i] // fractions.gcd(ans, A[i])
 ans=min(ans,(M+1))
 c=int(M/(2**(t-1))/ans)
 d=int(M/(2**(t))/ans)
 print(c-d)

Submission status: Accepted

Solution code:
import sys, fractions, functools
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

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

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

def resolve():
    N, M = LI()
    a = LI()

    a_half = [i//2 for i in a]
    a_half_lcm = lcm_list(a_half)
    has_scm = not 0 in [a_half_lcm//i%2 for i in a_half]

    if has_scm:
        print((M-a_half_lcm)//(2*a_half_lcm)+1)
    else:
        print(0)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

import fractions
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0
def mult_crt(b1,m1,b2,m2):
    gcd = xgcd(m1,m2)
    if b1 % gcd[0] != b2 % gcd[0]:
        return False
    else:
        x = b1 + m1*(b2-b1)//gcd[0]*gcd[1]
        m3 = (m1*m2) // fractions.gcd(m1,m2)
        b3 = x % m3
        return b3,m3

N,M = (int(x) for x in input().split())
a = list(map(int, input().split()))
temp = [a[0],a[0]//2]
broke = False
for i in range(1,N):
    bm = mult_crt(temp[1],temp[0],a[i]//2,a[i])
    if bm == False:
        broke = True
        break
    else:
        temp[0] = bm[1]
        temp[1] = bm[0]
if broke:
    print('0')
else:
    dm = divmod(M,temp[0])
    if dm[1] >= temp[1]:
        print(dm[0]+1)
    else:
        print(dm[0])

Submission status: Accepted

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

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

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

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

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

count = f(a[0])

for i in range(n):
    if f(a[i]) != count:
        print(0)
        sys.exit()
    a[i] /= 2**count
m /= 2**count

l = 1
for i in range(n):
    l = lcm(l,a[i])
    if l > m:
        print(0)
        sys.exit()
m /= l

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

Submission status: Accepted

Solution code:
import fractions
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

N,M = (int(x) for x in input().split())
a = list(map(int, input().split()))
temp = [a[0],a[0]//2]
broke = False
for i in range(1,N):
    gcd = xgcd(temp[0],a[i])
    if temp[1] % gcd[0] != (a[i]//2) % gcd[0]:
        broke = True
        break
    else:
        x = temp[1] + temp[0]*((a[i]//2)-temp[1])//gcd[0]*gcd[1]
        temp[0] = (temp[0] * a[i]) // fractions.gcd(temp[0], a[i])
        temp[1] = x % temp[0]
if broke:
    print('0')
else:
    dm = divmod(M,temp[0])
    if dm[1] >= temp[1]:
        print(dm[0]+1)
    else:
        print(dm[0])

Submission status: Accepted

Solution code:
from fractions import gcd  # for python 3.5~, use math.gcd


def main():
    N, M = list(map(int, input().split(' ')))
    half_A = list(map(lambda x: int(x) // 2, input().split(' ')))
    lcm = 1
    for half_a in half_A:
        lcm *= half_a // gcd(lcm, half_a)
        if lcm > M:
            print(0)
            exit(0)
    for half_a in half_A:
        if (lcm // half_a) % 2 == 0:
            print(0)
            exit(0)
    num_multiples = M // lcm
    print((num_multiples + 1) // 2)  # count only cases that ratios are odd numbers.


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

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

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

def lcms(a):
    l = a[0]
    for num in a[1:]:
        l = lcm(l, num)
    return l

n, m = map(int, input().split())
a = list(map(int, input().split()))
# a2 = [num//2 for num in a]
acount = [None]*n # aを2で割れる回数
anum = [None]*n # 割ったあとの残り(=奇数)
for i,num in enumerate(a):
    c = 0
    while num%2==0 and num>1:
        num //=2
        c += 1
    acount[i] = c
    anum[i] = num
if all(item==acount[0] for item in acount):
    l = lcms(anum)
    num0 = l * (pow(2, (acount[0]-1)))
    span = num0*2
    if m<num0:
        print(0)
    else:
        print(int((m-num0)//span + 1))
else:
    print(0)

Submission status: Accepted

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

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

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

N, M = map(int, input().split())
a = list(map(int, input().split()))
b = [ai//2 for ai in a]
cnt = [0]*N

for i in range(N):
    t = b[i]
    
    while t%2==0:
        cnt[i] += 1
        t //= 2
    
if cnt!=[cnt[0]]*N:
    print(0)
    exit()

L = 1

for bi in b:
    L = lcm(L, bi)

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