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:
from fractions import gcd
from math import ceil
def f(x):
  cnt=0
  while x%2==0:
    x//=2
    cnt+=1
  return cnt
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=[a[i]//2 for i in range(n)]
g=b[0]
for i in range(1,n):
  g=g*b[i]//gcd(g,b[i])
t=f(a[0])
for i in range(n):
  if t!=f(a[i]):
    print(0)
    exit()
else:
  print(int((m/g+1)//2))

Submission status: Accepted

Solution code:
#abc150d
def gcd(a,b):
 while b:
  a,b=b,a%b
 return a
def lcm(a,b):
 return a/gcd(a,b)*b
import sys
n,m=map(int,raw_input().split())
a=map(int,raw_input().split())
LCM=1
for i in range(n):
 LCM=lcm(LCM,a[i])
for i in range(n):
 if LCM/a[i]%2==0:
  print 0
  sys.exit()
res=(m/(LCM/2)+1)/2
print res

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
A = list(map(int,input().split()))
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)
cur = 0
if n != 1:
    t = A[0]
    while t%2 == 0:
        cur += 1
        t = t//2
        flag = True
    for i in range(1,n):
        temp = 0
        s = A[i]
        while s%2 == 0:
            temp += 1
            s = s//2
        if temp != cur:
            flag = False
            break
    if flag:
        g = A[0]*A[1]//(4*gcd(A[0]//2, A[1]//2))
        for i in range(2, n):
            u = g
            v = A[i]//2
            p = u*v//gcd(u,v)
            g = p
        if g <= m:
            print(int((m/g-1)/2)+1)
        else:
            print(0)
    else:
        print(0)
else:
    if A[0] <= 2*m:
        print(int(((2*m/A[0])-1)/2)+1)
    else:
        print(0)

Submission status: Accepted

Solution code:
import fractions
def LCM(X,Y):
  return X*(Y//fractions.gcd(X,Y))
N,M=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]

def Oddcheck(lst):
  for num in lst:
    if num%2==0:
      return False
      break
  else:
    return True
def Evencheck(lst):
  for num in lst:
    if num%2==1:
      return False
      break
  else:
    return True

c=1
while Oddcheck(ls)==False:
  if Evencheck(ls)==True:
    c*=2
    for i in range(N):
      ls[i]//=2
  else:
    print(0)
    break
else:
  g=1
  for num in ls:
    g=LCM(g,num)
  g*=c//2
  print((M+g)//(2*g))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def gcd(a,b):
        if a == 0:
            return b
        return gcd(b%a,a)
    n,m = LI()
    a = LI()
    k = [i&-i for i in a]
    if len(set(k)) > 1 or all([i == 1 for i in k]):
        print(0)
        return
    a = [i>>1 for i in a]
    l = a[0]
    for i in a[1:]:
        g = gcd(l,i)
        l *= i//g
    print(m//l-m//(2*l))
    return

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

Submission status: Accepted

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

a = [1]*n
#print(a)
a = [int(s) for s in input().split()]

a_half = [s//2 for s in a]
#print(a)

def check(x):
    while (all(c%2 == 0 for c in x)):
        x = [s//2 for s in x]
        if any(c%2 == 1 for c in x) and any(c%2 == 0 for c in x):
            return 0
        
    
    return 1

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


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

if(check(a)== 1):
    x = a_half[0]
    for i in range(1,n):
        y = a_half[i]
        x = lcm(x,y)
    if(x > m):
        print(0)
    else:
        res = int((m//x+1)//2)
        print(res)
else:
    print(0)

Submission status: Accepted

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


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


def judge(A):
    B = [0] * len(A)
    for i, a in enumerate(A):
        b = 0
        while a % 2 == 0:
            b += 1
            a //= 2
        B[i] = b
    if len(set(B)) == 1:
        return True
    else:
        return False


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

if judge(A):
    for a in A[1:]:
        m = lcm(m, a)

    M //= m
    ans = (M + 1) // 2
else:
    ans = 0
print(ans)

Submission status: Accepted

Solution code:
#150_D
from fractions import gcd
from functools import reduce
def lcm(x, y):
    return x * y // gcd(x, y)
n, m = map(int, input().split())
a = list(map(int, input().split()))
flg = True
cnt0 = 0
while a[0] % 2 == 0:
    a[0] //= 2
    cnt0 += 1

for i in range(1, n):
    cnti = 0
    while a[i] % 2 == 0:
        a[i] //= 2
        cnti += 1
    
    if cnti != cnt0:
        flg = False
        break
        
lcm_a = reduce(lcm, a) * (2 ** (cnt0 - 1))
x = m // lcm_a
print(-(-x // 2) if flg else 0)

Submission status: Accepted

Solution code:
import fractions
from functools import reduce

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

div_num = [0 for _ in range(n)]
same = True
for i in range(n):
    tmp = a[i]
    while tmp%2 == 0:
        tmp //= 2
        div_num[i] += 1
if len(set(div_num)) != 1:
    same = False

if same:
    lcm = reduce(lambda x, y: (x*y)//fractions.gcd(x, y), a)
    print(int((m/lcm + 1)//2))
else:
    print(0)

Submission status: Accepted

Solution code:

from functools import lru_cache
import math


@lru_cache(maxsize=None)
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_all(lst):
    curr = 1
    for l in lst:
        curr = lcm(curr, l)
    return curr


def divide_count(x):
    ans = 0
    while True:
        q, r = divmod(x, 2)
        if r == 0:
            ans += 1
            x = q
        else:
            break
    return ans



def submit():
    n, m = map(int, input().split())
    alist = list(map(int, input().split()))

    a_divide_count = [divide_count(a) for a in alist]
    for a in a_divide_count[1:]:
        if a != a_divide_count[0]:
            print(0)
            return

    l = lcm_all(alist)
    x = l // 2
    if x > m:
        print(0)
    else:
        print(math.ceil(m // x / 2))


if __name__ == "__main__":
    submit()

Submission status: Accepted

Solution code:
#=============================================================================
#ABC150 D
#=============================================================================
import fractions
from functools import reduce

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

lcm = 1
for A in a:
    A//=2
    lcm *=A//fractions.gcd(lcm, A)
    if lcm>M:
        print(0)
        exit()
for A in a:
    if lcm/A==int(lcm/A):
        print(0)
        exit()

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

Submission status: Accepted

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

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

ans = -1
b = [0] * n
for i in range(n):
    if a[i] % 2 != 0:
        ans = 0
        break

    else:
        b[i] = a[i] // 2


    if i == 0:
        num = format(a[i], 'b')[::-1].find('1')

    else:
        if format(a[i], 'b')[::-1].find('1') != num:
            ans = 0
            break
        else:
            num = format(a[i], 'b')[::-1].find('1')


if ans != 0:
    g = b[0]
    for i in range(1,n):

        g = (g*b[i]) // gcd(b[i],g)

    if g > m: ans = 0
    else:
        ans = (1 + (m-g)//(2*g))

print(ans)

Submission status: Accepted

Solution code:
import sys
import fractions

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

a_max = max(a)

smallest_X = 0

lcm_N = a[0]

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


for X in range(int(a_max * 0.5), min(lcm_N + 1, M + 1), a_max):
    flag = True
    for j in range(N):
        if (X - a[j] * 0.5) % a[j] != 0:
            flag = False
            break
    if flag:
        smallest_X = X
        break

if smallest_X == 0:
    print(0)
    
else:
    print(int((M - smallest_X) / lcm_N) + 1)

Submission status: Accepted

Solution code:
def count_power_of_2(x):
    cnt = 0
    while x % 2 == 0:
        x //= 2
        cnt += 1
    return cnt


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


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


def main():
    N, M = map(int, input().split())
    a = map(int, input().split())
    *a, = map(lambda x: x >> 1, a)

    power = count_power_of_2(a[0])

    if any(count_power_of_2(x) != power for x in a):
        print(0)
        return

    common = 1 << power

    base = common
    for x in a:
        x //= common
        base = lcm(base, x)

    ret = (M // base) - (M // (base * 2))
    print(ret)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
import sys

def gcd(p, q):
    if p < q:
        p, q = q, p
    while q > 0:
        p, q = q, p%q
    return p

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

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

b = a//2
while True:
    p = b%2
    if all(p):
        break
    elif any(p):
        print(0)
        sys.exit()
    else:
        b //= 2
        continue

a //= 2
k = a[0]
for i in range(1, n):
    k = k*a[i]//gcd(k, a[i])
print(1+(m-k)//(2*k) if m >= k else 0)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math
import copy
#GCD（最大公約数）
def gcd(x, y):
    if x < y:
        x, y = y, x
    while y > 0:
        x, y = y, x % y
    return x

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


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

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

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

ans = math.ceil((2 * m // l) / 2) 
print(ans)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7


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

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

n, m = MAP()
a = LIST()
a0 = a[0]
aa = 0
while a0 % 2 == 0:
    a0 //= 2
    aa += 1
for i in range(1, n):
    ai = a[i]
    for _ in range(aa):
        if ai % 2 == 1:
            print(0)
            exit()
        ai //= 2
    if ai % 2 == 0:
        print(0)
        exit()

l = 1
for i in range(n):
    l = lcm(l, a[i])
ans = 2 * m // l
ans = ans // 2 + ans % 2
print(ans)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7


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

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

n, m = MAP()
a = LIST()
a0 = a[0]
aa = 0
while a0 % 2 == 0:
    a0 //= 2
    aa += 1
for i in range(1, n):
    ai = a[i]
    for _ in range(aa):
        if ai % 2 == 1:
            print(0)
            exit()
        ai //= 2
    if ai % 2 == 0:
        print(0)
        exit()

b = [i // 2 for i in a]
l = 1
for i in range(n):
    l = lcm(l, b[i])
ans = m // l
ans = (ans + 1) // 2
print(ans)

Submission status: Accepted

Solution code:
'''
https://atcoder.jp/contests/abc150/tasks/abc150_d
'''
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

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

    if len(a) == 1:
        if m >= a[0]//2:
            print((m-a[0]//2) // a[0] + 1)
        else:
            print(0)
        exit()

    def gcd(a, b):
        if b == 0:
            return a
        else:
            return gcd(b, a % b)
    
    def gcd_group(arr):
        g = gcd(arr[0], arr[1])
        for i in range(2, len(arr)):
            g = gcd(g, arr[i])
        return g
    
    def lcm(a, b):
        g = gcd(a, b)
        return (a*b)//g
    
    def lcm_group(arr):
        l = lcm(arr[0], arr[1])
        for i in range(2, len(arr)):
            l = lcm(l, arr[i])
        return l
    g = gcd_group(a)
    for i in a:
        if (i//g)%2 == 0:
            print(0)
            exit()
    lcm = lcm_group(a)
    semi_lcm = lcm // 2
    if m >= semi_lcm:
        print((m-semi_lcm)//lcm + 1)
    else:
        print(0)


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()))
 
if len(set([i&-i for i in a])) != 1:
  print(0)
else:
  x = 1
  for i in range(N):
    x = x*(a[i]//2//gcd(x,a[i]//2))
 
  print(M//x-M//(2*x))

Submission status: Accepted

Solution code:
import sys
import math
import fractions

N, M = map(int, input().split())
a = list(map(lambda x: int(x) >> 1, input().split()))
set(a)

fdigit = 0
while True:
	c = 1 << fdigit
	if a[0] & c != 0:
		break
	fdigit += 1

alcm = 1
for i in range(N):
	digit = 0
	while True:
		c = 1 << digit
		if a[i] & c != 0:
			break
		digit += 1
	if digit != fdigit:
		print(0)
		sys.exit(0)

	alcm = (alcm * a[i]) // fractions.gcd(alcm, a[i])

print(math.ceil((M // alcm) / 2))

Submission status: Accepted

Solution code:
import sys,queue,math,copy
from fractions import gcd
input = sys.stdin.readline
LI = lambda : [int(x) for x in input().split()]
LI_2 = lambda : [int(x) / 2 for x in input().split()]

N,M = LI()
A = LI_2()

lcm = 1
for a in A:
    c = gcd(lcm,a)
    if (lcm//c) % 2 == 0:
        print (0)
        exit (0)
    lcm *= (a//c)

print (math.ceil((M//lcm) / 2))

Submission status: Accepted

Solution code:
from fractions import gcd

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

if len(set([i&-i for i in a])) != 1:
  print(0)
else:
  x = a[0]//2
  for i in range(1, len(a)):
      x = x*(a[i]//2//gcd(x,a[i]//2))

  print(M//x-M//(2*x))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import fractions

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

have2=[0]*len(A)

for index,item in enumerate(A):
    while item%2==0:
        item/=2
        have2[index]+=1

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

f=0
f2=1
for item in A:
    f=fractions.gcd(f2,item)
    f2=f2*item//f
if M>=f2//2:
    M-=f2//2
    print(max(M//f2+1,0))
else:
    print(0)

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,m = mi() 
alis = li()
for i in range(n):
    alis[i] //= 2

ima = alis[0] & -alis[0]
alis[0] //= ima
for i in range(1,n):
    tmp = alis[i] & -alis[i]
    if ima != tmp:
        print(0)
        exit()
    else:
        alis[i] //=ima

tmp = ima
#a>b
def gcd(a,b):
    if a < b:
        a,b = b,a
    while b!=0:
        a,b=b,a%b
    return a
#a>b
def lcm(a,b):
    return a*b // gcd(a,b)
ima = 1
for i in range(n):
    ima = lcm(alis[i],ima)
    if ima*tmp > m:
        print(0)
        exit()
ans = 0

tmm = m//(ima*tmp)
if tmm % 2 ==0:
    print(tmm//2)
else:
    print(tmm//2 +1)

Submission status: Accepted

Solution code:
from functools import reduce

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x%y)
    
def lcm_base(x, y):
    return x*y//gcd(x, y)

def lcm_list(list):
    return reduce(lcm_base, list)

N, M = map(int, input().split())
a = list(map(int, input().split()))
b = [x//2 for x in a]
T = lcm_list(b)
for n in b:
    if T//n%2 == 0:
        print (0)
        break
else:
    print ((M//T+1)//2)

Submission status: Accepted

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

from functools import reduce
import fractions
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)
def lcm(numbers):
    return reduce(lcm_base, numbers, 1)

def get2(num):
    cnt=0
    while num %2==0:
        cnt+=1
        num//=2
    return cnt

div2=get2(a[0])
for i in range(len(a)):
    if div2 != get2(a[i]):
        print(0)
        exit()

num = lcm(a)
thr = m - num//2

if thr < 0:
    print(0)
else:
    print(thr//num + 1)

Submission status: Accepted

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()

n,m=map(int,input().split())
A=[int(i)//2 for i in input().split()]
ct=0
s=A[0]
while s:
  if s%2==0:
    s//=2
    ct+=1
  else:
    s=0
chk=True
for i in range(1,n):
  cur=0
  a=A[i]
  while a:
    if a%2==0:
      a//=2
      cur+=1
    else:
      a=0
  if cur!=ct:
    chk=False
    break


def gcd(a,b):
  while b:
    a,b=b,a%b
  return a
if not chk:
  print(0)
else:
  lcm=A[0]
  for i in range(1,n):
    lcm*=A[i]//gcd(lcm,A[i])
  print((m//lcm+1)//2)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce
import sys
sys.setrecursionlimit(10 ** 7)

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

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

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


if __name__ == '__main__':
    n, m = list(map(int, input().split(" ")))
    a = list(map(int, input().split(" ")))
    a = list(set(a))

    # for j in a:
    #     if j % 2 != 0:
    #         print("0")

    # a = [i/2 for i in a]
    l = lcm_list(a)

    # if l == 0:
    #     print(0)
    #     exit()

    if (2 * m) < l:
        print("0")
        exit()

    i = l / 2

    for j in a:
        if i // (j // 2) % 2 == 0:
            print(0)
            exit()

    # if m < i:
    #     print("0")
    else:
        # print("1")
        print(int(((m - i) // l) + 1))
        # print(int((m // i + 1) // 2))

Submission status: Accepted

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

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
A = LIST()

# semi_A = []
tmp = A[0] // 2
# for a in A:
#     semi_A.append(a // 2)


for i in range(1, N):
    # tmp = (A[i] // 2)
    # a[0]とa[1]で2で割り切れる数が異なればダメ

    if abs(A[0] // 2 - A[i] // 2) % gcd(A[0], A[i]) != 0:
        print(0)
        exit()
    tmp = (A[i] // 2 * tmp) // gcd(A[i] // 2, tmp)
# print(tmp)
ans = 0
print((M-tmp) // (2 * tmp)+1)
# while tmp * moto <= M:
#     ans += 1
#     moto += 2
# print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return map(int,input().split())
def LI(): return list(map(int,input().split()))

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

    b = [0]*N

    for i in range(N):
        aa = a[i]
        cnt = 0
        while aa%2==0:
            aa //= 2
            cnt +=1
        b[i] = cnt
    
    if b.count(b[0]) != N:
        print(0)
        return
    
    # 2で割れる回数が同じ
    import fractions
    from functools import reduce
    def lcm(x, y):
        return (x * y) // fractions.gcd(x, y)
    def lcm_list(numbers):
        return reduce(lcm, numbers)

    LCM = lcm_list([aa//2 for aa in a])
    c = M//LCM
    if c&1:
        c += 1
    
    print(c//2)
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import fractions
from functools import reduce


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


def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)  # 数列に対しての最小公倍数


n, m = map(int, input().split())
a = list(map(int, input().split()))
b = [x // 2 for x in a]
c = 0
while a[0] % (2 ** (c + 1)) == 0:
    c += 1

for x in a:
    if x % (2 ** c) != 0 or x % (2 ** (c + 1)) == 0:
        print(0)
        exit()

lc = lcm(*b)

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

Submission status: Accepted

Solution code:
def deg(n):
    cnt = 0
    while n%2==0:
        cnt += 1
        n = n//2
    return cnt
def gcm(a,b):
    while b>0:
        a,b = b,a%b
    return a
def lcm(a,b):
    c = gcm(a,b)
    return (a//c)*b
N,M = map(int,input().split())
A = list(map(int,input().split()))
n = deg(A[0])
flg = 0
for i in range(1,N):
    if deg(A[i])==n:continue
    else:
        flg = 1
        break
if flg==1:
    print(0)
else:
    B = [A[i]//2**n for i in range(N)]
    b = B[0]
    for i in range(1,N):
        b = lcm(b,B[i])
    m = 2**(n-1)*b
    print((M+m)//(2*m))

Submission status: Accepted

Solution code:
import sys
import numpy as np
import math
N, M = map(int, input().split())

A = np.array(list(map(int, input().split())), np.int64)

cnt = 0
while True:
	num_E = np.count_nonzero(A % 2 == 0) 
	if 0 < num_E < N:
		print(0)
		sys.exit()
	elif num_E == 0:
		cnt -= 1
		break
	else:
		cnt += 1
		A //= 2

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

	return gcd(b, a%b)
lcm = A[0]
for i in range(1,N):
	tmp_gcd = gcd(lcm, A[i])
	lcm *= A[i]//tmp_gcd
	if lcm > M:
		print(0)
		sys.exit()
M = math.floor(M/(2**cnt))

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

Submission status: Accepted

Solution code:
import functools

N,M = map(int,input().split())
a = list(map(int,input().split()))
b = [0]*N

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

def multiple(a, b):
    return a*b // euclid(a, b)

def lcm(nums):
        return functools.reduce(multiple, nums)

def count_two(n):
    c = 0
    while n%2 ==0:
        c += 1
        n //= 2
    return c

l = [0]*N
for i in range(N):
    l[i] = count_two(a[i])

if len(set(l)) != 1:
    print(0)
else:
    p_2 = l[0] #2で何回割れるか
    for i in range(N):
        b[i] = a[i] // (2**p_2)
    
    X = lcm(b)*(2**(p_2-1))
    nax = M // X

    print((nax+1)//2)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce


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

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

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

def func(x):
    return x // 2

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

def main():
    N, M = map(int, input().split())
    A = list(map(func, map(int, input().split())))

    l = lcm_list(A)
    cnt = cont(A[0])
    for i in range(1, N):
        if cnt != cont(A[i]):
            print(0)
            exit()

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



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs,math
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

import fractions
from functools import reduce
def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
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 nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

N,M = m()

a = l()

ap = [0 for i in range(N)]
for i in range(N):
    co = 0
    while a[i] % 2 == 0:
        a[i] //= 2
        co += 1
    ap[i] = co

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

po = lcm_list(a) * int(math.pow(2,ap[0]-1))

p = -(-(M // po) // 2)

print(p)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def gcd(a, b):
    if a < b:
        d, (p, q) = gcd(b, a)
        return d, (q, p)
    if b == 0:
        return a, (1, 0)
    d, (q, p) = gcd(b, a % b)
    q -= a // b * p
    return d, (p, q)


def ch(x, y):
    a1, m1 = x
    a2, m2 = y
    d, (p, q) = gcd(m1, m2)
    if (a2 - a1) % d != 0:
        return (0, -1)

    m = m1 * m2 // d
    r = (a1 + m1 * (a2 - a1) // d * p) % m
    return (r, m)


def main():
    N, M = read_values()
    A = read_list()
    p = (0, 1)
    for a in A:
        p = ch((a // 2, a), p)
        if p[1] == -1:
            print(0)
            return
    print((M - p[0]) // p[1] + 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    N,M = map(int,input().split())
    A = list(map(int,input().split()))
    
    count = 0
    a = A[0]
    while a%2 == 0:
      a //= 2
      count += 1
      
    for num in A:
      c = 0
      while num%2 == 0:
        num //= 2
        c += 1
      if c != count:
        print(0)
        exit()
    
    def lcm(a):
        x = a[0]
        for i in range(1,N):
            x = (x*a[i]) // gcd(x,a[i])
        return x
    
    x = lcm(A)
    print(M//(x//2)-M//x)
        
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from fractions import gcd
n, m = [int(i) for i in input().split()]
a = [int(i)//2 for i in input().split()]


def two(x):
    i = 0
    while x % 2 == 0:
        i += 1
        x //= 2
    return i


if two(min(a, key=two)) != two(max(a, key=two)):
    print(0)
else:
    lcm = 1
    for i in a:
        lcm = i * lcm // gcd(i, lcm)
        if lcm > m:
            print(0)
            break
    else:
        print((m+lcm)//(2*lcm))

Submission status: Accepted

Solution code:
from fractions import gcd

N, M = map(int, input().split())
a = list(map(int, input().split()))
b = [0] * N
for i in range(N):
	tmp = a[i]
	while tmp & 1 == 0:
		tmp = tmp>>1
		b[i] += 1

same = True
ct = b[0]
for i in range(1, N):
	if b[i] != ct:
		same = False
if not same:
	print(0)
else:
	plcm = 1
	for i in range(N):
		if plcm > M:
			plcm = M+1
		else:
			a[i] //= 2
			plcm = plcm * (a[i] // gcd(plcm, a[i]))
	if plcm > M:
		print(0)
	else:
		ansd = M // plcm
		ans = (ansd + 1)//2
		print(ans)

Submission status: Accepted

Solution code:
import fractions

N,M = map(int, input().split())
l_a = list(map(int, input().split()))
l_num = []
lcm = 1

flg = True
for a in l_a:
  a //= 2
  if not a in l_num:
    l_num.append(a)
  lcm = lcm * a // fractions.gcd(lcm, a)
  if lcm > M:
    flg = False
    break
if flg:
  for num in l_num:
    if lcm > num and lcm // num % 2 == 0:
      flg = False
if flg:
  print((M // lcm + 1) //2)
else:
  print(0)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
#最小公倍数(least common multiple)
import fractions
from functools import reduce
def lcm_base(x, y):
    return ((x * y) // fractions.gcd(x, y))

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
def solve():
    n,m = list(map(int,input().split()))

    a = list(map(int,input().split()))
    a = list(set(list(map(lambda x:x//2,a))))
    div_cnt = 0
    a0 = a[0]
    while a0%2==0:
        div_cnt+=1
        a0//=2
    two_pow_divcnt = 2**div_cnt
    for i in a:
        if i%two_pow_divcnt!=0 or i%(two_pow_divcnt*2)==0:
            return 0
    base = lcm(*a)
    if base > m:
        return 0
    else:
        return (m+base)//(base*2)

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