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 math
import fractions
from functools import reduce
 
n, m = map(int, input().split())
a = list(map(int, input().split()))
a=[t//2 for t in a] # リストの要素を全て2で割る
 
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)
 
def lcm_list(numbers): # 最小公倍数を求める
    return reduce(lcm_base, numbers, 1)
 
def num_dev2(x): # 2で割り切れる回数をカウント
    return format(x, 'b')[::-1].find('1')
 
lcm = lcm_list(a)
q = m // lcm # mは最小公倍数で何回割れるか
 
count = 0
dev2 = num_dev2(a[0])
for i in range(1, n):
    if dev2 != num_dev2(a[i]): # リストの全ての要素の、2で割れる回数は等しいか？
        count += 1
        break
if count != 0:
    print(0)
else:
    print(math.ceil(q/2))

Submission status: Accepted

Solution code:
from fractions import gcd
def lcm(a,b):
    return (a*b)//gcd(a,b)
n,m = map(int,input().split())
a = list(map(int,input().split()))
ans = 1
for i in a:
    ans = lcm(ans,i)
for i in a:
    if (ans//i) % 2 == 0:
        print(0)
        exit()
print(((m//(ans//2))+1)//2)

Submission status: Accepted

Solution code:
def gcd(x, y):
    while y > 0:
        r = x % y
        x = y
        y = r
    return x

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

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

l = 1
for i in range(n):
    a[i] //= 2
    l = lcm(a[i], l)

flg = True
for x in a:
    if (l // x) % 2 == 0:
        flg = False
        break

if flg:
    print(m // l - m // (l * 2))
else:
    print(0)

Submission status: Accepted

Solution code:
from fractions import gcd
# from math import gcd
from functools import reduce
N, M = map(int, input().split())
nums = set([num // 2 for num in list(map(int, input().split()))])
# 1<=X<=Mの範囲で、半公倍数の数を求める。
# 但し、Xは、num*(p+0.5)でなければならない
# Mが10**9なので、全部やるのは無理。
# n.5倍なので、numsのあたいは全て偶数になっている。

# nums一つ一つ、答えになりうるXの配列を作って、重複したものを残せばそれが答えになる。
# Nが10**5なので、どうだろう


def half_multiple(x, y):
    # 最大公約数は無駄なのではぶく
    # x=6,y=10なら=>2が無駄なもの
    return (x * y) // gcd(x, y)


def run():
    half_multiple_num = reduce(half_multiple, nums, 1)

    # print(half_multiple_num)
    for num in nums:
        # n.5倍の値でなければならないので、ここでチェックする
        if (half_multiple_num // num) % 2 == 0:
            print(0)
            return

    ans = M // half_multiple_num
    ans = ans - 1 if ans % 2 == 0 else ans

    print((ans + 1) // 2)


run()

Submission status: Accepted

Solution code:
from fractions import gcd
# from math import gcd
from functools import reduce
N, M = map(int, input().split())
nums = set([num // 2 for num in list(map(int, input().split()))])
# 1<=X<=Mの範囲で、半公倍数の数を求める。
# 但し、Xは、num*(p+0.5)でなければならない
# Mが10**9なので、全部やるのは無理。
# n.5倍なので、numsのあたいは全て偶数になっている。

# nums一つ一つ、答えになりうるXの配列を作って、重複したものを残せばそれが答えになる。
# Nが10**5なので、どうだろう


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


def run():
    half_multiple_num = reduce(half_multiple, nums, 1)

    # print(half_multiple_num)
    for num in nums:
        if (half_multiple_num // num) % 2 == 0:
            print(0)
            return

    pmax = M // half_multiple_num
    pmax = pmax - 1 if pmax % 2 == 0 else pmax

    print((pmax + 1) // 2)


run()

Submission status: Accepted

Solution code:
import functools
import sys

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

# A[0]を素因数分解して2で割り切れる回数を数える
div = 0

a_0 = a[0]
while a_0 % 2 == 0:
    a_0 /= 2
    div += 1

# print("count = " + str(div))#

# Aのすべての整数がA[0]と同じ回数2で割り切れるか調べる
for i in range(1, len(a)):
    div2 = 0
    tmp_a = a[i]
    while tmp_a % 2 == 0:
        tmp_a /= 2
        div2 += 1
    # print("A[" + str(i) + "] count = " + str(div2))#
    if div2 != div:
        print("0")
        sys.exit()


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

    return gcd(y % x, x)


def least_common_multiple(iter):
    '''
    最小公倍数を返す
    '''
    lcm = lambda x, y: x * y // gcd(x, y)
    return functools.reduce(lcm, iter)


lc = least_common_multiple(a)
ans = 0
a = 1

ans = m // lc
if ans == 0:
    print(0)
    sys.exit()
if ans % 2 == 0:
    print(ans // 2)
else:
    print(ans // 2 + 1)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=list(map(int,input().split()))
l=list(set(l))
n=len(l)
ll=[]
for i in l:
    ll.append(int(i/2))

newl=[]
for i in ll:
    j=i
    count=0
    while j%2==0:
        j//=2
        count+=1
    newl.append(count)
import collections
newl=collections.Counter(newl)
if len(newl)!=1:
    print(0)
     
else:
    from fractions import gcd
    num=ll[0]
    flag=True
    for i in ll:
        if num<=m:
            num=int(i*num/gcd(i,num))
        else:
            flag=False
            break
    if flag==False:
        print(0)
    else:
        k=m%(num*2)
        if k>=num:
            print(int(m//(num*2)+1))
        else:
            print(int(m//(num*2)))

Submission status: Accepted

Solution code:
import sys
from fractions import gcd

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


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


def main():
    N, M, *A = map(int, read().split())
    A = list({a // 2 for a in A})

    power = 1
    while all(a % 2 == 0 for a in A):
        A = [a // 2 for a in A]
        power *= 2

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

    l = 1
    for a in A:
        l = lcm(l, a)

    l *= power
    ans = (M + l) // (2 * l)
    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from fractions import gcd

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


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


def main():
    N, M, *A = map(int, read().split())
    A = list({a // 2 for a in A})

    power = 1
    while all(a % 2 == 0 for a in A):
        A = [a // 2 for a in A]
        power *= 2

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

    l = 1
    for a in A:
        l = lcm(l, a)
        if l > M:
            print(0)
            return

    l *= power
    ans = (M + l) // (2 * l)
    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from fractions import gcd

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


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


def main():
    N, M, *A = map(int, read().split())
    A = [a // 2 for a in A]

    power = 1
    while all(a % 2 == 0 for a in A):
        A = [a // 2 for a in A]
        power *= 2

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

    l = 1
    for a in A:
        l = lcm(l, a)
        if l > M:
            print(0)
            return

    l *= power
    ans = (M + l) // (2 * l)
    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

numdic = {}

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

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

lcmnum = lcm_list(alist)

for i in alist:
    if (lcmnum//i)%2==0:
        print(0)
        sys.exit()

pmax = M // lcmnum
pmax = pmax - 1 if pmax % 2 == 0 else pmax

print((pmax+1)//2)

Submission status: Accepted

Solution code:
from fractions import gcd

def lcm(*args):
    ans = 1
    for x in args:
        ans = ans * x // gcd(ans, x)
    return ans

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

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

def solve(a):
    tmp = None
    for ta in a:
        if tmp is None:
            tmp = log(ta)
        else:
            if tmp == log(ta):
                continue
            else:
                print(0)
                return
    l = lcm(*a)
    print(m // (l//2) - m // l)

solve(a)

Submission status: Accepted

Solution code:
def gcd_e(x, y):
  if y == 0:
    return x
  else:
    return gcd_e(y,x%y)      

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

n,m=list(map(int,input().split()))
A=list(map(int,input().split()))
a,b=A[0],0

for i in range(1,n):
  b = A[i]
  a = lcm(a,b)
  
for i in set(A):
  if (a // i) % 2 == 0:
    print('0')
    exit()    
  
if a // 2 > m:
  print('0')
else:
  print((m-a//2)//a+1)

Submission status: Accepted

Solution code:
def gcd_e(x, y):
  if y == 0:
    return x
  else:
    return gcd_e(y,x%y)      

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

n,m=list(map(int,input().split()))
A=list(map(int,input().split()))
a,b=A[0],0

for i in range(1,n):
  b = A[i]
  a = lcm(a,b)
  
for i in range(n):
  if (a // A[i]) % 2 == 0:
    print('0')
    exit()    
  
if a // 2 > m:
  print('0')
else:
  print((m-a//2)//a+1)

Submission status: Accepted

Solution code:
def divider(A,N):
    """
    リストA内の全要素が全て2**nで割れるときTrueを返す
    """
    cnt_list=[]
    same=True
    for n in range(N):        
        tmp=A[n]
        cnt=0
        while tmp%2==0:
            tmp//=2
            cnt+=1
        cnt_list.append(cnt)
        if n>=1 and cnt!=cnt_list[n-1]:
            same=False
            break
    return same       

def cal_minX(A,N,M):
    """
    hit A内の数全てでXが割り切れ、かつ商が奇数だったらTrue
    """
    max_A=max(A)

    if divider(A,N)==False:
        no_ans=True
        minX=0
    else:
        fin=False
        no_ans=False
        i=0
        while fin==False:
            coef=2*i+1
            if max_A*coef>M:
                fin=True
                no_ans=True
            else:
                hit=True
                for n in range(N):
                    if max_A*coef%A[n]==0:
                        if (max_A*coef//A[n])%2==1:
                            pass
                        else:
                            hit=False
                            break
                    else:
                        hit=False
                        break

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

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

Submission status: Accepted

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

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


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


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


def lcm_list(numbers):
    x = 1
    for i in range(n):
        x = lcm_base(x, numbers[i])
        if x > 2*m:
            print(0)
            exit()

    return x


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


two_count = count_two(A[0])
for a in A[1:]:
    if two_count != count_two(a):
        print(0)
        exit()

LCM = lcm_list(A)
# print(LCM)
print((m - LCM//2)//LCM + 1)

Submission status: Accepted

Solution code:
import sys
import fractions
def lcm(a, b):
    return abs(a*b) // fractions.gcd(a, b)
n,m=map(int,input().split())
a=list(map(int,input().split()))
c=2
while a[0]%c==0:
  c=c*2
c=c//2
fail=0
for i in range(n):
  if a[i]%c!=0:
    fail=1
  if a[i]%(2*c)==0:
    fail=1
if fail==1:
  print(0)
  sys.exit()
A=1
for i in range(n):
  A=lcm(A,a[i])
print(2*m//A-2*m//(2*A))

Submission status: Accepted

Solution code:
from functools import reduce

def gcd_base(x, y):
    if x % y:
        return gcd_base(y, x%y)
    return y

def gcd(numbers):
    return reduce(gcd_base, numbers)

def lcm_base(x, y):
    res = (x * y) // gcd_base(x, y)
    return res if res <= 1000000007 else 0

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

n, m = map(int, input().split())
a = [int(i) for i in input().split()]
k = [0] * n
for i in range(n):
    j = a[i]
    while(j%2==0):
        j //= 2
        k[i] += 1
if any([k[i]!=k[i+1] for i in range(n-1)]):
    print(0)
else:
    l = [i//2 for i in a]
    x = lcm(l)
    if x==0:
        print(0)
    else:
        print((m//x+1)//2)

Submission status: Accepted

Solution code:
def prime_factor(n):
    arr = []
    temp = n
    for i in range(2, 3):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

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


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

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

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

n //= 2

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

print(ans)

Submission status: Accepted

Solution code:
from math import ceil
from fractions import gcd

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

# 2で割ったものに置き換え
A = [a // 2 for a in A]


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


# 各要素について、2で割り切れる回数が等しいかチェック
count_div_2 = None
for a in A:
    cnt = 0
    while a % 2 == 0:
        a //= 2
        cnt += 1

    if count_div_2 is None:
        count_div_2 = cnt
    elif cnt != count_div_2:
        print(0)
        exit()

# LCM計算
while len(A) > 1:
    a, b = A.pop(), A.pop()
    my_lcm = lcm(a, b)

    # Mを超えたlcmは意味がない
    if my_lcm > M:
        print(0)
        exit()

    A.append(my_lcm)


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

Submission status: Accepted

Solution code:
from fractions import gcd
import sys
n, m = map(int, input().split())
a = [int(i) for i in input().split()]
b = [i // 2 for i in a]
def div2check(i):
    count = 0
    while i % 2 == 0:
        count += 1
        i //= 2
    return count
c = [div2check(i) for i in b]
if c.count(c[0]) != n:
    print(0)
    sys.exit()

lcm = b[0]
for i in b[1:]:
    lcm = lcm * i // gcd(lcm, i)
print((m // lcm + 1) // 2)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
 
from functools import reduce
# from math import *
from fractions import *
N, M = map(int, readline().split())
A = list(sorted(map(lambda x: int(x) // 2, readline().split())))
min_cm = reduce(lambda a, b: (a * b) // gcd(a, b), A)
 
# print(all(map(lambda x: (min_cm // x) % 2 == 1, A)))
if not all(map(lambda x: (min_cm // x) % 2 == 1, A)):
    print(0)
    exit(0)
if min_cm > M:
    print(0)
    exit(0)
ans = (M // min_cm + 1) // 2
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
 
from functools import reduce
# from math import *
from fractions import *
N, M = map(int, readline().split())
A = list(map(lambda x: int(x) // 2, readline().split()))

def f(n):
    cnt = 0
    while n % 2 == 0:
        n //= 2
        cnt += 1
    return cnt
t = f(A[0])
for i in range(N):
    if f(A[i]) != t:
        print(0)
        exit(0)
    A[i] >>= t
M >>= t
lcm = reduce(lambda a, b: (a * b) // gcd(a, b), A)
if lcm > M:
    print(0)
    exit(0)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def SMI(): return input().split()
def SLI(): return list(input())

def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')

from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate

from fractions import gcd
# from math import gcd
def lcm(x, y):
  return x // gcd(x, y) * y

def solve():
    N, M = MI()
    A = LI()

    A = list(map(lambda x: x // 2, A))

    EX = 0
    b = A[0]
    while b % 2 == 0:
        b //= 2
        EX += 1

    l = 1
    for a in A:
        ex = 0
        while a % 2 == 0:
            a //= 2
            ex += 1
        if ex != EX:
            print(0)
            return
        l = lcm(l, a)

    M //= pow(2, EX)
    # print(l)

    print(ceil((M // l) / 2))


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import fractions
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

#2で何回割れるかを数える関数
def t_per2(k):
    return format(k,'b')[::-1].find('1')

def main():
    n,m = map(int,ipt().split())
    a = [int(i) for i in ipt().split()]
    k2 = t_per2(a[0])
    l = a[0]//2
    for ai in a[1::]:
        if not k2 == t_per2(ai):
            print(0)
            exit()
        l = l*(ai//2)//(fractions.gcd(l,ai//2))
        if l > m:
            print(0)
            exit()
    print((m+l)//(2*l))
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from functools import reduce

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

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

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

A = [count(i) for i in a]

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

aa = [i // 2 for i in a]
LCM = reduce(lcm, aa)

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

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

print((M // A_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()))
last_cnt = 0
v=a[0]
while v%2==0:
  v//=2
  last_cnt+=1
for v in a[1:]:
  cnt = 0
  while v%2 == 0:
    v //=2
    cnt += 1
  if last_cnt != cnt:
    print(0)
    exit()
    
a=[v//2 for v in a]

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

l = lcm_list(a)
if l>m:
  print(0)
  exit()
print(1+(m-l)//(l*2))
#print(lcm_list(a))

Submission status: Accepted

Solution code:
from fractions import gcd
n, m = map(int, input().split())
a = [int(i) // 2 for i in input().split()]
x = 1
for i in range(n):
    x *= a[i] // gcd(x, a[i])
for i in a:
    if x // i % 2 == 0:
        print(0)
        exit()
print((m // x + 1) // 2)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

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

# 4と8の場合
# 2 6 10 14 18...
# 4 12 20 28... これを２で割ると

# 1 3 5 7 9...
# 2 4 10 14... 起点が偶数と奇数なため永遠に一致しない

# 4と12なら
# 2 6 10 14 18...
# 6 18 30 42... これを２で割ると
# 1 3 5 7 9...
# 3 9 15 21...　になり、起点が奇数と奇数になるためどこかで一致する

# Aの各要素がどれも2でn回ちょうど割れる必要がある
def div_2(n):
    cnt = n
    res = 0
    while cnt > 0:
        if cnt % 2 == 0:
            cnt //= 2
            res += 1
        else:
            return res

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

judge = [div_2(i) for i in A]

if min(judge) != max(judge):
    print(0)
    exit()
L = 1
for i in range(N):
    L = lcm(L, A[i])

# Ai * 0.5, Ai * 1, Ai * 1.5...の個数 - Ai * 1, Ai * 2...の個数
print(M // L - M // (2 * L))

Submission status: Accepted

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

    return gcd(y % x, x)


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


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

aa = [e // 2 for e in a]

for i, e in enumerate(aa):
    if i == 0:
        base = 0
        while e % 2 == 0:
            e //= 2
            base += 1

    else:
        cnt = 0
        while e % 2 == 0:
            e //= 2
            cnt += 1

        if cnt != base:
            print(0)
            exit()

c = 1
for e in aa:
    c = lcm(c, e)
    if c > m:
        print(0)
        exit()

ans = (m - c) // (2 * c) + 1
print(ans)

Submission status: Accepted

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

    return gcd(y % x, x)


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


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

aa = [e // 2 for e in a]

for i, e in enumerate(aa):
    if i == 0:
        base = 0
        while e % 2 == 0:
            e //= 2
            base += 1

    else:
        cnt = 0
        while e % 2 == 0:
            e //= 2
            cnt += 1

        if cnt != base:
            print(0)
            exit()

c = 1
for e in aa:
    c = lcm(c, e)


ans = (m - c) // (2 * c) + 1
print(ans)

Submission status: Accepted

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


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


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


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

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

Submission status: Accepted

Solution code:
def gcd(x, y):
    if x == 0: return y
    return gcd(y%x, x)
lcm = lambda x, y: x*y//gcd(x, y)

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

cm = arr[0]
for e in arr[1:]:
    cm = lcm(cm, e)

if any([cm//e % 2 == 0 for e in arr]):
    print(0)
    exit()
print((m//cm+1)//2)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def SI(): return input().split()

def printlist(lst, k='\n'): print(k.join(list(map(str, lst))))
INF = float('inf')

from math import ceil, floor, log2
from collections import deque
from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product
from heapq import heapify, heappop, heappush

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

def solve():
    n, m = MI()
    A = LI()

    # aを2で割る
    for i in range(n):
        a = A[i]
        A[i] = a // 2

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

    div2 = f(A[0])
    for i, a in enumerate(A):
        if div2 != f(a):
            print(0)
            return
        A[i] = a >> div2

    m = m >> div2
    # print(A, m)

    l = 1
    for a in A:
        l = lcm(l, a)

    # print(l)

    # l * odd <= m を数える
    ans = m // l - m // (2 * l)
    print(ans)




if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
def gcd(a, b):
    while b: a, b = b, a % b
    return abs(a)

def solve(N: int, M: int, a: "List[int]"):
    a = [t//2 for t in list(set(a))]

    g = a[0]
    for t in a:
        g = gcd(g, t)

    ag = [t//g for t in a] 

    mu = 1
    for t in ag:
        if t%2==1:
            mu*= t//gcd(t,mu)
        else:
            print(0)
            return
    # print(g)
    # print(mu)
    print((M//(mu*g)+1)//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 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 = [a[i]//2 for i in range(n)]
l = 1
b = -1
for x in a:
    if l % x != 0:
        l = l * x // gcd(l,x)
    c = 0
    while x % 2 == 0:
        x = x // 2
        c += 1
    if b != -1 and b != c:
        print(0)
        exit()
    elif b == -1:
        b = c
        
ans = m // l
ans = (ans + 1) // 2
print(ans)
#print(l)

Submission status: Accepted

Solution code:
import sys

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

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

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

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

for i in range(N):
    A[i] //= 2
    
t = f(A[0])
A[0] >> t
M >> t

for i in range(1, N):
    if f(A[i]) != t:
        print(0)
        sys.exit()
        
    A[i] >> t
    
l = 1
for a in A:
    l = lcm(l, a)
    
if l > M: 
    print(0)
    sys.exit()
    
M /= l

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

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_list(numbers):
    return reduce(lcm_base, numbers, 1)
  

N, M = map(int, input().split())
A = list(map(int, input().split()))
for i in range(N):
  A[i] = A[i] // 2
  
p = 0
de_2 = 0
x = A[0]
while (p == 0):
  if x % 2 == 0:
    x = x // 2
    de_2 += 1
  else:
    p = 1
    
de = 2 ** de_2
for i in range(1, N):
  if A[i] % de == 0:
    if A[i] % (de * 2) != 0:
      continue
    else:
      print("0")
      quit()
  else:
    print("0")
    quit()
  
lcm = lcm_list(A)
p = M // lcm
if p % 2 == 0:
  ans = p // 2
else:
  ans = (p + 1) // 2
  
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from queue import deque
readline = sys.stdin.buffer.readline
#sys.setrecursionlimit(10**8)

from fractions import gcd


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    n, m = geta(int)
    a = tuple(geta(int))

    g = a[0] // 2

    def fn(i):
        ret = 0
        while i & 1 == 0:
            ret += 1
            i = i >> 1
        return ret

    t = fn(g)

    for ai in a[1:]:
        ai2 = ai // 2

        if t != fn(ai2):
            print(0)
            exit()

        g = (g * ai2) // gcd(g, ai2)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

temp = S[0]
cnt = 0
while temp%2 == 0:
    temp //= 2
    cnt += 1
temp = S[0]
for i in range(1, N):
    temp = temp*S[i]//gcd(temp, S[i])
    if S[i]%(2**cnt) == 1 or (S[i]//(2**cnt))%2 == 0:
        print(0)
        break
else:      
    if temp//2 > M:
        print(0)
    else:
        print((M-temp//2)//temp+1)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce
def l(a,b):return a*b//gcd(a,b)
def L(N):return reduce(l,N)
n,m=map(int,input().split())
A=list(map(lambda x:int(x)//2,input().split()))
a=A[0]
c=0
while(a%2==0):
  a//=2
  c+=1
if any([(a%(2**c)==0 and a//(2**c))%2==0 for a in A]):
  print(0)
  exit()
a=L(A)
print((m+a)//(2*a))