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: Wrong Answer

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

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

# lcd of a1*x1+n1 & a2*x2+n2
def lcd(a1, n1, a2, n2, M):
    if a1*a2 == 0:
        return M, M
    x1 = 0
    x2 = 0
    k1 = n1
    k2 = n2
    while (k1 != k2)&(k1<M+2)&(k2<M+2):
        if k1 < k2:
            x1 += max(1,(k2-k1)//a1)
            k1 = a1*x1 + n1
        else:
            x2 += max(1, (k1-k2)//a2)
            k2 = a2*x2 + n2
        # print(k1, k2)
    return k1, n_lcd(a1, a2)


def solve(N: int, M: int, a: "List[int]"):
    a = sorted(list(set(a)))
    base = 1
    base_n = 0
    for i in a:        
        base_n, base = lcd(base, base_n, i, i//2, M)
        if base >= M:
            print(0)
            return 

    if base > M:
        print(0)
    else:
        print((M-base_n)//base + 1)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, a)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

# lcd of a1*x1+n1 & a2*x2+n2
def lcd(a1, n1, a2, n2, M):
    if a1*a2 == 0:
        return M, M
    x1 = 0
    x2 = 0
    k1 = n1
    k2 = n2
    while (k1 != k2)&(k1<M+2)&(k2<M+2):
        if k1 < k2:
            x1 += 1
            k1 = a1*x1 + n1
        else:
            x2 += 1
            k2 = a2*x2 + n2
        # print(k1, k2)
    return k1, n_lcd(a1, a2)


def solve(N: int, M: int, a: "List[int]"):
    a = sorted(list(set(a)))
    base = 1
    base_n = 0
    for i in a:        
        base_n, base = lcd(base, base_n, i, i//2, M)
        if base >= M:
            print(0)
            return 

    if base > M:
        print(0)
    else:
        print((M-base_n)//base + 1)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, a)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

# lcd of a1*x1+n1 & a2*x2+n2
def lcd(a1, n1, a2, n2, M):
    if a1*a2 == 0:
        return M, M
    x1 = 0
    x2 = 0
    k1 = n1
    k2 = n2
    while (k1 != k2)&(k1<M+2)&(k2<M+2):
        if k1 < k2:
            x1 += 1
            k1 = a1*x1 + n1
        else:
            x2 += 1
            k2 = a2*x2 + n2
        # print(k1, k2)
    return k1, n_lcd(a1, a2)


def solve(N: int, M: int, a: "List[int]"):
    a = sorted(list(set(a)))
    base = 1
    base_n = 0
    for i in a:        
        base_n, base = lcd(base, base_n, i, i//2, M)

    if base > M:
        print(0)
    else:
        print((M-base_n)//base + 1)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, a)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

# lcd of a1*x1+n1 & a2*x2+n2
def lcd(a1, n1, a2, n2, M):
    if a1*a2 == 0:
        return M
    x1 = 0
    x2 = 0
    k1 = n1
    k2 = n2
    while (k1 != k2)&(k1<M+2)&(k2<M+2):
        if k1 < k2:
            x1 += 1
            k1 = a1*x1 + n1
        else:
            x2 += 1
            k2 = a2*x2 + n2
        # print(k1, k2)
    return k1


def solve(N: int, M: int, a: "List[int]"):
    a = sorted(list(set(a)))
    base = 1
    base_n = 0
    for i in range(len(a)):
        temp = n_lcd(base, a[i])
        base_n = lcd(base, base_n, a[i], a[i]//2, M)
        base = temp

    if base > M:
        print(0)
    else:
        print((M-base_n)//base + 1)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, a)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

# lcd of a1*x1+n1 & a2*x2+n2
def lcd(a1, n1, a2, n2, M):
    if a1*a2 == 0:
        return 0
    x1 = 0
    x2 = 0
    k1 = n1
    k2 = n2
    while (k1 != k2)&(k1<M+2)&(k2<M+2):
        if k1 < k2:
            x1 += 1
            k1 = a1*x1 + n1
        else:
            x2 += 1
            k2 = a2*x2 + n2
        # print(k1, k2)
    return k1


def solve(N: int, M: int, a: "List[int]"):
    a = sorted(list(set(a)))
    base = 1
    base_n = 0
    for i in range(len(a)):
        temp = n_lcd(base, a[i])
        base_n = lcd(base, base_n, a[i], a[i]//2, M)
        base = temp

    if base > M:
        print(0)
    else:
        print((M-base_n)//base + 1)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, a)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

# lcd of a1*x1+n1 & a2*x2+n2
def lcd(a1, n1, a2, n2, M):
    if a1*a2 == 0:
        return 0
    x1 = 0
    x2 = 0
    k1 = n1
    k2 = n2
    while (k1 != k2)&(k1<M+2)&(k2<M+2):
        if k1 < k2:
            x1 += 1
            k1 = a1*x1 + n1
        else:
            x2 += 1
            k2 = a2*x2 + n2
        # print(k1, k2)
    return k1


def solve(N: int, M: int, a: "List[int]"):
    # a = sorted(list(set(a)))
    base = 1
    base_n = 0
    for i in range(len(a)):
        temp = n_lcd(base, a[i])
        base_n = lcd(base, base_n, a[i], a[i]//2, M)
        base = temp

    if base > M:
        print(0)
    else:
        print((M-base_n)//base + 1)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, a)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

# lcd of a1*x1+n1 & a2*x2+n2
def lcd(a1, n1, a2, n2):
    if a1*a2 == 0:
        return 0
    x1 = 0
    x2 = 0
    k1 = n1
    k2 = n2
    while (k1 != k2):
        if k1 < k2:
            x1 += 1
            k1 = a1*x1 + n1
        else:
            x2 += 1
            k2 = a2*x2 + n2
    return k1


def solve(N: int, M: int, a: "List[int]"):
    a = sorted(list(set(a)))
    base = 1
    base_n = 0
    for i in range(len(a)):
        temp = n_lcd(base, a[i])
        base = lcd(base, base_n, a[i], a[i]//2)
        base_n = temp

    if base > M:
        print(0)
    else:
        print((M-base)//base_n + 1)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, a)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import fractions
import math

n, m = map(int, input().split())
a = list(map(int, input().split()))
flag = [(i / 2) % 2 == 1 for i in a]

if sum(flag) % 2 == 1:
    ans = 0
else:
    # 最小公倍数求める
    lcm = a[0]
    for i in range(1, n):
        lcm = lcm * a[i] // fractions.gcd(lcm, a[i])

    ans = math.floor(m / lcm + 0.5)
print(ans)

Submission status: Wrong Answer

Solution code:
import fractions
import math

n, m = map(int, input().split())
a = list(map(int, input().split()))
flag = [(i / 2) % 2 == 0 for i in a]

if sum(flag) % 2 == 1:
    ans = 0
else:
    # 最小公倍数求める
    lcm = a[0]
    for i in range(1, n):
        lcm = lcm * a[i] // fractions.gcd(lcm, a[i])

    ans = math.floor(m / lcm + 0.5)
print(ans)

Submission status: Wrong Answer

Solution code:
import fractions
import math

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

# 最小公倍数求める
lcm = a[0]
for i in range(1, n):
    lcm = lcm * a[i] // fractions.gcd(lcm, a[i])

ans = math.floor(m / lcm + 0.5)
print(ans)

Submission status: Wrong Answer

Solution code:
import fractions

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

# 最小公倍数求める
lcm = a[0]
for i in range(1, n):
    lcm = lcm * a[i] // fractions.gcd(lcm, a[i])

if m < lcm:
    ans = 0
else:
    ans = round(m / lcm + 0.5)
print(ans)

Submission status: Wrong Answer

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

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

ans = 1 + (m - l//2)//l if m >= a//2 else 0
print(ans)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
import fractions


def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    mul = a[0]
    for i in range(1, n):
        mul = mul * a[i] // fractions.gcd(mul, a[i])
    if m >= mul // 2:
        ans = (m - mul // 2) // mul + 1
        print(int(ans))
    else:
        print(0)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import fractions


def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    mul = a[0]
    for i in range(1, n):
        mul = mul * a[i] // fractions.gcd(mul, a[i])
    ans = (m - mul // 2) // mul + 1
    print(int(ans))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import fractions


def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    mul = a[0]
    for i in range(1, n):
        mul = mul * a[i] // fractions.gcd(mul, a[i])
    if m > mul // 2:
        ans = (m - mul // 2) // mul + 1
        print(int(ans))
    else:
        print(0)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
import fractions
from functools import reduce
N,M=map(int,input().split())
P=list(map(int,input().split()))
Q=[0]*N
for i in range(N):
  j=0
  while True:
    j+=1
    if P[i] // (2**j) == P[i] /(2**j):
      Q[i] += 1
    else:
      j -= 1
      break
#print(Q)

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

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
  
if max(Q)==min(Q):
  T=lcm(*[i/2 for i in P])
  print(int((M/T+1)//2))
else:
  print(0)

Submission status: Wrong Answer

Solution code:
import math
import fractions
from functools import reduce
N,M=map(int,input().split())
P=list(map(int,input().split()))
Q=[0]*N
for i in range(N):
  j=0
  while True:
    j+=1
    if P[i] // (2**j) == P[i] /(2**j):
      Q[i] += 1
    else:
      j -= 1
      break
#print(Q)

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

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
  
if max(Q)==min(Q):
  T=lcm(*[i/2 for i in P])
  print((M/T+1)//2)
else:
  print(0)

Submission status: Wrong Answer

Solution code:
import math
N,M=map(int,input().split())
P=list(map(int,input().split()))
Q=max(P)
kouho = Q //2
count=0
while kouho < M :
  for i in range(N):
    if int (kouho / P[i] - 0.5) !=  (kouho / P[i] - 0.5):
      kouho += Q
      break
  else:
    count += 1
    if count ==1:
      a=kouho
      #print('a',a,count)
      kouho += Q
    elif count ==2:
      b=kouho
      #print('b',b,count)
      print(((M-a) // (b-a))+1)
      break
if count <= 1:
  print(count)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

N, M = rl()
A = rl()

import fractions
from functools import reduce

for i in range(len(A)):
    A[i] //= 2

def get_gcd(A):
    return reduce(fractions.gcd, A)

gcd = get_gcd(A)
d = 1
for a in set(A):
    d *= a
d //= gcd

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

Submission status: Wrong Answer

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

from math import floor
from fractions import gcd
from functools import reduce


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


b = [n // 2 for n in a]

odd_lcm = b[0]
for i in range(N - 1):
    odd_lcm = lcm(b[i], b[i + 1])
    if odd_lcm // b[i] % 2 == 0 or odd_lcm // b[i + 1] % 2 == 0:
        print(0)
        exit()

n = floor((M / odd_lcm - 1) / 2) + 1

print(n)

Submission status: Wrong Answer

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

from math import floor
from fractions import gcd
from functools import reduce


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


b = [n // 2 for n in a]
lcm_b = reduce(lcm, b)
n = floor((M / lcm_b - 1) / 2) + 1

print(n)

Submission status: Wrong Answer

Solution code:
judge=0
N,M = map(int,input().split())
import fractions
a = list(map(int, input().split()))
ans = a[0]
for i in range(1, N):
    ans = ans * a[i] // fractions.gcd(ans, a[i])
for j in a:
    if (ans//j)%2==0:
        judge=1
        sss=0
        break
if judge==0 and (M-ans)//2 <0:
    sss=0
elif judge==0 and (M-ans) >=0:
    sss=((M-ans//2)//ans)+1
print(sss)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
import fractions
a = list(map(int, input().split()))
ans = a[0]
for i in range(1, N):
    ans = ans * a[i] // fractions.gcd(ans, a[i])
if M-ans//2 <0:
    sss=0
else:
    sss=((M-ans//2)//ans)+1
print(sss)

Submission status: Wrong Answer

Solution code:
import sys

import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt
from collections import deque
from collections import Counter
from math import ceil
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#######ここから天ぷら########

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

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

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

n,m=map(int,input().split())
A=list(map(int,input().split()))
        
B=[i//2 for i in A]
p=qq(B)

print(m//p - m//(p*2))

Submission status: Wrong Answer

Solution code:
import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt
from collections import deque
from collections import Counter
from math import ceil
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#######ここから天ぷら########
@lru_cache(maxsize=10**10)
def gcd(a,b):
    if b==0: return a
    else:
        return gcd(b,a%b)
@lru_cache(maxsize=10**10)        
def lcm(a,b):
    return a*b//gcd(a,b)

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

def llcm(A):
    n=len(A)
    if n==1 : return A[0]
    elif n%2==1 : 
        A[1]=lcm(A[0],A[1])
        if max(A)>m :
            print(0)
            exit()
        return llcm(A[1:])
    else: 
        B=[lcm(A[i],A[i+1]) for i in range(0,n,2)]
        if max(B)>m:
            print(0)
            exit()
        return llcm(B)

B=[i//2 for i in A]
p=llcm(B)
if p>m: 
  print(0)
  exit()
print(m//p - m//(p*2))

Submission status: Wrong Answer

Solution code:
import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt
from collections import deque
from collections import Counter
from math import ceil
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#######ここから天ぷら########
@lru_cache(maxsize=10**10)
def gcd(a,b):
    if b==0: return a
    else:
        return gcd(b,a%b)
@lru_cache(maxsize=10**10)        
def lcm(a,b):
    return a*b//gcd(a,b)

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

def llcm(A):
    n=len(A)
    if n==1 : return A[0]
    elif n%2==1 : 
        A[1]=lcm(A[0],A[1])
        if max(A)>m :
            print(0)
            exit()
        return llcm(A[1:])
    else: 
        B=[lcm(A[i],A[i+1]) for i in range(0,n,2)]
        if max(B)>m:
            print(0)
            exit()
        return llcm(B)

B=[i//2 for i in A]
p=llcm(B)
print(m//p - m//(p*2))

Submission status: Wrong Answer

Solution code:
import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt
from collections import deque
from collections import Counter
from math import ceil
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#######ここから天ぷら########
@lru_cache(maxsize=10**10)
def gcd(a,b):
    if b==0: return a
    else:
        return gcd(b,a%b)
@lru_cache(maxsize=10**10)        
def lcm(a,b):
    return a*b//gcd(a,b)

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

def llcm(A):
    n=len(A)
    if n==1 : return A[0]
    if n%2==1 : 
        A[1]=lcm(A[0],A[1])
        return llcm(A[1:])
    else: 
        A=[lcm(A[i],A[i+1]) for i in range(0,n,2)]
        return llcm(A)

B=[i//2 for i in A]
p=llcm(B)
print(m//p - m//(p*2))

Submission status: Wrong Answer

Solution code:
from fractions import gcd
from functools import reduce

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

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

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

def semiCM(A,m):
    B=list(set(count2(a) for a in A))
    if len(B)!=1 or B[0]==0:
        return 0
    n=B[0]
    N=lcm(A)
    return int(m/N-0.5)+1


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

Submission status: Wrong Answer

Solution code:
import math

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

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

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

t = True
while(True):
    if(a[0]%2 == 0):
        for i in range(n):
            if(a[i]%2!=0):
                t = False
                break
            a[i] = a[i] // 2
        m = m // 2
    else:
        break

if(t):
    val = a[0]
    for i in range(1,n):
        val = (val*a[i]) // gcd(val, a[i])
    result = math.ceil((m//t)/(val*2))
    print(result)
else:
    print('0')

Submission status: Wrong Answer

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

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

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

t = True
while(True):
    if(a[0]%2 == 0):
        for i in range(n):
            if(a[i]%2!=0):
                t = False
                break
            a[i] = a[i] // 2
        m = m // 2
    else:
        break

if(t):
    val = a[0]
    for i in range(1,n):
        val = (val*a[i]) // gcd(val, a[i])
    result = (m//t)//val - (m//t)//(val*2)
    print(result)
else:
    print('0')

Submission status: Wrong Answer

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

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

t = 1
while(True):
    for i in range(n):
        a[i] = a[i] // 2
    tmp = False
    for i in range(n):
        if(a[i]%2 != 0):
            tmp = True
            break
    if(tmp):
        break
    t = t*2

val = a[0]
for i in range(1,n):
    val = (val*a[i]) // gcd(val, a[i])
result = (m//t)//val - (m//t)//(val*2)
print(result)

Submission status: Wrong Answer

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

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

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

val = a[0]
for i in range(1,n):
    val = (val*a[i]) // gcd(val, a[i])
result = (m//t)//val - (m//t)//(val*2)
print(result)

Submission status: Wrong Answer

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

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

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

val = a[0]
for i in range(1,n):
    val = (val*a[i]) // gcd(val, a[i])
result = m//val - m//(val*2)
print(result)

Submission status: Wrong Answer

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

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

def llcm(A):
    n=len(A)
    if n==1 : return A[0]
    if n%2==1 : 
        A[1]=lcm(A[0],A[1])
        return llcm(A[1:])
    else: 
        A=[lcm(A[i],A[i+1]) for i in range(0,n,2)]
        return llcm(A)

p=llcm(A)
print(max(-1, (m-p//2)//(p)) +1)

Submission status: Wrong Answer

Solution code:
from fractions import gcd
from functools import reduce

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

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

cnt = m//num
if num%2 == 1:
    if cnt%2 == 0:
        cnt //= 2
    else:
        cnt = cnt//2 + 1
print(cnt)

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

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


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


N, M = map(int, input().split())
A = list(map(int, input().split()))
x = A[0] // 2
for a in A[1:]:
    x = lcm(x, a // 2)
ans = M // x
print(ans - ans // 2)

Submission status: Wrong Answer

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

num1 = a[0]
num2 = 0
while num1 % 2 == 0:
    num1 //= 2
    num2 += 1
gc = 2 ** num2

b = []
for i in a:
    if i % gc != 0 or (i // gc) % 2 == 0:
        print(0)
        exit()
    else:
        b.append(i // gc)

from fractions import gcd
lcm = 1
for i in b:
    lcm = (lcm * i) // gcd(lcm, i)

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

Submission status: Wrong Answer

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

num1 = a[0]
num2 = 0
while num1 % 2 == 0:
    num1 //= 2
    num2 += 1
gc = 2 ** num2

b = []
for i in a:
    if i % gc != 0 or (i // gc) % 2 == 0:
        print(0)
        exit()
    else:
        b.append(i // gc)

from fractions import gcd
lcm = 1
for i in b:
    lcm = (lcm * i) // gcd(lcm, i)

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

Submission status: Wrong Answer

Solution code:
N,M = [int(v) for v in input().split()]
A = [int(v) for v in input().split()]

def gcm(a,b):
    if a < b: a,b= b,a
    while a % b != 0:
        a,b = b, a%b
    return b

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

A5 = [0.5*v for v in A]
lcm_num = A5[0]
for v in A5:
    lcm_num = lcm(lcm_num,v)
    if lcm_num > 1e9:
        print(0)
        exit()

for c in A5:
    if (lcm_num/c) % 2 == 0:
        print(0)
        exit()

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

Submission status: Wrong Answer

Solution code:
N,M = [int(v) for v in input().split()]
A = [int(v) for v in input().split()]

def gcm(a,b):
    if a < b: a,b= b,a
    while a % b != 0:
        a,b = b, a%b
    return b

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

A5 = [0.5*v for v in A]
lcm_num = A5[0]
for v in A5:
    lcm_num = lcm(lcm_num,v)
    if lcm_num > M:
        print(0)
        exit()

for c in A5:
    if (lcm_num/c) % 2 == 0:
        print(0)
        exit()

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

Submission status: Wrong Answer

Solution code:
N,M = [int(v) for v in input().split()]
A = [int(v) for v in input().split()]

def gcm(a,b):
    if a < b: a,b= b,a
    while a % b != 0:
        a,b = b, a%b
    return b

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

A5 = [0.5*v for v in A]
lcm_num = A5[0]
for v in A5:
    lcm_num = lcm(lcm_num,v)

for c in A5:
    if (lcm_num/c) % 2 == 0:
        print(0)
        exit()

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

Submission status: Wrong Answer

Solution code:
from fractions import gcd
n,m = map(int,input().split())
a = list(map(lambda x: int(x)//2,input().split()))
def lcm(x,y):
    return x*y//gcd(x,y)
def f(x):
    cnt = 0
    while x%2 == 0:
        x //= 2
        cnt += 1
r = set([f(i) for i in a])
if len(r) != 1:
    print(0)
    exit()
T = 1
for i in range(n):
    T = lcm(T,a[i])
ans=-(-(m//T)//2)
c=T
print(ans)

Submission status: Wrong Answer

Solution code:
from fractions import gcd
n,m = map(int,input().split())
a = list(map(lambda x: int(x)//2,input().split()))
def lcm(x,y):
    return x*y//gcd(x,y)
T = 1
for i in range(n):
    T = lcm(T,a[i])
ans=-(-(m//T)//2)
c=T
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = [int(v) for v in input().split()]
A = [int(v) for v in input().split()]

def gcm(a,b):
    if a < b: a,b= b,a
    while a % b != 0:
        a,b = b, a%b
    return b

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

A5 = [0.5*v for v in A]
lcm_num = A5[0]
for v in A5:
    lcm_num = lcm(lcm_num,v)

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

Submission status: Wrong Answer

Solution code:
from fractions import gcd
n, m = map(int, input().split())
aa = list(map(int, input().split()))
lcm = 1
for a in aa:
    lcm = a * lcm // gcd(a, lcm)
tmp = lcm // 2
print((m // tmp + 1) // 2)

Submission status: Wrong Answer

Solution code:
from functools import reduce
from fractions import gcd

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

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

n = reduce(lcm, [v // 2 for v in A])
print(-(-(M // n) // 2))

Submission status: Wrong Answer

Solution code:
import fractions

# least common multiple
def lcm(a,b):
  f = fractions.gcd(a,b)
  return a*b // f

N,m = list(map(int, input().split()))
A = list(map(int,input().split()))
l = A[0]

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

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

  return res

Submission status: Wrong Answer

Solution code:
import fractions

# least common multiple
def lcm(a,b):
  f = fractions.gcd(a,b)
  return a*b // f

N,m = list(map(int, input().split()))
A = list(map(int,input().split()))
l = A[0]

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

def F(x):
  print(x)
  res = 0
  while x%2==0:
    x //= 2
    res += 1

  return res

t = F(A[0])
for i in range(N):
  if F(A[i]) != t:
    print(0)
    exit(0)
  A[i] >>= t # a[i] /= 2^t
m >>= t

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

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