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 sys
import numpy as np
from fractions import gcd
from functools import reduce

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N, M = rl()
A = np.array(rl())
B = A // 2

def merge(a, b):
    g = gcd(a, b)
    a //= g; b //= g
    if a%2 == 0 or b%2 == 0:
        return 0
    n = g * a * b
    if n > 10 ** 9:
        return 0
    return n

x = reduce(merge, B)
if x == 0:
    answer = 0
else:
    answer = M // x - M // (2*x)

print(answer)

Submission status: Accepted

Solution code:
import sys

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 LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def gcd(x,y):
    while y:x,y=y,x%y
    return x

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

def main():
    n,m=MI()
    aa=LI()
    aa=[a>>1 for a in aa]
    l=1
    for a in aa:l=lcm(l,a)
    for a in aa:
        if l//a%2==0:
            print(0)
            exit()
    print((m//l+1)//2)

main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
A = list(map(int,input().split()))

# import numpy as np

# def gcd(x, y):
#     while x != 0 and y != 0:
#         x, y = max(x, y), min(x, y)
#         x %= y
#     return y

from fractions import gcd

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

import sys

a = 0

B = [0] * n
C = A[:]

for i in range(n):
    while A[i] % 2 == 0:
        A[i] //= 2
        B[i] += 1

if len(set(B)) != 1:
    print("0")
else:
    for i in range(n):
        C[i] //= 2
    A = C
    b = A[0]
    for i in range(1,n):
        b = lcm(A[i], b)
        if b > m:
            print(0)
            sys.exit()
        # b = np.lcm(A[i],b)
    # print("b", b)

    # b=np.lcm.reduce(A)

    ans = (m//b + 1) // 2
    # if (m//(b*2))*(b*2)+b<=m:
    #     ans += 1
    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)

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

def cnt_div_2(x):
    cnt = 0
    while x > 0:
        if x % 2 == 0:
            x //= 2
            cnt += 1
        else:
            break
    return cnt

def main():
    N, M = map(int, input().split())
    A = list(set(map(int, input().split())))
    cnt_2 = cnt_div_2(A[0])
    for a in A:
        if cnt_div_2(a) != cnt_2:
            print(0)
            exit()


    common = lcm_list(A)
    max_A = max(A)
    cnt = M // common
    if ((2 * cnt + 1) * common) // 2 <= M:
        print(cnt + 1)
    else:
        print(cnt)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from fractions import gcd


def cntTwo(n):
    i = 0
    while n % 2 == 0:
        i += 1
        n //= 2
    return i


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

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

c = 1
numTwo = cntTwo(B[0])
for b in B:
    if cntTwo(b) != numTwo:
        print(0)
        exit()
    c = b * c // gcd(c, b)

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

Submission status: Accepted

Solution code:
from fractions import gcd

lcm = lambda a, b: a * b // gcd(a, b)

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

Y = A[0]
for a in A[1:]:
    Y = lcm(Y, a)
    if Y > 2 * M:
        print(0)
        quit()

print(M // (Y // 2) - (M // Y) if all((Y // a) % 2 for a in A) else 0)

Submission status: Accepted

Solution code:
import sys
from functools import reduce

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

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

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

n, m, *a = map(int, sys.stdin.read().split())

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

    cnt = cnt_2(a[0])
    for i in range(1, n):
        if cnt_2(a[i]) != cnt:
            return 0

    l = reduce(lcm, a, a[0])
    
    return m // l - m // (l * 2)

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

Submission status: Accepted

Solution code:
import sys
from functools import reduce

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

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

n, m, *a = map(int, sys.stdin.read().split())

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

    res = 1
    while True:
        oe = a[0] & 1
        if oe == 0:
            for i in range(n):
                if a[i] & 1 == 1:
                    return 0
                a[i] //= 2
            res *= 2
        else:
            for i in range(n):
                if a[i] & 1 == 0:
                    return 0
            break
        
    l = reduce(lcm, a, a[0]) * res
    
    return m // l - m // (l * 2)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
from fractions import gcd
from functools import reduce
def lcm(a,b):
    return a//gcd(a,b)*b

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

    l=reduce(lcm,A)
    # A の要素の 2 で割り切れる回数は等しくなければならない
    k=0
    while(l%(1<<(k+1))==0): k+=1
    for a in A:
        if(a%(1<<k)):
            print(0)
            return

    print((m+l)//(2*l))
resolve()

Submission status: Accepted

Solution code:
import sys
import fractions
import numpy as np
x,y = map(int,input().split())
A = list(map(int,input().split()))
B = [0]*len(A)
for i in range(x-1):
	if format(A[i], 'b')[::-1].find('1') != format(A[i+1], 'b')[::-1].find('1'):
		print(0)
		sys.exit()
for i in range(x):
    B[i] = A[i]//2

def lcm(h, g):
    return (h * g) // fractions.gcd(h, g)
for i in range(1,len(B)):
    B[i]=lcm(B[i-1], B[i])

if int(B[x-1])>y:
    print(0)
else:
  print((y-int(B[x-1]))//(2*int(B[x-1]))+1)

Submission status: Accepted

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

import sys
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

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

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

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

for a in A:
    if l // a % 2 != 1:
        print(0)
        exit()
ans = M*2 // l + 1
print(ans // 2)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import fractions
from functools import reduce
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

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

def solve(N: int, M: int, a: "List[int]"):
    # 2でわれる回数が一緒じゃないとダメ
    b = a[0]
    count = 0

    while b%2 == 0:
        b //= 2
        count += 1

    for aa in a[1:]:
        tmp_count = 0

        while aa%2 == 0:
            aa //= 2
            tmp_count += 1
        
        if tmp_count == count:
            continue
        else:
            print(0)
            return
    lcm = lcm_list(a)
    print((M-lcm//2)//lcm + 1)
    return

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: Accepted

Solution code:
import sys
import itertools
from functools import reduce
import math
import fractions
#import numpy as np


def calc_double(n):
    return n//2

def calc_num(n):
    c=0
    while n%2==0: #evenなら
        n=n//2
        c+=1
    return c


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

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


def resolve():
    input = sys.stdin.readline
    N,M=map(int,input().rstrip().split())
    A=list(map(int,input().rstrip().split()))
    #AA=[0 for i in range(N)]    
    AA=list(map(calc_double,A))

    calAA=list(map(calc_num,AA))
    if all([True if calAA[0]==calAA[i] else False for i in range(N)])==False:
        print(0)
        return

    
    """
    for i in range(N):
        buf=A[i]//2
        if buf%2==0:
            print("0")
            return
        AA[i]=buf
    """

    a=lcm_list(AA)
    

    odd=M//a
    count=(odd+1)//2

    print(count)

    

from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """2 50
6 10"""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """3 100
14 22 40"""
        output = """0"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """5 1000000000
6 6 2 6 2"""
        output = """166666667"""
        self.assertIO(input, output)

if __name__ == "__main__":
    #unittest.main()
    resolve()

Submission status: Accepted

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

    div2cnt = 0
    a = A[0]
    while a % 2 == 0:
        a //= 2
        div2cnt += 1

    lcmval = A[0]//2
    for i in range(1, N):
        if A[i] % (2 ** (div2cnt+1)) == 0 or A[i] % (2 ** div2cnt) != 0:
            print(0)
            exit(0)
        
        lcmval = lcm(lcmval, A[i]//2)
        if lcmval > M:
            print(0)
            exit(0)
    
    print(int((M-lcmval)//(lcmval* 2)+ 1))

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

if __name__ == '__main__':
    solve()

Submission status: Accepted

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

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

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

b = f(a[0])
for i in a:
    if f(i) != b:
        print(0)
        exit()

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

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

Submission status: Accepted

Solution code:
import fractions
from functools import reduce
n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):
    a[i]=a[i]//2
def lcm_base(x,y):
    return (x*y)//fractions.gcd(x,y)
def lcm_list(numbers):
    return reduce(lcm_base,numbers,1)
f2=lcm_list(a)

ans=0
for i in range(n):
    if f2//a[i]%2!=1:
        print(ans)
        break
else:
    ans=m//f2
    print((ans+1)//2)

Submission status: Accepted

Solution code:
from functools import reduce
def gcd(a, b):
    while b: a, b = b, a % b
    return abs(a)
def lcm(a, b):
    return a*b//gcd(a, b)
N, M = map(int, input().split())
A = [int(a)//2 for a in input().split()]
B = [a & -a for a in A]
if min(B) != max(B):
    print(0)
else:
    l = reduce(lcm, A)
    print(M // l - M // l // 2)

Submission status: Accepted

Solution code:
import sys
from fractions import gcd
from operator import mul
from functools import reduce
inputs = sys.stdin.readlines()

n, m = map(int, inputs[0].split())
A = list(map(int, inputs[1].split()))
g = reduce(gcd, A)
if all((a // g) % 2 for a in A):
    print(round((m+1) / reduce(lambda x, y: x*y // gcd(x, y), A)))
else:
    print(0)

Submission status: Accepted

Solution code:
import sys

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

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

GCD = 1
t = a[0]
cond = 0
while t%2 == 0:
	t //= 2
	cond += 1
	
mod = 2**cond
for i in range(len(a)):
	t = a[i]
	t_div, t_mod = divmod(t,mod)
	if t_div == 0 or t_mod > 0:
		print(0)
		sys.exit()
	if t_div % 2 == 0:
		print(0)
		sys.exit()

	GCD = GCD*a[i] // gcd(GCD,a[i])
	
A = (2*m) // GCD
if A%2 == 1:
	A+=1

print(A//2)

Submission status: Accepted

Solution code:
import fractions
from functools import reduce
import sys
n, m = map(int, input().split())
a = [int(i)//2 for i in input().split()]
a = list(set(a))
flg = -1
for i in a:
    if i%2==0 and flg!=1:
        flg = 0
    elif i%2==1 and flg!=0:
        flg = 1
    else:
        print(0)
        sys.exit(0)
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

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

l = lcm(a)
for i in a:
    if (l//i)%2==0:
        print(0)
        sys.exit(0)
print((m+l)//(l*2))

Submission status: Accepted

Solution code:
import fractions
n,m = map(int,input().split())
l = input().split()
lcm = 1
sum = 0
for i in range(len(l)):
    lcm = (int(l[i]) * lcm) // fractions.gcd(int(l[i]), lcm)
for i in range(len(l)):
    if (lcm // int(l[i])) % 2 == 1:
        sum += 1
if sum == len(l):
    x = m // (int(lcm) // 2)
    y = m // lcm
    print(int(x - y))
else:
    print(0)

Submission status: Accepted

Solution code:
from fractions import gcd

def check(n):
   count=0
   while n%2==0:
      n/=2
      count+=1
   return count
   
N,M=map(int,input().split())
A=list(map(int,input().split()))

#すべてのiについてa_iを２で割れる回数が同じであるか
a_0=A[0]
a_0_count=check(a_0)
flag=True
for i in range(1,N):
   if check(A[i])!=a_0_count:
      flag=False
      break

if flag==False:
   print(0)
else:
   ans=A[0]//2
   for i in range(1,N):
      ans=(ans*A[i]//2)//gcd(ans,A[i]//2)

   left=0
   right=10**9
   while left<right-1:
      mid=(left+right)//2
      mid_2=2*mid-1
      if ans*mid_2<=M:
         left=mid
      else:
         right=mid
      
   print(left)

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 div2(x):
    c = 0
    while x%2==0:
        x //= 2
        c+=1
    return c

def test():
    N, M = map(int, input().split())
    a = list(map(int, input().split()))
    for i in range(N):
        if a[i]%2 == 1:
            return 0
        a[i] //= 2

    t = div2(a[0])
    for i in range(N):
        if div2(a[i]) != t:
            return 0
        a[i] >>= t
    M >>= t

    L = a[0]
    for i in range(1, N):
        L = lcm(L, a[i])
        if L > M:
            return 0

    ans = (M-L)//(2*L)+1
    return ans

print(test())

Submission status: Accepted

Solution code:
def main():
    """"ここに今までのコード"""
    import sys
    input = sys.stdin.readline
    n,m=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()
    if n==1:
        ans=(m//(A[0]//2)+1)//2
        print(int(ans))
        exit()
    from fractions import gcd
    kou=A[0]*A[1]//gcd(A[0],A[1])
    for a in A:
        kou=a*kou//gcd(a,kou)
        if (kou//a)%2==0:
            print(0)
            exit()
    kou//=2
    #print(kou)
    ans=(m//kou+1)//2
    print(int(ans))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
from fractions import gcd
from functools import reduce
from math import ceil, floor

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

def lcm_list(nums):
    return reduce(lcm, nums)

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

# X = lcm_list(A)
X = A[0]
for i in range(1, N):
    X = lcm(X, A[i])
T = X
cnt = 0
while X % 2 == 0:
    cnt += 1
    X //= 2
# print()
for i in range(N):
    if A[i] % 2**cnt != 0:
        print(0)
        exit()
t_ans = T // 2
if (M // t_ans) % 2 == 0:
    print((M//t_ans) // 2)
else:
    print(((M//t_ans) + 1) // 2)

Submission status: Accepted

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

from fractions import gcd
from functools import reduce

A = [x >> 1 for x in A]

def merge(a, b):
    g = gcd(a, b)
    a //= g
    b //= g
    if a % 2 == 0:
        return 0
    if b % 2 == 0:
        return 0
    n = a * b * g
    if n > 10 ** 9:
        return 0
    return n

x = reduce(merge, A)
if x == 0:
    ans = 0
else:
    ans = (M//x) - (M//(2*x))

print(ans)

Submission status: Accepted

Solution code:
def main():
    """"ここに今までのコード"""
    import sys
    input = sys.stdin.readline
    n,m=map(int,input().split())
    A=list(map(int,input().split()))
    #A.sort()
    if n==1:
        ans=(m//(A[0]//2)+1)//2
        print(int(ans))
        exit()
    from fractions import gcd
    kou=A[0]*A[1]//gcd(A[0],A[1])
    for a in A:
        kou=a*kou//gcd(a,kou)
        if (kou//a)%2==0:
            print(0)
            exit()
    kou//=2
    #print(kou)
    ans=(m//kou+1)//2
    print(int(ans))
if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

L=1
cur=-1
for i in range(len(A)):
  A[i]//=2
  p=A[i]
  c=0
  while p%2==0:
    p//=2
    c+=1
  if cur!=-1:
    if c!=cur:
      print(0)
      exit(0)
  cur=c
  L=lcd(L,A[i])

ans=M//(L*2)
ans+=(M%(L*2))//L
print(ans)

Submission status: Accepted

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

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

a = a // 2

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

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

l = lcm(*a)
exist = not 0 in ((l//a)%2)

if exist:
    print((M // l + 1 ) // 2)
else:
    print(0)

Submission status: Accepted

Solution code:
n,m=map(int, input().split())
an=[int(i) for i in input().split()]
import fractions
ans=an[0]
for i in range(1, n):
    ans = ans * an[i] // fractions.gcd(ans, an[i])

def count2(i):
    if i%2==0:
        c=0
        while i%2==0:
            i//=2
            c+=1
        return c
    else:
        return 0
    
c2=count2(ans)

for ak in an:
    if ak%(2**c2)==0:
        d=1
        pass
    else:
        d=0
        break

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

Submission status: Accepted

Solution code:
import fractions

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

exp2 = 0
temp = a[0]
while(True):
    if(temp%2 == 1):
        break
    exp2 += 1
    temp /= 2

a_div = []
for i in range(n):
    if(a[i] % 2**exp2 != 0):
        print(0)
        exit()
    if( a[i] % (2**(exp2+1)) == 0):
        print(0)
        exit()

    a_div.append(a[i]//(2**exp2))

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

base = lcm * 2**(exp2 -1)

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

Submission status: Accepted

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

import fractions
count=0
num=a[0]
#何個2の因数を持っているか調べる
while True:
    if num%2==0:
        count+=1
    else:
        break
    num//=2
    
for i in range(n):
    
    if a[i]%(2**count)!=0 or a[i]%(2**(count+1))==0:
        print(0)
        exit()
        

lcm=(a[0]//2)//fractions.gcd(a[0]//2,1)

for i in range(1,n):
    lcm=lcm*(a[i]//2)//fractions.gcd(lcm,a[i]//2)

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

Submission status: Accepted

Solution code:
def gcd(a, b):
  if b == 0:
    return a
  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()))

LCM = a[0]
c = 0
while a[0] % 2 == 0:
    c += 1
    a[0] = a[0] // 2
for i in range(1, n):
    LCM = lcm(LCM, a[i])
    k = 0
    while a[i] % 2 == 0:
        k += 1
        a[i] = a[i] // 2
    if k != c:
        print(0)
        exit()


x = (m * 2) // LCM
y = (m * 2) // (LCM * 2)

print(x - y)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

def solve(A, M):
    A = [x // 2 for x in A]
    g = reduce(gcd, A)
    lcm = 1
    if lcm == 0:
        print(A)
    for c in A:
        j = c // g
        if j % 2 == 0:
            return 0
        k = gcd(lcm, c)
        lcm *= c // k
    return (M // lcm + 1) // 2


def main():
    N, M = map(int, input().split())
    A = map(int, input().split())
    ans = solve(A, M)
    print(ans)


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)


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

base = B[0]

is_break = False
for b in B:
  if base % b == 0:
    if (base // b) % 2 == 0:
      is_break = True
      break
    
    continue
  
  new_base = lcm(base, b)
  if (new_base // base) % 2 == 0:
    is_break = True
    break
  
  base = new_base

if is_break:
  ans = 0
else:
  ans = M // base
  if ans%2 == 0:
    ans = ans // 2
  else:
    ans = (ans + 1) // 2


print(ans)

Submission status: Accepted

Solution code:
import fractions

a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
c=list(set(b))
d = [n//2 for n in c]
e=d[0]
for i in range(1, len(d)):
    e = e * d[i] // fractions.gcd(e, d[i])

odd=0
even=0
while odd != len(d) and even==0 or even==len(d):
    odd=0
    even=0
    for i in range(len(d)):
        if d[i]%2==0:
            d[i]=d[i]//2
            even+=1
        else:
            odd+=1

if even>0:
    print(0)            
else:
    if a[1]//e%2==0:
        print(a[1]//e//2)
    else:    
        print(a[1]//e//2 + 1)

Submission status: Accepted

Solution code:
n,m=map(int, input().split())
an=[int(i) for i in input().split()]
import fractions
ans=an[0]
for i in range(1, n):
    ans = ans * an[i] // fractions.gcd(ans, an[i])

def count2(i):
    if i%2==0:
        c=0
        while i%2==0:
            i//=2
            c+=1
        return c
    else:
        return 0
    
c2=count2(ans)

for ak in an:
    if ak%(2**c2)==0:
        d=1
        pass
    else:
        d=0
        break

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

Submission status: Accepted

Solution code:
import math
import fractions
from functools import reduce

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

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

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

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

l = lcm(*[a // 2 for a in A])
ans = math.floor((m + l) / (2*l))
if len(set([f(a) for a in A])) != 1:
    print(0)
else:
    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
p = p_dash = 1

def gcd(a, b):
    while(b != 0):
        a, b = b, a % b
    return a
    
def lcm(m,n):
    return (m*n)//gcd(m,n)

n,m=map(int,input().split())
A=list(map(int,input().split()))
a=A[0]
while a%2==0:
    count+=1; a//=2
for ai in A:
    p=lcm(p,ai)
    p_dash=lcm(p_dash,ai//2)
    tmp=0
    while ai%2==0:
        tmp+=1; ai//=2
    if tmp!=count:
        # print(213243)
        print(0)
        exit()

if p_dash>m:
    print(0)
else:
    print((m-p_dash)//p+1)
# print(p,p_dash)

Submission status: Accepted

Solution code:
import sys
from fractions import gcd


def cnt(x):
    a = 0
    while True:
        r = x % 2
        if r == 1:
            break
        else:
            a += 1
            x //= 2
    return a


read = sys.stdin.read
N, M, *a = map(int, read().split())
a = list(set(a))
b = [cnt(i) for i in a]
if len(set(b)) != 1:
    print(0)
    exit()

m = 2 * M

lcm = a[0]
for i in a:
    g = gcd(lcm, i)
    lcm = lcm * i // g
    if lcm > m:
        print(0)
        exit()

lcm //= 2
if M < lcm:
    print(0)
else:
    print((M - lcm) // (lcm * 2) + 1)

Submission status: Accepted

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

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

# c = [ i for i in a if i%2!=0 ]
# if len(c)!=0:
#     print(0)
#     exit()

b = list(map( lambda x : x//2 , a ))

# print(a)
# print(b)

# def factorization(n):
#     arr = []
#     temp = n
#     for i in range(2, int(-(-n**0.5//1))+1):
#         if temp%i==0:
#             cnt=0
#             while temp%i==0:
#                 cnt+=1
#                 temp //= i
#             arr.append([i, cnt])

#     if temp!=1:
#         arr.append([temp, 1])

#     if arr==[]:
#         arr.append([n, 1])

#     return arr

# chls = []
# for i in range(n):
#     f = factorization(a[i])
#     num2 = f[0][1]
#     chls.append(num2)
# if len(list(set(chls)))!=1:
#     print(0)
#     exit()

def count2inNumber(n):
    count = 0
    while n%2==0:
        n //= 2
        count += 1
    return count

chls = []
for i in range(n):
    count = count2inNumber(a[i])
    chls.append(count)
if len(list(set(chls)))!=1:
    print(0)
    exit()

from fractions import gcd
from functools import reduce

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

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

l = lcm_list(b)
# print(l)
# if l>m:
#     print(0)
#     exit()

pmax = (m-l) // (2*l)
# print(pmax)

ans = pmax + 1

print(ans)

Submission status: Accepted

Solution code:
#!python3

def iim():
    return map(int, input().rstrip().split())

from fractions import gcd

def nbit(x):
    if x == 0: return 0

    n = 0
    while x & 1 == 0:
        x >>= 1
        n += 1
    return n

def resolve():
    N, M = iim()
    a = list(iim())

    y = a[0]
    nb = nbit(y)
    for x in a[1:]:
        if nbit(x)  != nb:
            print(0)
            return

        y *= x // gcd(y, x)


    print((M+y//2)//y)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
# -*- encoding: utf-8 -*-
import sys
import re
import random
import numpy as np
from math import sqrt,log
from fractions import gcd  # python<=3.4
from collections import Counter, defaultdict


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

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

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


def extgcd(a, b, c=1, d=0, e=0, f=1):
    # sys.stderr.write("extgcd(%d, %d, %d, %d, %d, %d)\n" % (a,b,c,d,e,f))
    if b == 0:
        return (a, c, e)
    else:
        q = a // b
        r = a % b
        return extgcd(b, r, d, c-q*d, f, e-q*f)

# ll extgcd(ll a, ll b, ll &x, ll &y, ll c=1, ll d=0, ll e=0, ll f=1) {
#   if (b == 0) {
#     x = c; y = e;  // dot([c,d; e,f], [1;0])
#     return a;
#   }
#   ll q = a/b, r = a%b;
#   return extgcd(b, r, x, y, d, c-q*d, f, e-q*f);  // dot([c,d; e,f], [0,1; 1,-q])
# }

def f(u, v):
    a, b = u  # a + bk
    c, d = v  # c + dk
    # sys.stderr.write("F (%d %d) , (%d %d)\n" % (a,b,c,d))
    g = gcd(b, d)
    l = lcm(b, d)
    # ax + b = cy + d
    # ax - cy = (d - b)
    # -ax + cy = b - d
    r = a-c
    # sys.stderr.write("  - %dx + %dy = (%d - %d) = %d; g = %d\n" % (b,d, a,c, a-c, g))
    if r % g != 0:
        return (0, 0)
    # if (r % g) return P(0,0);
    mag = r / g
    # // ax - by = (d - c)
    # //if (a % mag || b % mag) return P(0,0);
    # // ax - by = gcd(a,b) は出る
    # // a /= mag; b /= mag;
    # r = g;

    _a, x, y = extgcd(-b, d)
    # if x < 0:
    #     x += lcd(a, b) / x
    # sys.stderr.write(" // x=%d, y=%d; av=%d\n" % (x,y,_a))

    x *= mag
    y *= mag
    w = a + b*x
    # sys.stderr.write("  w = %d+%dx%d = %d, l=%d\n" % (a,b,x, w, l))
    w %= l
    # sys.stderr.write("  => (%dk + %d)\n" % (l, w))
    if w <= 0:
        w += l

    return (w, l)


def solve(N, M, ar):
    a, b = 1, 1  # a + bk
    # u = (1, 1)
    for i in range(N):
        c, d = (ar[i]//2, ar[i])  # c + dk
        a, b = f((a,b), (c,d))
        if a == b == 0: # u == (0, 0):
            return 0

    # q, p = u
    if a == 0:
        a += b

    # sys.stderr.write("u = (%d %d); range [1, %d]\n" % (a, b, M))
    if a > M:
        return 0
    cnt = 1
    dif = M - a
    cnt += dif // b
    return int(cnt)


def main():
    N, M = read_ints()
    ar = read_ints()
    print(solve(N, M, ar))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import fractions

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

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
  
def kn(h):
  l=0
  while h%2==0:
    h=h//2
    l+=1
  return l
  
k=1
flag=kn(A[0]//2)
for a in A:
  a//=2
  k=lcm(k,a)
  if flag != kn(a):
    print(0);exit()
  
print(int(M//k//2+M//k%2))

Submission status: Accepted

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


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


# 整数 x の 2 の次数
def f(x):
    if x < 1:
        return 0
    i = 0
    while True:
        if x % (2 << i):
            break
        i += 1
    return i


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

    t = 1
    for a in A:
        if a & 1:
            print(0)
            return
        else:
            t = lcm(t, a//2)

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

    print(-(-(M//t)//2))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

    s = set()
    for i in a:
        cnt = 0
        while i % 2 == 0:
            i //= 2
            cnt += 1
        s.add(cnt)
    if len(s) == 1:
        for i in a[1:]:
            g = (g*i)//gcd(g, i)

        print((m//g+1)//2)
    else:
        print(0)


main()