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 functools import reduce


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


def solve(string):
    n, m, *a = map(int, string.split())
    l = reduce(lcm, a)
    while a[0] % 2 == 0:
        c = a[0] % 2
        for _a in a[1:]:
            if _a % 2 != c:
                return "0"
        if not c:
            a = [_a // 2 for _a in a]
    c = a[0] % 2
    for _a in a[1:]:
        if _a % 2 != c:
            return "0"
    return str(max((m - l // 2) // l + 1, 0))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce


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


def solve(string):
    n, m, *a = map(int, string.split())
    c = 0
    for _a in a:
        if not c:
            while _a % 2 == 0:
                _a //= 2
                c += 1
        else:
            t = 0
            while _a % 2 == 0:
                _a //= 2
                t += 1
            if c != t:
                return "0"
    l = reduce(lcm, a)
    return str(max((m - l // 2) // l + 1, 0))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
def wczytaj_liste(): 
    wczytana_lista = input()
    lista_znakow = wczytana_lista.split()
    ostateczna_lista = []
    for element in lista_znakow:
        ostateczna_lista.append(int(element))
    return ostateczna_lista 

def NWD(A,B): 
    if B == 0: 
        return A
    else: 
        return NWD(B, A%B)  

def nww(x, y): 
    return x*y // NWD(x,y)

def pol_wielokrotnosci(): 
    N, M = wczytaj_liste()
    A = wczytaj_liste()
    potega_2 = A[0]&-A[0]
    for liczba in A:
        if liczba&-liczba != potega_2:
            print(0)
            return
    najmiejsza_wspolna_listy = A[0]
    for i in range(1,len(A)):
        najmiejsza_wspolna_listy = nww(najmiejsza_wspolna_listy, A[i])
        if najmiejsza_wspolna_listy//2 > M:
            print(0)
            return     
    odp = (M - najmiejsza_wspolna_listy//2) // najmiejsza_wspolna_listy + 1
    print(odp)

pol_wielokrotnosci()

Submission status: Accepted

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

N,M = map(int,input().split())
A = np.array(list(map(int,input().split())))
A = A // 2

def lcmb(x,y):
    return (x*y)//fractions.gcd(x,y)
def lcm(L):
    return reduce(lcmb, L, 1)
    
T = lcm(A)

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

m = M//T
if flg:
    ans = 0
elif m%2 == 0:
    ans = m//2
else:
    ans = m//2 + 1
print(ans)

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()))
a.sort(reverse=True)

num_lcm = lcm(*a)
lst = [num_lcm//a_i for a_i in a]

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

harf_lcm = num_lcm // 2
if m < harf_lcm:
    print(0)
else:
    print(1+(m-harf_lcm)//num_lcm)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub
from fractions import gcd

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


# @mt
def slv(N, M, A):
    b = []
    for a in A:
        c = 0
        while a % 2 == 0:
            c += 1
            a //= 2
        b.append(c)
    if not all(map(lambda x: x==b[0], b)):
        return 0

    d = reduce(lambda x, y: x * y//gcd(x, y), A)
    ans = 0
    if M - d//2 >= 0:
        ans = (M-d//2) // d
    if d // 2 <= M:
        ans += 1

    return ans

def main():
    N, M = read_int_n()
    A = read_int_n()
    print(slv(N, M, A))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

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

N, M=map(int, input().split())
A=list(map(int, input().split()))
B=[0 for _ in range(N)]
for i in range(N):
  tmp=A[i]
  while True:
    if tmp%2==1:
      break
    B[i]+=1
    tmp=tmp//2
flag=True
for i in range(N-1):
  if B[i]!=B[i+1]:
    flag=False
    break
ans=0
if flag:
  A=[a//2 for a in A]
  lcm=reduce(lcm_base, A, 1)
  ans=1+(M-lcm)//(2*lcm)
print(ans)

Submission status: Accepted

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

lcm = a[0]//2

for x in a:
    x //= 2
    g = fractions.gcd(lcm, x)
    if (lcm//g)%2 != (x//g)%2:
        print(0)
        quit()

    lcm = lcm*x//g

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

Submission status: Accepted

Solution code:
import sys
import fractions
n,m=map(int,input().split())
A=list(map(int,input().split()))
A=list(map(lambda x: x//2, A))

def dev2(x):
    c=0
    while x%2==0:
        x=x//2
        c+=1
    return c

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

if n==1:
    if A[0]<=m:
        print(int((m/A[0]+1)/2))
    else:
        print(0)
else:
    d=dev2(A[0])
    for i in range(n-1):
        if dev2(A[i+1]) != d:
            print(0)
            sys.exit()
    l=A[0]
    for i in range(n-1):
        l=lcm(l,A[i+1])
        if l>m:
            print(0)
            sys.exit()
    print(int((m/l+1)/2))

Submission status: Accepted

Solution code:
from fractions import gcd
def main():
    n,m=map(int,input().split())
    a=list(map(int,input().split()))
    ta = a[0]
    res = 0
    while ta % 2 == 0:
        res += 1
        ta //= 2
    for sa in a:
        tres = 0
        while sa % 2 == 0:
            tres += 1
            sa //= 2
        if res != tres:
            return 0
    hc = 1
    m2 = m*2
    for i in range(n):
        hc = (hc*a[i])//gcd(hc,a[i])
        if hc > m2:
            return 0
    hc //= 2
    ret = m // hc
    return (ret+1)//2

print(main())

Submission status: Accepted

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

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

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

def solve(n, m, a):
    S = set(map(count, a))
    if len(S) > 1:
        return 0
    b = a[0]
    for i in range(1, n):
        b = lcm(b, a[i])
    b //= 2
    return (m // b + 1) // 2

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

Submission status: Accepted

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

def lcm(*x):
    result = 1
    for x0 in x:
        d = gcd(result, x0)
        result = result // d * x0
    return result

def p_adic_valuation(n, p):
    result = 0
    while n % p == 0:
        n //= p
        result += 1
    return result

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

def solve():
    v = p_adic_valuation(a[0], 2)
    for i in range(1, N):
        if p_adic_valuation(a[i], 2) != v:
            return 0
    assert v > 0
    X_min = lcm(*a) // 2
    return M // X_min - M // (2 * X_min)

print(solve())

Submission status: Accepted

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N,M=LI()
BS=list(map(lambda x: x//2, LI()))

LCM=1
GCD=BS[0]
for i in range(N):
    LCM = LCM*BS[i]//gcd(LCM, BS[i])
    GCD = gcd(GCD, BS[i])

# print("LCM:{}".format(LCM))

if (LCM//GCD) % 2 == 0:
    print(0)
else:
    print(M//LCM//2 + (M//LCM)%2)

Submission status: Accepted

Solution code:
import fractions
import functools

def lcm(n1, n2):
    return n1 * n2 // fractions.gcd(n1, n2)

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

lcmA = functools.reduce(lcm, A)
gcdA = functools.reduce(fractions.gcd, A)
if (lcmA // gcdA) % 2 == 0:
    print(0)
else:
    print((M // lcmA + 1) // 2)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
 
import fractions
 
n, m = map(int, input().split(" "))
numbers = list(set(map(int, input().split(" "))))
 
for i in range(len(numbers)):
    if i == 0:
        gcd = numbers[i]
        lcm = numbers[i]
    else:
        gcd = fractions.gcd(gcd, numbers[i])
        lcm = (lcm * numbers[i]) // fractions.gcd(lcm, numbers[i])
 
if (lcm//gcd) % 2 == 0:
    print(0)
else:
    init_num = lcm // 2
    print((m - init_num) // lcm + 1)

Submission status: Accepted

Solution code:
import sys
import fractions
from functools import reduce
input = sys.stdin.readline
n, m = [int(x) for x in input().rstrip().split()]
a = [int(x)//2 for x in input().rstrip().split()]
a = list(set(a))

def lcm_base(x, y): return x * y // fractions.gcd(x, y)
lcm = reduce(lcm_base, a, 1)


for x in a:
    if (lcm // x) % 2 == 0:
        print(0)
        break
else:
    print((m // lcm + 1) // 2)

Submission status: Accepted

Solution code:
import sys
import fractions
from functools import reduce
input = sys.stdin.readline
n, m = [int(x) for x in input().strip().split()]
a = [int(x)//2 for x in input().strip().split()]
a = list(set(a))

def lcm_base(x, y): return x * y // fractions.gcd(x, y)
lcm = reduce(lcm_base, a, 1)


for x in a:
    if (lcm // x) % 2 == 0:
        print(0)
        break
else:
    print((m // lcm + 1) // 2)

Submission status: Accepted

Solution code:
import fractions
from functools import reduce

def main():
    n,m=map(int,input().split())
    a=list(map(int,input().split()))
    modtmp = 0
    for i,aa in enumerate(a):
        j = 0

        while aa % 2 == 0:
            aa //= 2
            j+=1
        if i == 0:
            modtmp = j
        else:
            if modtmp != j:
                print(0)
                return

    for i,aa in enumerate(a):
        a[i] = aa//2
    tmp = lcm(*a)
    # print(tmp)
    cnt =0
    # print(a)

    up = m//tmp
    if up % 2 == 0:
        up = up//2
    else:
        up = up//2 + 1

    nowtmp = tmp
    cnt = 0
    ans = 0
    a.sort()
    # print(nowtmp)
    # print(up)
    before = 0
    before_aa = 0
    print(up)
    return
    

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)
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import fractions
from functools import reduce

def main():
    n,m=map(int,input().split())
    a=list(map(int,input().split()))
    
    for i,aa in enumerate(a):
        j = 0

        while aa % 2 == 0:
            aa //= 2
            j+=1
        if i == 0:
            modtmp = j
        else:
            if modtmp != j:
                print(0)
                return

    for i,aa in enumerate(a):
        a[i] = aa//2
    tmp = lcm(*a)
    # print(tmp)
    cnt =0
    # print(a)

    up = m//tmp
    if up % 2 == 0:
        up = up//2
    else:
        up = up//2 + 1

    nowtmp = tmp
    cnt = 0
    ans = 0
    a.sort()
    # print(nowtmp)
    # print(up)
    before = 0
    before_aa = 0
    print(up)
    return
    for i, aa in enumerate(a):
        if before_aa == aa:
            continue
        if aa == 1:
            print(up)
            return
        if aa <= nowtmp and aa>before:
            cnt += 1

        elif aa> nowtmp :
            ans += cnt * up
            up -=1
            cnt = 0
            nowtmp += tmp
            before += tmp
    ans += cnt * up
    print(ans)

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)
if __name__=='__main__':
    main()

Submission status: Accepted

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

for i in range(N):
    cnt=0
    num=a[i]
    while num%2==0:
        cnt+=1
        num//=2
    A.append(cnt)
A.sort()
if A[0]!=A[-1]:
    print(0)
    exit()

def lcm(x,y):
    if y>x:
        x,y=y,x
    X=x
    Y=y
    while X%Y!=0:
        X,Y=Y,X%Y
    return x*y//Y
    
LCM=a[0]

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from fractions import gcd

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

N, M = map(int, input().split())
a = list(map(int, input().split()))
for i in range(N):
    a[i] = a[i] // 2
t = fe(a[i])
for i in range(N):
    tmp = fe(a[i])
    if tmp != t:
        print(0)
        exit()
    a[i] >>= t
M >>= t

l = 1
for i in range(N):
    l = l * a[i] // gcd(l, a[i])
    if l > M:
        print(0)
        exit()
M //= l
ans = (M + 1) // 2
print(ans)

Submission status: Accepted

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

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(x, y):
    return (x * y) // gcd(x, y)

def count2(x):
    c=0
    while x%2==0:
        x//=2
        c+=1
    return c

c2=count2(A[0])
LCM=1

for a in A:
    if count2(a)!=c2:
        print(0)
        sys.exit()

    LCM=lcm(a//2,LCM)
    if LCM>M:
        print(0)
        sys.exit()

print(max(0,(M-LCM)//(2*LCM)+1))

Submission status: Accepted

Solution code:
from fractions import gcd

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

gcd_n = A[0]
for a in A:
    gcd_n = gcd(gcd_n, a)

for a in A:
    if (a // gcd_n) % 2 == 0:
        print(0)
        exit()

lcm_n = 1
for a in A:
    lcm_n = (lcm_n * a // 2) // gcd(lcm_n, a // 2)

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

Submission status: Accepted

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

def gcd(n, m):
    while m > 0:
        n, m = m, n%m

    return n

def f(M, A):
    lcm = 1

    for a in A:
        g = gcd(lcm, a)
        lcm = lcm*a//g

        if lcm > M:
            return 0

    for a in A:
        if lcm//a%2 == 0:
            return 0

    return (M-lcm)//(2*lcm) + 1
            


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

    print(f(M,A))

    



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
g = A[-1]
l = A[-1]
import fractions
for i in range(2,N+1):
    a = A[-i]
    g = fractions.gcd(l,a)
    l = l*a//g
    if l//2 > M:
        print(0)
        quit()
b = l//2
f = (M-b)//l + 1
for i in range(N):
    if b%A[i] == 0:
        f = 0
        break
if M < l//2:
    ans = 0
else:
    ans = f
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
import math
def gcd(x,y):
    if x%y==0:
        return y
    else:
        return gcd(y,x%y)
def lcm(x,y):
    return x*y//gcd(x,y)
a[0]=a[0]//2
l=a[0]
cnt=0
while a[0]%2==0:
    a[0]=a[0]//2
    cnt+=1
    
for i in range(1,n):
    a[i]=a[i]//2
    l=lcm(l,a[i]) 
    x=0
    while a[i]%2==0:
        a[i]=a[i]//2
        x+=1
    if x!=cnt:
        print(0)
        exit()

print(((m//l-1)//2)+1)

Submission status: Accepted

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

a = list(set(map(int, input().split(" "))))
g = a.copy()

while not any(x%2 for x in g): g = [i //2 for i in g]

if not all(x%2 for x in g): print(0); exit(0)

def gcd(a, b):

    while b:

        a, b = b, a % b
    return a

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


tot = 1

for x in a: tot = lcm(tot, x//2)
print((M//tot+1)//2)

Submission status: Accepted

Solution code:
import fractions
n,m=map(int,input().split())
lis  = list(map(int,input().split()))
#aそれぞれを2で割ったものを持っておく
div = []
for i in range(n):
    div.append(lis[i]//2)
#lisそれぞれの要素を2で割り切れる回数をすべて数える
L = []
for i in range(n):
    cnt = 0
    while lis[i] %2 ==0:
        lis[i] //= 2
        cnt += 1
    L.append(cnt)

bl = True
#重複要素を削除して要素数でLがすべて一緒か判断
def set_list(es):
    return len(list(set(es))) == 1

if set_list(L) != 1:
    print(0)
    exit()

#div内の最小子公倍数ansを求める

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

S = m//ans
if S %2 ==0:
    print(S//2)
else:
    print(S//2 +1)

Submission status: Accepted

Solution code:
import math
import fractions
n,m=map(int, input().split())
a=list(map(int, input().split()))
b=[]
s=math.floor(math.log2(max(a)))
buf=0
for i in range(n): #aは偶数なので、1/2した値の配列を作った
    b.append(int(a[i]//2))

for i in range(s+1): #2のi乗ですべての数が割れるかどうか
    for j in b:
        if j%(2**i)==0:
            buf+=1
        else:
            continue
    if buf==n:
        buf=0
        continue
    else:
        break

def lcm(x,y): #最小公倍数を求める関数の定義
    return (x*y)//fractions.gcd(x,y)

if buf!=0 and buf!=n: #偶奇が入り混じってるとき
    print(0)
elif n==1: #配列の要素が1つしかないとき
    d=int(m//b[0])
    print(int((d+1)//2))
else:
    c=[lcm(b[0],b[1])] #以下のサイクルで求めた最小公倍数を入れる配列
    for i in range(1,n-1):
        x=lcm(c[i-1],b[i+1])
        c.append(x)
        if x<m:
            continue
        else:
            break
    d=int(m//c[len(c)-1]) #最後の値(c[len(c)-1])が配列bの最小公倍数
    ans=int((d+1)//2)
    print(ans)

Submission status: Accepted

Solution code:
import math
import fractions
n,m=map(int, input().split())
a=list(map(int, input().split()))
b=[]
s=math.floor(math.log2(max(a)))
buf=0
for i in range(n): #aは偶数なので、1/2した値の配列を作った
    b.append(int(a[i]//2))

for i in range(s+1): #2のi乗ですべての数が割れるかどうか
    for j in b:
        if j%(2**i)==0:
            buf+=1
        else:
            continue
    if buf==n:
        buf=0
        continue
    else:
        break

def lcm(x,y): #最小公倍数を求める関数の定義
    return (x*y)//fractions.gcd(x,y)

if buf!=0 and buf!=n: #偶奇が入り混じってるとき
    print(0)
elif n==1: #配列の要素が1つしかないとき
    d=int(m//b[0])
    print(int((d+1)//2))
else:
    c=[lcm(b[0],b[1])] #以下のサイクルで求めた最小公倍数を入れる配列
    for i in range(1,n):
        x=lcm(c[i-1],b[i])
        c.append(x)
        if x<m:
            continue
        else:
            break
    d=int(m//c[len(c)-1]) #最後の値(c[len(c)-1])が配列bの最小公倍数
    ans=int((d+1)//2)
    print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import fractions
n,m=map(int,input().split())
lis  = list(map(int,input().split()))
#aそれぞれを2で割ったものを持っておく
div = []
for i in range(n):
    div.append(lis[i]//2)
#lisそれぞれの要素を2で割り切れる回数をすべて数える
L = []
for i in range(n):
    cnt = 0
    while lis[i] %2 ==0:
        lis[i] //= 2
        cnt += 1
    L.append(cnt)

bl = True
#重複要素を削除して要素数でLがすべて一緒か判断
def set_list(es):
    return len(list(set(es))) == 1

if set_list(L) != 1:
    print(0)
    exit()

#div内の最小子公倍数ansを求める

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

S = m//ans
if S %2 ==0:
    print(S//2)
else:
    print(S//2 +1)

Submission status: Accepted

Solution code:
import math
import sys
from fractions import gcd
m=10**9 + 7 
sys.setrecursionlimit(1000010)
(N, M) = list(map(int,input().split()))
A  = list(map(int,input().split()))
B = [ a//2 for a in A]

def log2N (x):
    c = 0
    while True:
        if x % 2 != 0:
            return c
        x = x // 2
        c = c + 1


def lcmn(B):
    if len(B)<1 :
        return 1
    elif len(B) == 1:
        return B[0]
    
    x = B[0] * B[1] // gcd(B[0],B[1])
    if x > M:
        return -1 

    for i in range(2,len(B)):
        x  = lcmn([x,B[i]])
        if x > M:
            return -1 
    return x
    

#print(N,M,A,B)

# print(lcmn(B))

p = log2N(B[0])
# print(p)
for i in range(1,len(B)):
    # print(log2N(B[i]))
    if p != log2N(B[i]):
        print(0)
        exit(0)
        
x = lcmn(B)
if x == -1:
    print(0)
else:
    print((M//x+1)//2)

Submission status: Accepted

Solution code:
import fractions
def main():
    N,M = map(int,input().split())
    A = [int(x)//2 for x in input().split()]
    # check
    ls = []
    for i in range(N):
        now = A[i]
        cnt = 0
        while 1:
            if now%2==0:
                now = now//2
                cnt +=1
            else:
                ls.append(cnt)
                break

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


    sub = A[0]
    for i in range(1,N):
        sub = sub*A[i]//fractions.gcd(sub,A[i])
    B = M//sub
    print((B-1)//2+1)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions import gcd

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

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


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

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

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

m //= l

ans = (m+1) // 2

print(ans)

Submission status: Accepted

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

N, M = map(int, input().split())
a = [int(c) for c in input().split()]
b = [c//2 for c in a]
g = reduce(lcm_base, b, 1)
G = reduce(lcm_base, a, 1)
if M<g:
  print(0)
  import sys
  sys.exit()
m = a[0]&-a[0]
for i in range(N):
  if m != a[i]&(-a[i]):
    print(0)
    break
else:
  n = (M-g)//G
  print(n+1)

Submission status: Accepted

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

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

n, m = map(int, input().split())
a = [int(item) // 2 for item in input().split()]
b = [0] * n

for i in range(n):
    tmp = a[i]
    while True:
        if tmp % 2 == 0:
            b[i] += 1
            tmp /= 2
        else:
            break

if len(set(b)) != 1:
    print(0)
    sys.exit()

a_lcm = lcm(a)
count = m // a_lcm
if count % 2 == 0:
    print(count // 2)
else:
    print((count + 1) // 2)

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd

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

N, M = map(int, input().split())
A = [int(x)//2 for x in input().split()]
B = [0] * N
for i in range(N):
    a = A[i]
    cnt = 0
    while a % 2 == 0:
        cnt += 1
        a //= 2
    B[i] = cnt

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

c = reduce(lcm, A)

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

Submission status: Accepted

Solution code:
from fractions import gcd
def lcm(a):

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

def map_all(es):
    return all([e == es[0] for e in es[1:]]) if es else False

n,m = map(int,input().split())
a = list(map(int,input().split()))
tmp = [0] * n
for i in range(n):
    tmpnum = a[i]
    while 1:
        if tmpnum%2:
            break
        else:
            tmpnum/=2
            tmp[i]+=1

if not map_all(tmp):
    print('0')
    exit()
    
tmplcm = lcm(a)


m -= tmplcm//2
ans = m // tmplcm +1

print(max(ans,0))

Submission status: Accepted

Solution code:
import math
import fractions
n,m=map(int, input().split())
a=list(map(int, input().split()))
b=[]
s=math.floor(math.log2(max(a)))
buf=0
for i in range(n): #aは偶数なので、1/2した値の配列を作った
    b.append(int(a[i]//2))

for i in range(s+1): #2のi乗ですべての数が割れるかどうか
    for j in b:
        if j%(2**i)==0:
            buf+=1
        else:
            continue
    if buf==n:
        buf=0
        continue
    else:
        break

def lcm(x,y): #最小公倍数を求める関数の定義
    return (x*y)//fractions.gcd(x,y)

if buf!=0 and buf!=n: #偶奇が入り混じってるとき
    print(0)
elif n==1: #配列の要素が1つしかないとき
    d=int(m//b[0])
    print(int((d+1)//2))
else:
    c=[lcm(b[0],b[1])] #以下のサイクルで求めた最小公倍数を入れる配列
    for i in range(1,n):
        x=lcm(c[i-1],b[i])
        c.append(x)
        if x<m:
            continue
        else:
            break
    d=int(m//c[len(c)-1]) #最後の値(c[len(c)-1])が配列bの最小公倍数
    ans=int((d+1)//2)
    print(ans)

Submission status: Accepted

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

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

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

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

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

t = f(a[0])

ans = 0
for i in range(n):
    if f(a[i]) != t:
        print(0)
        exit()
    a[i] >>= t

m >>= t

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

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

Submission status: Accepted

Solution code:
import fractions
import copy
n, m = map(int, input().split())
a_list = [int(i) for i in input().split()]

c = 1
b_list = []
for a in a_list:
    d = copy.deepcopy(a)
    k = 1
    while (d % 2 == 0):
        d = d // 2
        k *= 2
    b_list.append(k)
    c = c * (a // 2) // fractions.gcd(c, a // 2)
if len(list(set(b_list))) > 1:
    print(0)
elif (m // c) % 2 == 0:
    print((m // c) // 2)
else:
    print(((m // c) // 2) + 1)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
import copy
b=copy.deepcopy(a)
t=0
while b[0]%2==0:
    b[0]//=2
    t+=1

def div2():
    for i in range(1,n):
        cnt=0
        while b[i]%2==0:
            b[i]//=2
            cnt+=1
        if t!=cnt:
            print(0)
            exit()
div2()
for i in range(n):
    a[i]=a[i]//2
import fractions
lcm=a[0]
for i in range(n-1):
    tmp=lcm*a[i+1]//fractions.gcd(lcm,a[i+1])
    lcm=max(lcm,tmp)
if m//lcm%2==0:
    print(m//lcm//2)
else:
    print(((m//lcm)+1)//2)

Submission status: Accepted

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

##半公倍数が存在するかチェック
def check_exist(l) :
  if(len(l) == 1) :
    return True
  while(True) :
    flag = l[0] % 2
    for x in l[1:] :
      if(x % 2 != flag) :
        return False
    if(flag == 0) :
      l = list(map(lambda x: int(x/2), l))
    else :
      return True
    

##最大公約数を求める

def gcd(a, b) :
  if(b==0) :
    return a
  else :
    return gcd(b, a%b)
   
##最小公倍数を求める
def lcm(a, b) :
  cd = gcd(a, b)
  return (a / cd) * b
  
##複数個の整数の最小公倍数を求める
def lcm_multi(l) :
  cm = 1
  for x in l :
    cm = lcm(x, cm)
    if(cm > 4 * M) :
      print(0)
      exit()
    
  return cm

if(not(check_exist(list_a))) :
  print(0)
  exit()

## 1/2の公倍数
lcm_m = lcm_multi(list(map(lambda x: int(x/2), list_a)))

if(M-lcm_m < 0) :
  print(0)
else :
  print(int((M-lcm_m) / (2*lcm_m)) + 1)

Submission status: Accepted

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


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


# 各要素について、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()


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


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


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

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

n, m = map(int, input().split())
a = [i // 2 for i in set(list(map(int, input().split())))]
b = []
for i in a:
    cnt = 0
    while i % 2 == 0:
        i //= 2
        cnt += 1
    b.append(cnt)

L = 1
ans = 0
if len(set(b)) == 1:
    for j in a:
        L = lcm(j, L)
        if m < L:
            ans = 0
            break
        else:
            ans = (m // L) - (m // (L * 2))
    print(ans)
else:
    print(0)