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
from sys import stdin
input = stdin.readline


def prime_fatorization(n):
  # O(sqrt(n))
  from collections import defaultdict
  # a = []
  a = defaultdict(int)
  while not(n % 2):
    # a.append(2)
    a[2] += 1
    n //= 2
  f = 3
  while f * f <= n:
    if not(n % f):
      # a.append(f)
      a[f] += 1
      n //= f
    else:
      f += 2
  if n != 1:
    # a.append(n)
    a[n] += 1
  return a


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

  pre = A[0]

  for i in range(1, N):
    if pre % 2 != A[i] % 2:
      print(0)
      return

  if not A[0] % 2:
    fac2 = prime_fatorization(A[0])[2]
    for i in range(1, N):
      if not A[i]//(2**fac2) % 2:
        print(0)
        return

  lcm = A[0]
  for i in range(1, N):
    lcm = lcm * A[i] // math.gcd(lcm, A[i])
  print((M // lcm + 1) // 2)


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

Submission status: Accepted

Solution code:

import math
from sys import stdin
input = stdin.readline


def prime_fatorization(n):
  # O(sqrt(n))
  from collections import defaultdict
  # a = []
  a = defaultdict(int)
  while not(n % 2):
    # a.append(2)
    a[2] += 1
    n //= 2
  f = 3
  while f * f <= n:
    if not(n % f):
      # a.append(f)
      a[f] += 1
      n //= f
    else:
      f += 2
  if n != 1:
    # a.append(n)
    a[n] += 1
  return a


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

  # print(A)
  pre = A[0]
#   bool_ini = A[0] % 2
#   bool_end = -1

  for i in range(1, N):
    if pre % 2 != A[i] % 2:
      print(0)
      return
#  for i in range(1, N):
#    if A[i] % 2 == 0 and A[i] != pre:
#      print(0)
#      return
#    else:
#      bool_end = A[i] % 2
#
#    pre = A[i]
#
#  if bool_ini != bool_end:
#    print(0)
#    return

  if not A[0] % 2:
    fac2 = prime_fatorization(A[0])[2]
    for i in range(1, N):
      if not A[i]//(2**fac2) % 2:
        print(0)
        return

  lcm = A[0]
  for i in range(1, N):
    lcm = lcm * A[i] // math.gcd(lcm, A[i])
  print((M // lcm + 1) // 2)
  return


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

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import sys

sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools

import queue
from collections import deque

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

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

def count2(a):
    count = 0
    while 1:
        if a % 2 == 0:
            count += 1
            a //= 2
        else:
            break
    return count

def main():
    num, m = map(int, input().split())
    data = list(map(int, input().split()))

    min_koubaisuu = data[0]

    for i in range(1, num):
        min_koubaisuu = lcm(min_koubaisuu, data[i])

    baisuu = min_koubaisuu // 2

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

    count2_num = count2(data[0])
    for i in range(1, num):
        if count2_num != count2(data[i]):
            print(0)
            sys.exit()

    print(ans)




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions import gcd

def lcm_base(x, y):
    return (x * y) // gcd(x, y)
def lcm(numbers):
    x = numbers[0]
    for y in numbers:
        x = lcm_base(x, y)
    return x

N, M = map(int, input().split())
aaa = list(map(int, input().split()))
a = aaa[0]
cnt = 0
while a % 2 == 0:
    cnt += 1
    a //= 2
for a in aaa:
    if a % 2 ** cnt != 0 or a % 2 ** (cnt + 1) == 0:
        print(0)
        exit()        
bbb = [a // 2 for a in aaa]
lc = lcm(bbb)
q, r = divmod(M // lc , 2)
print(q + r)

Submission status: Accepted

Solution code:
import copy
# from math import gcd


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

def lcm(a, b):
    return (a // gcd(a, b)) * b
def main():
    n, m = map(int, input().split())
    A = set([int(x) for x in input().split()])
    a_lcm = 1
    for a in A:
        a_lcm = lcm(a_lcm, a)
        # mがlcmの半分よりも小さかったら0
        if (a_lcm / 2) > m:
            print(0)
            exit()
    for a in A:
        if (a_lcm / 2) % a == 0:
            print(0)
            exit()
    # # あとは定数倍の数調べて終わり
    ans = int((m - (a_lcm / 2)) // a_lcm) + 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import gcd
def lcm(a,b):
    return a//gcd(a,b)*b
def lcm(ab):
    l=len(ab)
    ret=ab[0]
    for i in range(1,l):
        ret=ret//gcd(ab[i],ret)*ab[i]
    return ret
def count2(a):
    ret=0
    while a%2==0:
        a//=2
        ret+=1
    return 2**ret
n,m=map(int,input().split())
A=list(map(int,input().split()))
#これはいらないです
if any(i%2 for i in A):
    exit(print(0))
A=[i//2 for i in A]
#全体の最小公倍数
p=lcm(A)
c=count2(p)
#2で割り切れる回数が同じでないものがある場合
if any(i%c for i in A):
    exit(print(0))
x=m//p
#print(p//c)
print(-(-x//2))

Submission status: Accepted

Solution code:
from math import gcd
def lcm(a,b):
    return a//gcd(a,b)*b
def lcm(ab):
    l=len(ab)
    ret=ab[0]
    for i in range(1,l):
        ret=ret//gcd(ab[i],ret)*ab[i]
    return ret
def count2(a):
    ret=0
    while a%2==0:
        a//=2
        ret+=1
    return 2**ret
n,m=map(int,input().split())
A=list(map(int,input().split()))
if any(i%2 for i in A):
    exit(print(0))
A=[i//2 for i in A]
#全体の最小公倍数
p=lcm(A)
c=count2(p)
#2で割り切れる回数が同じでないものがある場合
#違うじゃん
if any(i%c for i in A):
    exit(print(0))
x=m//p
#print(p//c)
if x%2==0:
    print(x//2)
else:
    print(x//2+1)

Submission status: Accepted

Solution code:
from functools import reduce
import math
def lcm_base(x, y):
  return (x * y) // math.gcd(x, y)

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

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

n,m = map(int, input().split())
a = list(map(int, input().split()))
a = [i//2 for i in list(set(a))]
nothing = False
cnt_common = -1
for i in a:
  cnt = 0
  while i % 2 == 0:
    i = i//2
    cnt += 1
  if cnt_common == -1:
    cnt_common = cnt
    continue
  if cnt_common != cnt:
    nothing = True
    break

b=lcm_list(a)
if nothing:
  print(0)
else:
  ans = (m-b)//(2*b) + 1
  print(max(ans,0))

Submission status: Accepted

Solution code:
from math 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)
n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):
  a[i]//=2
b=lcm(*a)
if b>m:
  print(0)
  exit()
i=a[0]
j=0
cnt=0
while (i>>j)&1==0:
  j+=1
  cnt+=1
for i in a[1:]:
  j=0
  ans=0
  while (i>>j)&1==0:
    j+=1
    ans+=1
  if ans!=cnt:
    print(0)
    break
else:print((m+b)//(2*b))

Submission status: Accepted

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

Submission status: Accepted

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

N,M=(int(x) for x in input().rstrip('\n').split())
As=[int(x) for x in input().rstrip('\n').split()]
n = 1
use2 = 0
check = 0
for i in range(N):
  x = As[i]
  if i==0:
    while x % 2==0:
      use2+=1 
      x = x//2
    lcm=x
  else:
    use=0
    while x%2==0:
      x = x//2
      use += 1
    if use2 != use:
      check += 1
      break
    lcm=lcm*x//(math.gcd(lcm,x))
if check > 0:
  print(0)
else:
  LCM=2**(use2-1)
  LCM=LCM*lcm
  print(((M//LCM)+1)//2)

Submission status: Accepted

Solution code:
from sys import exit
from math import gcd
n, m  = map(int, input().split())
A = list(map(int, input().split()))
Count = [0] * n

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

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

for i, a in enumerate(div_A):
    while a % 2 == 0:
        Count[i] += 1
        a //= 2
if len(set(Count)) != 1:
    print(0)
    exit()

lcm_num = 1
for div_a in div_A:
    lcm_num = lcm(div_a, lcm_num)
    if lcm_num > m:
        print(0)
        exit()
else:
    print((m + lcm_num) // (2 * lcm_num))

Submission status: Accepted

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

def gcd(num1,num2):
    r=1
    while r>0:
        r=num1%num2
        num1=num2
        num2=r
    return num1

def lcm(num1,num2):
    gcd1=gcd(num1,num2)
    return num1*num2//gcd1

lcm1=a[0]//2
lcm2=a[0]

for i in range(1,n):
    t=a[i]
    lcm1=lcm(lcm1,t//2)
    lcm2=lcm(lcm2,t)
    ta=max(t//2,lcm1)
    tb=min(t//2,lcm1)
    if ta!=tb and ta//tb%2==0:
        lcm1=0
        lcm2=0
        break

if lcm1!=0:
    ans1=m//lcm1
    ans2=m//lcm2
    ans=ans1-ans2
else:
    ans=0

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
aas = set(list(map(int, input().split())))
a = [i//2 for i in aas]
import math
N = len(a)
def n_of_twos(x):
    res = 0
    while x%(2**(res+1))==0:
        res += 1
    return res
if N>=2:
    n_of_twos_0 = n_of_twos(a[0])
    for i in range(1,N):
        if n_of_twos(a[i]) != n_of_twos_0:
            print(0)
            exit()
ans = a[0]
for i in range(1, N):
    ans = ans * a[i] // math.gcd(ans, a[i])
if ans > m:
    print(0)
    exit()
print(1 + (m//ans-1)//2)

Submission status: Accepted

Solution code:
import fractions
import math

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

flg = True
times = None
for i,a in enumerate(A):
  t = 0
  while a%2==0:
    a //= 2
    t += 1

  if times is None:
    times = t
  else:
    if times != t:
      flg = False
      break
  A[i] = a
M >>= times

if not flg:
  print(0)
  exit()

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

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

Submission status: Accepted

Solution code:
import math
from functools import reduce
from copy import deepcopy
n,m = map(int,input().split())
A = list(map(int,input().split()))
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
def lcm_list(numbers):
  return reduce(lcm_base, numbers, 1)
Acopy = deepcopy(A)
flag = -1
for i in range(n):
  cnt = 0
  while True:
    if Acopy[i] % 2 == 1:
      break
    else:
      Acopy[i] //= 2
      cnt += 1
  if i == 0:
    flag = cnt
  else:
    if flag != cnt:
      print(0)
      break
else:
  A = [a//2 for a in A]
  lcm = lcm_list(A)
  print((lcm+m)//2//lcm)

Submission status: Accepted

Solution code:
from math import gcd

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

n, m = map(int, input().split())
a = list(map(int, input().split()))
l = [0] * n
for i in range(n):
    tmp = a[i]
    while tmp % 2 == 0:
        tmp //= 2
        l[i] += 1
    if i > 0 and l[i] != l[i - 1]:
        print(0)
        exit(0)
res = 1
for i in range(n):
    res = lcm(res, a[i] // 2)
print(m // res - m // (res * 2))

Submission status: Accepted

Solution code:
import sys
import math

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

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def LCM(a, b):
    return a * b // math.gcd(a, b)


def main():
    N, M = in_nn()
    a = in_nl()

    lcm = 1
    for i in range(N):
        lcm = LCM(lcm, a[i])
        if lcm > M * 2:
            print(0)
            exit()

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

    lcm = lcm // 2
    q = M // lcm
    if q % 2 == 0:
        ans = q // 2
    else:
        ans = q // 2 + 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math 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 evencount(n):
  cnt=0
  while n%2==0:
    cnt+=1
    n//=2
  return cnt
n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):
  a[i]//=2
if all(evencount(i) == evencount(a[0]) for i in a):
  d=lcm(*a)
  print((m+d)//2//d)
else:print(0)

Submission status: Accepted

Solution code:
import math
n,m= map(int,input().split())
al= list(map(int,input().split()))
twos = set()
for c in al:
    temp,tempc=0,c
    while tempc%2==0:
        tempc//=2
        temp+=1
    twos.add(temp)
if len(twos)>1:print(0)
else:
    lcmv=al[0]
    for i in range(1,n):lcmv = lcmv*al[i] // math.gcd(lcmv,al[i])
    print(max(0,1 + (m-lcmv//2)//lcmv))

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

def lcm(a,b): # lcmは標準ライブラリには存在しない
    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): # 最下位ビットが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] # a_k/2 を考える
lc = ls_lcm(A)
print ((M + lc) // (2*lc)) # 最小公倍数を奇数倍したものが条件を満たす

Submission status: Accepted

Solution code:
from math import gcd
from functools import reduce

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

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

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

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


x = [v // 2 for v in A]
if all(even_count(v) == even_count(x[0]) for v in x):
    num = lcm_list(x)
    print(-(-(M // num) // 2))
else:
    print(0)

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    A = tuple(map(int,input().split()))
    ans = count(A, N, M)
    print(ans)
def count(A, N, M):
    t = hMt(A[0])
    B = [A[0]//(2**t)]
    for val in A[1:]:
        if hMt(val) != t:
            ans = 0
            return ans
        B.append(val//(2**t))
    T = nlcm(B)
    MdivT = (M//(2**(t-1)))//T
    ans = countodd(MdivT)
    return ans
def countodd(num):
    if num%2 == 0:
        ans = num//2
    else:
        ans = num//2 + num%2
    return ans
def nlcm(A):
    LCM = A[0]
    for val in A[1:]:
        #print("%d %d gcm:%d LCM:%d"%(LCM,val,gcm(LCM,val),lcm(LCM,val)))
        LCM = lcm(LCM,val)
    return LCM
    
def gcm(a, b):
    abtuple = (a,b)
    abmin = min([0,1], key=lambda x:abtuple[x])
    remainder = abtuple[1-abmin]%abtuple[abmin]
    if remainder == 0:
        return abtuple[abmin]
    return gcm(abtuple[abmin], remainder)
def lcm(a,b):
    prod = a*b
    ans = prod//gcm(a,b)
    return ans
def hMt(num):
    ans = 0
    tmp = num
    while tmp%2 == 0:
        tmp = tmp//2
        ans += 1
    return ans
main()

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)
INF = 10**9
mod = 10**9+7

N,M = I()
a = l()
num1 = format(a[0],'b')[::-1].find('1')
num2 = 1
for i in range(N):
  num2 = lcm(num2,a[i])
  if num1 != format(a[i],'b')[::-1].find('1'):
    print(0)
    exit()
num2 = num2//2
print(math.ceil(M//num2/2))

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

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

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

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

x = f(A[0])
for a in A:
    y = f(a)
    if y != x:
        print(0)
        exit()

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

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

Submission status: Accepted

Solution code:
import math

N, M = [int(_) for _ in input().split()]

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

for i in range(N):
    a = A[i]
    if a % 2 > 0:
        print(0)
        exit()
    A[i] = a // 2


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


c = f(A[0])
for i in range(N):
    if c != f(A[i]):
        print(0)
        exit()
    if c > 0:
        A[i] <<= c

if c > 0:
    M <<= c


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


l = 1
for a in A:
    l = lcm(l, a)
if l > M:
    print(0)
    exit()
print((M // l + 1) // 2)

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
A = list(map(int,input().split()))
# 17:22

import sys
from math import gcd
def lcm(a,b):
    return a//gcd(a,b)*b
#%%
ans = 0
L = 1
for i in range(N):
    L = lcm(L, A[i])
    if L>2*M:
        print(0)
        sys.exit()

L2 = L
L1 = L//2
for a in A:
    if (L//a)&1==0:
        print(0)
        sys.exit()
ans = M//L1 - M//L2
print(ans)

Submission status: Accepted

Solution code:
import sys
from math import gcd
from copy import deepcopy

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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


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

    A_ = deepcopy(A)
    cnt = [0] * n
    for i in range(n):
        while A_[i] % 2 == 0:
            A_[i] //= 2
            cnt[i] += 1
        if i != 0 and cnt[i] != cnt[i - 1]:
            print(0)
            exit()

    L = 1
    for a in A:
        L = lcm(L, a // 2)

    res = m // L - (m // (L * 2))
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

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

def f(n):
    cnt = 0
    while n:
        if n % 2 == 0:
            n //= 2
            cnt += 1
        else:
            break
    return cnt

l = A[0]//2
cnt = f(l)

for k in range(1, N):
    a = A[k]//2
    c = f(a)
    if cnt != c:
        print(0)
        exit()
    l = lcm(l, a)

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

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

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

def main():
    N, M = LI()
    A = LI()
    g = 1
    for i in range(N):
        A[i] //= 2
        g = lcm(g, A[i])

    for a in A:
        if g // a % 2 == 1:
            continue
        else:
            print(0)
            return
    shou = M // g
    if shou % 2 == 1:
        shou -= 1
        ans = shou // 2
        ans += 1
    else:
        ans = shou // 2
    print(ans)


main()

Submission status: Accepted

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

def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)

fv=A[0]//2
fmod=A[0]

for i in range(1,N):
    sv=A[i]//2
    smod=A[i]

    x,y,gcd=egcd(fmod,smod)
    if sv%gcd!=fv%gcd:
        print(0)
        exit(0)
    fv=fv-fmod*x*(fv-sv)//gcd
    fmod=fmod*smod//gcd
    fv=(fv+fmod)%fmod

if M<fv:
    print(0)
    exit(0)

if fv==0:
    print((M-fv)//fmod)
else:
    print((M-fv)//fmod+1)

Submission status: Accepted

Solution code:
from math import gcd, ceil
from functools import reduce
import sys

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

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

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

s = set()
for x in a:
    cur = 0
    y = x
    while y%2 == 0:
        cur += 1
        y //= 2
    s.add(cur)
    if len(s) >= 2:
        print(0)
        sys.exit()
lcm = lcm_list(a)
print((M//lcm+1)//2)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
from math import gcd
from math import floor
def main():
    n, m, *a = map(int, read().split())
    if n == 1:
        r = m >= a[0]//2
        r += floor((m - a[0]//2) / a[0])
        print(int(r))
        sys.exit()
    d = [0] * n
    for i, ae in enumerate(a):
        t1 = 0
        while ae > 1:
            if ae % 2 == 0:
                t1 += 1
                ae /= 2
            else:
                break
        d[i] = t1
    d_c = [de == d[0] for de in d]
    if not all(d_c):
        print(0)
        sys.exit()
    
    div = 2
    a2 = [ae // div for ae in a]
    g = (a2[0] * a2[1]) // gcd(a2[0], a2[1])
    for i1 in range(1, n):
        g = (g * a2[i1]) // gcd(g, a2[i1])
        if g > m:
            print(0)
            sys.exit()
    r = m >= g
    r += floor((m - g) / (g * 2))
    print(int(r))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    N, M = (int(i) for i in input().split())
    from math import gcd

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

    def prime_factorize(n):
        res = {2: 0}
        for i in range(2, 3):
            if i*i > n:
                break
            if n % i != 0:
                continue
            ex = 0
            while n % i == 0:
                ex += 1
                n //= i
            res[i] = ex
        if n != 1:
            res[n] = 1
        return res

    B = [int(i)//2 for i in input().split()]
    c = set()
    L = 1
    for b in B:
        L = lcm(L, b)
        c.add(prime_factorize(b)[2])

    if len(c) != 1:
        print(0)
    else:
        ans = 0
        i = 1
        while L*i <= M:
            ans += 1
            i += 2
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
from math import ceil

n,m = map(int,input().split())
a = list(map(int,input().split()))
a = [x//2 for x in a]
lcm = np.lcm.reduce(a)
ans = 0

for i in a:
    if lcm // i % 2 == 0:
        break
else:
    ans = ceil((m//lcm)/2)

print(ans)

Submission status: Accepted

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

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

def cnt(a):
  res = 0
  while(a and a % 2 == 0):
    a //= 2
    res += 1
  return res

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

l = 1
c = cnt(A[0])
for a in A:
  if cnt(a) != c or c == 0:
    print(0)
    exit()
  else:
    l = lcm(l, a // 2)
d = m // l
print((d + 1) // 2)

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
def lcm(a, b):
    """最小公倍数"""
    from math import gcd
    return (a * b) // gcd(a, b)


# from decorator import stop_watch
#
#
# @stop_watch
def solve(N, M, As):
    if sum([a % 2 for a in As]) > 0:
        print(0)
        return

    As = [a // 2 for a in As]
    all_lcm = 1
    for a in As:
        all_lcm = lcm(all_lcm, a)
        if all_lcm > M:
            print(0)
            return

    for a in As:
        if (all_lcm // a) % 2 == 0:
            print(0)
            return
    from math import ceil
    print(ceil(M // all_lcm / 2))


if __name__ == '__main__':
    N, M = map(int, input().split())
    As = [int(i) for i in input().split()]

    # import random
    # N, M = 10 ** 5, 10 ** 9
    # As = [random.randint(5, 5) * 2 for _ in range(N)]
    solve(N, M, As)

Submission status: Accepted

Solution code:
# ABC150D

import sys
input=sys.stdin.readline
from math import gcd,ceil

def main():
    N,M=map(int,input().split())
    A=list(map(lambda x: int(x)//2,input().split()))
    lcm=A[0]
    for i in range(1,N):
        lcm=lcm*A[i]//gcd(lcm,A[i])
    allo=1
    for i in range(N):
        allo&=(lcm//A[i])%2
    if allo:
        print(ceil(int(M//lcm)/2))
    else:
        print(0)
    
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import math

n, m = map(int, input().split())
a = list(map(int, input().split()))
b = {}
for i in range(n):
    count = 0
    temp = a[i]
    while temp % 2 == 0:
        count += 1
        temp //= 2
    b.setdefault(count, 0)
    b[count] += 1
if len(b.keys()) >= 2:
    ans = 0
else:
    temp = 1
    for i in range(n):
        temp = temp * a[i] // math.gcd(temp, a[i])
    temp2 = temp // 2
    ans = m // temp2 - m // temp
print(ans)

Submission status: Accepted

Solution code:
from math import gcd
def lcm(a,b):return (a*b)//(gcd(a,b))

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

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

t=f(a[0])
for i in range(n):
    if(f(a[i])!=t):
        print(0)
        exit()
    a[i]=a[i]//(2**t)
m=m//(2**t)
l=1
for i in range(n):
    l=lcm(l,a[i])
    if(l>m):
        print(0)
        exit()
m=m//l
print((m+1)//2)

Submission status: Accepted

Solution code:
from fractions import gcd
from math import gcd

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


def get_2(x):
    curr_2 = 0
    curr_x = x
    while curr_x%2 == 0:
        curr_x = curr_x//2
        curr_2 += 1
    return curr_2

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


if n == 1:
    cnt = (m-al[0]//2)//al[0] + 1
    print(cnt)
    exit()



a2_set = set()
a2_set.add(get_2(al[0]))
for a in al:
    two_cnt = get_2(a)
    if two_cnt not in a2_set:
        print(0)
        exit()
    a2_set.add(two_cnt)


curr_lcm = 1
for a in al:
    curr_lcm = lcm(curr_lcm, a//2)

lcm_cnt = m//curr_lcm
lcm_cnt = (lcm_cnt+2-1)//2

# print(curr_lcm)
print(lcm_cnt)

Submission status: Accepted

Solution code:
from functools import reduce

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

Bs = [A//2 for A in As]

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

nums = []
for B in Bs:
    num = 0
    while B%2 == 0:
        B //= 2
        num += 1
    nums.append(num)

if len(set(nums)) != 1:
    ans = 0
else:
    L = reduce(lcm, Bs)
    ans = M//L - M//(2*L)

print(ans)

Submission status: Accepted

Solution code:
import math
import numpy as np
N,M=map(int,input().split())
A=list(map(int,input().split()))
c=1
test=A[0]
l=0

while test%2 == 0:
  test=test//2
  c*=2
  
for i in np.arange(N-1):
  if A[i+1]%c!=0:
    print(0)
    l=1
    break
  elif A[i+1]%(c*2)==0:
    print(0)
    l=1
    break
  else:
    k=A[i+1]//c
    test=test*k//math.gcd(test,k)
if l==0:
  k=test*c//2
  print(M//k//2+M//k%2)

Submission status: Accepted

Solution code:
import math
import numpy as np
N,M=map(int,input().split())
A=list(map(int,input().split()))
c=1
test=A[0]
l=0

while test%2 == 0:
  test=test//2
  c*=2

def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
  
for i in np.arange(N-1):
  if A[i+1]%c!=0:
    print(0)
    l=1
    break
  elif A[i+1]%(c*2)==0:
    print(0)
    l=1
    break
  else:
    k=A[i+1]//c
    test=lcm_base(test, k)
if l==0:
  k=test*c//2
  print(M//k//2 + M//k%2)

Submission status: Accepted

Solution code:
import fractions
import math
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 lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

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

for i in range(n):
  if 0==(b//(a[i]//2))%2:
    swt=1
    break

if 0==swt:
  print(math.ceil((m//b)/2))
else:
  print(0)

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):
    return bin(x)[::-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]):#リストのすべての要素の２で割れる回数は等しいか
        count += 1
        break
if count != 0:
    print(0)
else:
    print(math.ceil(q/2))