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 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=[int(i)//2 for i in input().split()]
q=lcm(*A)
#print(q)
for i in A:
    #print(i)
    if q//i%2==0:
        print(0)
        exit()
print((M//q+1)//2)

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 main():
    from math import ceil

    n, m, *a = map(int, open(0).read().split())
    c = 0
    t = a[0]
    while t % 2 == 0:
        c += 1
        t = t // 2

    for x in a[1:]:
        d = 0
        while x % 2 == 0:
            d += 1
            x = x // 2

        if d != c:
            print(0)
            break

        t = lcm(t, x)
    else:
        ans = ceil(m // 2 ** (c-1) // t / 2)
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    from fractions import gcd
    from math import ceil

    n, m, *a = map(int, open(0).read().split())
    b = [0 for _ in range(n)]
    a.sort()

    for i, j in enumerate(a):
        c = 0
        while j % 2 == 0:
            c += 1
            j = j // 2
        a[i] = j
        b[i] = c

    if len(set(b)) > 1:
        print(0)
        exit()

    lcm = 1
    for i in a:
        lcm = (lcm * i) // gcd(lcm, i)

    k = b[0] - 1
    ans = ceil(m // 2 ** k // lcm / 2)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
def func(n):
  ret=0
  n=n/2
  while n.is_integer():
    ret+=1
    n=n/2
  return ret
b=func(a[0])
for i in range(1,n):
  if b==func(a[i]):
    continue
  else:
    print(0)
    exit(0)
from fractions import gcd
lcmn=a[0]//2
for i in range(1,n):
    lcmn=(lcmn*a[i]//2)//gcd(lcmn,a[i]//2)
print((1+m//lcmn)//2)

Submission status: Accepted

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

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

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

lcm = lcm_list(a)
test = a[0]
count = 0
while test%2 ==0:
    test = test//2
    count += 1
for i in range(N):
    if (a[i]//2**count)%2 == 0:
        print(0)
        exit()
print((M+lcm//2)//lcm)

Submission status: Accepted

Solution code:
import sys
import fractions

readline = sys.stdin.buffer.readline


def main():
    gcd = fractions.gcd

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

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

    B = A[::]
    while not any(b % 2 for b in B):
        B = [b // 2 for b in B]

    if not all(b % 2 for b in B):
        print(0)
        return

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

    print((M // semi_lcm + 1) // 2)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import fractions
from functools import reduce

readline = sys.stdin.buffer.readline


def main():
    gcd = fractions.gcd

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

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

    B = A[::]
    while not any(b % 2 for b in B):
        B = [b // 2 for b in B]

    if not all(b % 2 for b in B):
        print(0)
        return

    semi_lcm = reduce(lcm, (a // 2 for a in A))
    print((M // semi_lcm + 1) // 2)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

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


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


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


def main():
    N, M = map(int, readline().split())
    A = list(set(map(int, readline().split())))

    B = A[::]
    while not any(b % 2 for b in B):
        B = [b // 2 for b in B]

    if not all(b % 2 for b in B):
        print(0)
        return

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

    print((M // semi_lcm + 1) // 2)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

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


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


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


def main():
    N, M, *A = map(int, read().split())
    A = list(set(A))
    B = A.copy()

    while not any(b % 2 for b in B):
        B = [b // 2 for b in B]

    if not all(b % 2 for b in B):
        print(0)
        return

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

    print((M // semi_lcm + 1) // 2)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

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


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


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


def main():
    N, M, *A = map(int, read().split())
    A = list(set(A))
    B = A.copy()

    while not any(b % 2 for b in B):
        B = [b // 2 for b in B]

    if not all(b % 2 for b in B):
        print(0)
        return

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

    print((M // semi_lcm + 1) // 2)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from fractions import gcd

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


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


def main():
    N, M = map(int, input().split())
    A = list(set(map(int, input().split(" "))))
    A = [a // 2 for a in A]
    semi_lcm = 1
    for a in A:
        semi_lcm = lcm(semi_lcm, a)
        if semi_lcm > M:
            print(0)
            return

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

    print((M // semi_lcm + 1) // 2)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from fractions import gcd

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


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


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

    semi_lcm = 1
    for a in A:
        semi_lcm = lcm(semi_lcm, a)
        if semi_lcm > M or semi_lcm // a % 2 == 0:
            print(0)
            return

    print((M // semi_lcm + 1) // 2)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from fractions import gcd

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


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


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

    semi_lcm = A[0]
    for a in A[1:]:
        semi_lcm = lcm(semi_lcm, a)
        if semi_lcm > M or semi_lcm // a % 2 == 0:
            print(0)
            return

    print((M // semi_lcm + 1) // 2)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

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


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


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


def main():
    N, M = map(int, input().split())
    A = list(set(map(int, input().split(" "))))
    B = A.copy()

    while not any(b % 2 for b in B):
        B = [b // 2 for b in B]

    if not all(b % 2 for b in B):
        print(0)
        return

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

    print((M // semi_lcm + 1) // 2)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

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


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


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


def main():
    N, M = map(int, readline().split())
    A = list(map(int, readline().split()))
    B = A.copy()

    while not any(b % 2 for b in B):
        B = [b // 2 for b in B]

    if not all(b % 2 for b in B):
        print(0)
        return

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

    print((M // semi_lcm + 1) // 2)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read


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


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


def main():
    N, M, *A = map(int, read().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)

    total = 1

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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


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


def main():
    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)

    total = 1

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

    A = list(set(map(int, input().split(" "))))
    G = A.copy()

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

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

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

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

    total = 1

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
import sys

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


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


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


def main():
    N, M, *A = map(int, read().split())
    B = A.copy()

    while not any(b % 2 for b in B):
        B = [b // 2 for b in B]

    if not all(b % 2 for b in B):
        print(0)
        return

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

    print((M // semi_lcm + 1) // 2)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

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

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

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


def main():
    N, M, *A = map(int, read().split())
    B = A[::]

    while not any(b % 2 for b in B):
        B = [b // 2 for b in B]

    if not all(b % 2 for b in B):
        print(0)
        return

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

    print((M // semi_lcm + 1) // 2)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from fractions import gcd

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


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


def main():
    N, M, *A = map(int, read().split())
    B = A[::]

    while not any(b % 2 for b in B):
        B = [b // 2 for b in B]

    if not all(b % 2 for b in B):
        print(0)
        return

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

    print((M // semi_lcm + 1) // 2)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from fractions import gcd

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


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


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

    while not any(b % 2 for b in B):
        B = [b // 2 for b in B]

    if not all(b % 2 for b in B):
        print(0)
        return

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

    print((M // semi_lcm + 1) // 2)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from fractions import gcd

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


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


def f(a):
    ans = 0
    while a % 2 == 0:
        a //= 2
        ans += 1
    return ans


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

    p2 = f(A[0])
    for a in A[1:]:
        if p2 != f(a):
            print(0)
            return

    semi_lcm = A[0]
    for a in A[1:]:
        semi_lcm = lcm(semi_lcm, a)

    print((M // semi_lcm + 1) // 2)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from fractions import gcd

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


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


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

    semi_lcm = A[0]
    for a in A[1:]:
        semi_lcm = lcm(semi_lcm, a)
        if semi_lcm > M or semi_lcm // a % 2 == 0:
            print(0)
            return

    print((M // semi_lcm + 1) // 2)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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


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


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

    semi_lcm = reduce(lcm, A)
    for a in A[1:]:
        semi_lcm = lcm(semi_lcm, a)
        if semi_lcm > M or semi_lcm // a % 2 == 0:
            print(0)
            return

    print((M // semi_lcm + 1) // 2)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# x=a_i * (p+0.5)
# 前提としてaが偶数
# x= (a_i//2)*(2*p+1)
from fractions import gcd

n, m = map(int, input().split())
A = list(map(int, input().split()))
koubai = A[0] // 2
temp = koubai & -koubai
for i in range(1, n):
    a = A[i]
    if a % 2 == 1:
        print(0)
        exit()
    a //= 2
    if a & -a != temp:
        print(0)
        exit()
    g = gcd(koubai, a)
    koubai *= a // g


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

Submission status: Accepted

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

for i in range(n):
    a[i] = a[i]//2
    
# print(a)
def calc(n):
    ret = 0
    while n%2 == 0:
        ret +=1
        n//=2
    return ret


flag = True
t = 0
for i in range(n-1):
    t = 2**calc(a[i])
    if calc(a[i]) == calc(a[i+1]):
        # print(calc(a[i]),calc(a[i+1]))
        continue
    else:
        flag = False
        break


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



if flag:
    lcm = 1
    for i in range(n):
        p = max(lcm, a[i])
        q = min(lcm, a[i])
        lcm = lcm*a[i]//gcd(p, q)
        # print(lcm)
    if (m//lcm)%2 == 0:
        print(int((m//lcm)//2))
    else:
        print(int((m//lcm+1)//2))

else:
    print(0)

Submission status: Accepted

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

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
  
N,M = (int(x) for x in input().split())
a = list(map(int,input().split()))
a = [a_i//2 for a_i in a]
lcm = lcm_list(a)
for a_i in a:
  if (lcm // a_i) %2 == 0:
    print(0)
    sys.exit()
  
print((M//lcm)//2 + ((M//lcm)%2==1))

Submission status: Accepted

Solution code:
from fractions import gcd
n,m = map(int, input().split())
a = list(map(int, input().split()))
b = []
lcm = 1
for i in a:
    b.append(i//2)
for i in b:
  lcm = lcm // gcd(lcm,i) * i
ans = m // lcm
sum = 0
for i in b:
  if (lcm // i) % 2 == 1:
    sum += 1
if sum != len(a):
  print(0)
elif ans%2 ==1:
    print((ans+1)//2)
else:
    print(ans//2)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

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

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

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

    t = f(A[0]) 
    for i in A:
        if f(i) != t:
            print(0)
            return

    A = [i//(2**t) for i in A] 
    M //= 2**t    

    l = 1
    for i in A:
        l = lcm(l, i)
        if l > M:
            print(0)
            return
    M //= l
    ans = (M+1)//2
    print(ans)
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)


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


n,m=map(int,input().split())
A=list(map(int,input().split()))
num=lcm(A)
semi=num//2

ans=0
if any([True for i in range(n) if semi%A[i]==0]):print(0)
elif semi<=m:
    ans +=1
    m -=semi
    ans +=m//num
    print(ans)
else:print(0)

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


n,m=map(int,input().split())
A=list(map(int,input().split()))
num=lcm(A)
semi=num//2

ans=0
if any([True for i in range(n) if semi%A[i]==0]):
    print(0)
elif semi<=m:
    ans +=1
    m -=semi
    ans +=m//num
    print(ans)
else:print(0)

Submission status: Accepted

Solution code:
from fractions import gcd

n, m = map(int, input().split())
a = list(map(int, input().split()))
l = 1
num = a[0]
bin = 1
while num % 2 == 0:
    bin *= 2
    num //= 2
for num in a:
    l = (l * num // 2) // gcd(l, num // 2)
    if num % bin != 0 or num % (bin * 2) == 0:
        print(0)
        exit()
print((m + l) // (2 * l))

Submission status: Accepted

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

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

cnt=1
while (a[0]%(2**cnt))==0:
    cnt+=1

cnt-=1
for item in a[1:]:
    if item%(2**cnt)!=0:
        print(0)
        exit()
    if (item//(2**cnt))%2==0:
        print(0)
        exit()


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

if ans%2==1:
    print(0)
    exit()

if ans//2>m:
    print(0)
    exit()

ans=ans//2

print((((m//ans)*(-1))//2)*(-1))

Submission status: Accepted

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

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()))
A = list(map(lambda x: x // 2 , A))
A = np.array(A)

l = lcm(A)

if ((l//A % 2 == 1).sum() != N):
    print(0)
else:
    ans = (M//l + 1) // 2
    print(ans)

Submission status: Accepted

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

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

n, m = map(int, input().split())
a = [int(i) // 2 for i in input().split()]
t = f(a[0])
flag = True
for i in range(n):
    if f(a[i]) != t:
        flag = False
    else:
        a[i] >>= t
m >>= t
l = 1
for i in range(n):
    l = lcm(l, a[i])
    if l > m:
        flag = False
m //= l
print(-(-m // 2) if flag else 0)

Submission status: Accepted

Solution code:
import sys
import itertools
import fractions
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

def frac2(p):
    return p//2

N,M=nm()
A=nl()
A=list(map(frac2,A))
min_bai=A[0]
for i in range(1,N):
    min_bai=min_bai*A[i]//fractions.gcd(min_bai,A[i])

for i in range(N):
    if((min_bai//A[i])%2==0):
        print(0)
        sys.exit(0)


tmp=M//min_bai
if(tmp%2==0):
    tmp-=1

print((tmp+1)//2)

Submission status: Accepted

Solution code:
k, x = map(int, input().split())
l = list(map(int, input().split()))
hl = [i // 2 for i in l]
from fractions import gcd
from functools import reduce
def lcm(a, b):
    return a * b // gcd(a, b)
def lcm_list(l):
    return reduce(lcm, l, 1)
a = lcm_list(hl)
i = hl[0]
cnt = 0
while i % 2 == 0:
    cnt += 1
    i //= 2
flag = True
for i in hl:
    if i % (2 ** cnt) == 0 and i % (2 ** (cnt + 1)) != 0:
        continue
    else:
        flag = False
        break
if flag:
    print((x - a) // (a * 2) + 1)
else:
    print(0)

Submission status: Accepted

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

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

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

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

lcma=reduce(lcm,b)   

yn=""
for i in range(n):
    if (lcma//b[i])%2==0:
        yn="no"
        break
    
if yn=="no":
    print(0)
else:    
    ans=m//lcma
    ans2=ans//2
    if (ans2*2+1)*lcma<=m:
        ans2+=1
    print(ans2)

Submission status: Accepted

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

norm = 0
tmp = lst[0]
while tmp%2 == 0:
  tmp = tmp//2
  norm += 1

for i in range(n):
  count = 0
  tmp = lst[i]
  while tmp%2 == 0:
    tmp = tmp//2
    count += 1
  if norm != count:
    print(0)
    exit()
  lst[i] = lst[i]//2
    
lst = sorted(list(set(lst)))

def lcm(a, b): # a, b の最大公約数を求める
  return(a*b//gcd(a, b))

def lcms(List): # list[a[0], a[1], ... , a[n]]の最小公倍数を求める
  if len(List) == 1:
    return List[0]
  ans = lcm(List[0], List[1])
  for i in range(2, len(List)):
    ans = lcm(ans, List[i])
  return ans
    
lcm = lcms(lst)
ans = m//lcm
if ans%2 == 0:
  ans = ans//2
else:
  ans = ans//2 + 1
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
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)

# def lcm_list(numbers, maxvalue):
#     first = 1
#     second = 1
#     for i in numbers:
#         second = i
#         lcm_result = lcm_base(first, second)
#         if lcm_result > maxvalue:
#             return -1
#         first = lcm_result
#     return lcm_result


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

max_value = 2 * m

try:
    lcm = lcm_list(A)
except:
    print("0")
    sys.exit(0)

if lcm > max_value:
    print("0")
    sys.exit(0)

if lcm == -1:
    print("0")
    sys.exit(0)

if any((lcm / a) % 2 != 1 for a in A):
    print("0")
    sys.exit(0)

max_product = max_value // lcm
print((max_product + 1) // 2)

Submission status: Accepted

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


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


def lcm_list(numbers, maxvalue):
    first = 1
    second = 1
    for i in numbers:
        second = i
        lcm_result = lcm_base(first, second)
        if lcm_result > max_value:
            return -1
        first = lcm_result
    return lcm_result


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

max_value = 2 * m

lcm = lcm_list(A, 2 * m)
if lcm == -1:
    print("0")
    sys.exit(0)

if any((lcm / a) % 2 != 1 for a in A):
    print("0")
    sys.exit(0)

max_product = max_value // lcm
print((max_product + 1) // 2)

Submission status: Accepted

Solution code:
mod = 10**9+7
import sys
from collections import Counter, defaultdict, deque
from itertools import product, permutations, combinations, combinations_with_replacement
from itertools import accumulate
from operator import itemgetter
from bisect import bisect_left,bisect
from heapq import heappop,heappush
from math import ceil,floor
from copy import deepcopy
from heapq import heappop,heappush,heapify
import heapq


# l = ['a', 'a', 'a', 'a', 'b', 'c', 'c']
# c = Counter(l)

# d = defaultdict(int)

sys.setrecursionlimit(10 ** 6)

int1 = lambda x: int(x) - 1

# リストの要素を改行を挟んで表示する
p2D = lambda x: print(*x, sep="\n")
# 入力を整数に変換して受け取る
def II(): return int(sys.stdin.readline())

def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())

# 入力全てを整数に変換したものの配列を受け取る
# def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LI(): return list(map(lambda x:int(x), sys.stdin.readline().split()))
def HI(): return list(map(lambda x:int(x)*(-1), sys.stdin.readline().split()))



# n = II()
# p = tuple(MI())
# q = tuple(MI())

# l = list(permutations(list(range(1,n+1))))
# print(abs(l.index(p)-l.index(q)))
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
 
N, M = MI()
A = LI()
A = [a//2 for a in A]


while A[0] % 2 == 0:
	for i in range(N):
		if A[i] % 2 != 0:
			print(0)
			exit()
		A[i] //= 2
	M //= 2

 
for i in range(N):
	if A[i] % 2 == 0:
		print(0)
		exit()
 
tmp_lcm = 1
for i in range(N):
	tmp_lcm = lcm(tmp_lcm, A[i])
	if M < tmp_lcm:
		print(0)
		exit()
 
print((M // tmp_lcm + 1) // 2)

Submission status: Accepted

Solution code:
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

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

while A[0] % 2 == 0:
    for i in range(N):
        if A[i] % 2 != 0:
            print(0)
            exit()
        A[i] //= 2
    M //= 2

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

lcm_ = 1
for i in range(N):
    lcm_ = lcm(lcm_, A[i])
    if M < lcm_:
        print(0)
        exit()

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

Submission status: Accepted

Solution code:

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

N,M = (int(x) for x in input().split())
A = list(map(int, input().split()))
lcm         =lcm_list(A)
harf_lcm     =lcm//2             # 最小公倍数の半分
harf_lcm_num =M//harf_lcm          # Mの中の半公倍数の個数
harf_lcm_num =(harf_lcm_num +1)//2 # 偶数を除く

#半公倍数がaiで割り切れるときは✖
import numpy as np 
A_np =np.array(A)
if np.any(harf_lcm % A_np ==0):
    harf_lcm_num =0
"""    
for a in A:
    if harf_lcm % a ==0:
        harf_lcm_num =0
        break
"""
print(harf_lcm_num)

Submission status: Accepted

Solution code:
from fractions import gcd

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

a = A[0]
n = 1
while a % 2 == 0:
    n *= 2
    a //= 2

lcm = 1
for a in A:
    if a % n != 0 or a % (2 * n) == 0:
        print(0)
        exit()
    lcm = lcm * a // gcd(lcm, a)
    if lcm // 2 > M:
        print(0)
        exit()

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

Submission status: Accepted

Solution code:

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

N,M = (int(x) for x in input().split())
A = list(map(int, input().split()))
lcm         =lcm_list(A)
harf_lcm     =lcm//2             # 最小公倍数の半分
harf_lcm_num =M//harf_lcm          # Mの中の半公倍数の個数
harf_lcm_num =(harf_lcm_num +1)//2 # 偶数を除く

#半公倍数がA自身の中にある時は✖
#if harf_lcm in A:
 #   harf_lcm_num =0

#半公倍数がaiで割り切れるときは✖
for a in A:
    if harf_lcm % a ==0:
        harf_lcm_num =0
        break

print(harf_lcm_num)