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, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = 10**6#float('inf')
#mod = 10 ** 9 + 7 
mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

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

A = sorted([x//2 for x in a], reverse=True)

b = A[0]
cnt = 0
while b%2 == 0:
	b //= 2
	cnt += 1

for x in A:
	if x%pow(2, cnt) or (x//pow(2, cnt))%2 == 0:
		print(0)
		exit()

lcm = A[-1]
for x in A:
	lcm = lcm*x//gcd(lcm, x)

r = lcm//A[0]
n = M//A[0]

#2p+1が1<=2p+1<=n の範囲で rの倍数となるpの個数
if r%2 == 0:
	print(0)
else:
	print(n//r - n//(2*r))

Submission status: Accepted

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

import math

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

def pow2(x):
  ret = 0
  while x%2 == 0:
    ret += 1
    x //= 2
  return ret

P = []
for a in A:
  P.append(pow2(a))

if len(set(P)) != 1:
  print(0)
else:
  m = 1
  for a in A:
    m = lcm(m, a)
  print(-(-(M//m)//2))

Submission status: Accepted

Solution code:
from math import gcd
n,m=map(int,input().split())
a=list(map(int,input().split()))
a=list(set(a))
a=list(map(lambda x: x//2, a))

def lcm(q):
  x = q[0]
  for i in range(1, len(q)):
    x = (x * q[i]) // gcd(x, q[i])
  return x

lcma=lcm(a)
for i in range(len(a)):
  if (lcma//a[i])%2==0:
    print(0)
    exit()
temp=m//lcma
print(-(-temp//2))

Submission status: Accepted

Solution code:
from math import gcd
n,m=map(int,input().split())
a=list(map(int,input().split()))
a=list(set(a))
a=list(map(lambda x: x//2, a))

def lcm(q):
  x = q[0]
  for i in range(1, len(q)):
    x = (x * q[i]) // gcd(x, q[i])
  return x

lcma=lcm(a)
for i in range(len(a)):
  if (lcma//a[i])%2==0:
    print(0)
    exit()
temp=m//lcma
print(temp//2 if temp%2==0 else temp//2+1)

Submission status: Accepted

Solution code:
import math

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

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

for i in range(1,N):
    cnt = 0
    while A[i] % 2 == 0:
        A[i] //= 2
        cnt += 1
    if cnt != pow2:
        print(0)
        exit()

LCM = 2**max(0,pow2-1)
for i in range(N):
    LCM = LCM * A[i] // math.gcd(LCM,A[i])

ans = M // LCM
print((ans+1)//2)

Submission status: Accepted

Solution code:
import sys
import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

def Main():
    n, m = read_ints()
    a = read_int_list()
    a = [x // 2 for x in a]
    lcm = 1
    for x in a:
        lcm *= x // math.gcd(lcm, x)
    for x in a:
        if lcm // x % 2 == 0:
            print(0)
            exit()
    print(math.ceil((m // lcm) / 2))

if __name__ == '__main__':
    Main()

Submission status: Accepted

Solution code:
N,M=map(int, input().split())
from collections import defaultdict
A=list(map(int, input().split()))
B=[]
import math
def lcm(x, y):
    return (x * y) // math.gcd(x, y)
# a 偶数
twos=0
D=defaultdict(int)
for i in range(N):
    B.append(A[i]//2)
    a=A[i]
    now=0
    while a%2==0:
        a//=2
        now+=1
    D[now]+=1
    twos=max(twos, now)
if len(set(D.values()))!=1:
    print(0)
    exit()
now=1
for i in range(N):
    now=lcm(now, B[i])

# 1.5 * 3 2*5
from math import ceil

ans=M//(now)-M//(now*2)


print(ans)

Submission status: Accepted

Solution code:
N,M=map(int, input().split())
from collections import defaultdict
A=list(map(int, input().split()))
B=[]
import math
def lcm(x, y):
    return (x * y) // math.gcd(x, y)
# a 偶数
twos=0
D=defaultdict(int)
for i in range(N):
    B.append(A[i]//2)
    a=A[i]
    now=0
    while a%2==0:
        a//=2
        now+=1
    D[now]+=1
    twos=max(twos, now)
if len(set(D.values()))!=1:
    print(0)
    exit()
now=1
for i in range(N):
    now=lcm(now, B[i])

# 1.5 * 3 2*5
from math import ceil

ans=ceil(M//now/2)


print(ans)

Submission status: Accepted

Solution code:
N,M=map(int, input().split())
from collections import defaultdict
A=list(map(int, input().split()))
B=[]
import math
def lcm(x, y):
    return (x * y) // math.gcd(x, y)
# a 偶数
twos=0
D=defaultdict(int)
for i in range(N):
    B.append(A[i]//2)
    a=A[i]
    now=0
    while a%2==0:
        a//=2
        now+=1
    D[now]+=1
    twos=max(twos, now)
if len(set(D.values()))!=1:
    print(0)
    exit()
now=1
for i in range(N):
    now=lcm(now, B[i])

# 1.5 * 3 2*5
from math import ceil
ans=M//(now*pow(2,twos))+1
#res=now+now%(2**twos)
ans=ceil(M//now/2)
#if M-res>0:
#    ans-=int((M-res)//now/(2**twos))

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

def f(x):
    cnt = 0
    while x%2 == 0:
        cnt += 1
        x //= 2
    return cnt
def lcm(x,y):
    return x*y//math.gcd(x,y)

n,m = inpl()
a = inpl()
a = list(set(a))
c = list(set([f(x) for x in a]))
if len(c) != 1:
    print(0)
    quit()
c = c[0]
x = 1
for i in range(len(a)):
    x = lcm(a[i]//2, x)
# print(x)
print((m+x)//(2*x))

Submission status: Accepted

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

g=a[0]
lcm=a[0]

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

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

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

Submission status: Accepted

Solution code:
import sys
from math import gcd
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


N,M = MI()
A = LI()

x = sum(a % 2 == 0 for a in A)
if x != N:  # 奇数が含まれたら駄目
    print(0)
    exit()

r = 0
while A[0] % 2 == 0:
    r += 1
    A[0] //= 2
for i in range(1,N):
    if A[i] % (2**r) != 0 or (A[i]//(2**r)) % 2 == 0:  # 2で割り切れる回数が異なるものがあったら駄目
        print(0)
        exit()
    else:
        A[i] //= 2**r

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

a = (lcm*2**r)//2

# a の奇数倍で、M 以下である整数の個数が答え

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

Submission status: Accepted

Solution code:
from math import gcd

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = [a//2 for a in A]
LCM = 1
for i in range(N):
    LCM = LCM * B[i] // gcd(LCM, B[i])
for i in range(N):
    if LCM // B[i] % 2 == 0:
        print(0)
        exit()
print((M//LCM + 1)//2)

Submission status: Accepted

Solution code:
import sys
from math import gcd
sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


N,M = MI()
A = LI()

x = sum(a % 2 == 0 for a in A)
if x != N:
    print(0)
    exit()

r = 0
while A[0] % 2 == 0:
    r += 1
    A[0] //= 2
for i in range(1,N):
    if A[i] % (2**r) != 0 or (A[i]//(2**r)) % 2 == 0:
        print(0)
        exit()
    else:
        A[i] //= 2**r

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

a = (lcm*2**r)//2
print(((M//a)+1)//2)

Submission status: Accepted

Solution code:
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] // math.gcd(LCM, A[i])
 
for i in range(N):
  temp = LCM//A[i]
  if temp%2 == 0: #存在しない
    print(0)
    exit()
MIN = LCM//2
nokori = M - MIN
#print(MIN,nokori,LCM)
ans = nokori//LCM + 1
print(ans)

Submission status: Accepted

Solution code:
from math import gcd, ceil
N,M = map(int,input().split())
A = list(map(int,input().split()))
A = [a//2 for a in A]
B = 1

for a in A:
  B*=a//gcd(B,a)
  
for a in A:
  if B//a%2==0:
    print(0)
    exit()

print(ceil((M//B)/2))

Submission status: Accepted

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

def f( a_k ): # 2で割り切れる回数
    count = 0
    while a_k % 2 == 0:
        count += 1
        a_k = a_k // 2
    return count

b = []
f_0 = f( a[ 0 ] )
for a_k in a:
    f_k = f( a_k )
    if f_k != f_0:
        print( 0 )
        exit()
    b.append( a_k // pow( 2, f_k ) )

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

b_lcm = 1
for b_k in b:
    b_lcm = lcm( b_lcm, b_k )

a_lcm = b_lcm * pow( 2, f_0 )
# print( b_lcm, f_0, b )
print( ( m + a_lcm // 2 ) // a_lcm )

Submission status: Accepted

Solution code:
import sys
N,M = map(int,input().split())
A = list(map(int,input().split()))
a = []
for i in A:
  i = i//2
  a.append(i)
def gcd(p,q):
  p,q = max(p,q),min(p,q)
  while q!=0:
    p,q = q,p%q
  return p
def lcm(p,q):
  return(p*q//gcd(p,q))
def aaa(i):
  count = 0
  while i%2==0:
    i = i//2
    count+=1
  return count
max_num = a[0]
aa = aaa(a[0])
for i in a:
  max_num = lcm(i,max_num)
  if aa != aaa(i):
    print(0)
    sys.exit()
print(((M//max_num)+1)//2)

Submission status: Accepted

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

N,M = map(int,input().split())
a = list(map(lambda a: int(a)//2, input().split()))
g = lcm(*a)
if any([g // item % 2 == 0 for item in a]):
    print(0)
else:
    ans = M//g
    ans = max(math.ceil(ans/2),0)   
    print(ans)

Submission status: Accepted

Solution code:
# ABC150 D
from math import gcd

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

g=A[0]
check=g&-g
for a in A:
    if check!=a&-a:
        check=-1
        break
    g=g*a//gcd(a,g)
if check>=0:
    g//=2
    print((M//g+1)//2)
else:
    print(0)

Submission status: Accepted

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

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

"""
2X = ak * (2p+1)
基本的には最小公倍数/2を基本とし，これの奇数倍か．

X  = (ak//2) * (2p+1)
と書ける．第二項が奇数なので，各akが2で割り切れれう回数が同じでなければならない
a=[2,4]だと無理
"""
def main():
    from math import gcd
    N,M=MI()
    A=LI()
    
    def count(X):
        cnt=0
        while X%2==0:
            cnt+=1
            X=X//2
        return cnt
    
    C=count(A[0])
    for i in range(1,N):
        if count(A[i])!=C:
            print(0)
            exit()
            
    lca=1
    for i in range(N):
        g=gcd(lca,A[i])
        lca=(lca*A[i])//g
        
    lca2=lca//2
    ans=M//lca2 - M//lca
    
    print(ans)
    
            
    

main()

Submission status: Accepted

Solution code:
import math
from decimal import Decimal, ROUND_HALF_UP
def lcm(a):
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // math.gcd(x, a[i])
    return x
def gcd(a):
  temp = math.gcd(a[0], a[1])
  for i in a:
    temp = math.gcd(temp,  i)
  return temp
n,m = map(int, input().split(" "))
a = list(map(int, input().split(" ")))
zero = False
count = 0
#a = list(map(lambda x: x // 2, na))
mini = lcm(a)
if len(a) != 1:
  maxi = gcd(a)
else:
  maxi = a[0]
maxi2 = maxi
nibai = 1
while(True):
  if maxi2 % 2 == 0:
    nibai *= 2
    maxi2 //= 2
  else:
    break
for i in a:
  if i % (2 * nibai) == 0:
    zero = True
    break
#print(nibai, maxi, mini)
if not zero:
  t = Decimal(str((m * 2 // mini) / 2))
  #print(t)
  print(t.quantize(Decimal('0'), rounding=ROUND_HALF_UP))
else:
  print(0)

Submission status: Accepted

Solution code:
def abc150_d():
    n, m = (int(x) for x in input().split())
    A = [int(x) // 2 for x in input().split()]

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

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

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

    if valid: ans = (m // x + 1) // 2
    else: ans = 0
    print(ans)

if __name__ == '__main__':
    abc150_d()

Submission status: Accepted

Solution code:
import math
import collections
import sys

input = sys.stdin.readline
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]

n,m=MI()
A=LI()
def num2(x):
    ans=0
    while x%2==0:
        x=x//2
        ans+=1
    return ans
mod=2**(num2(A[0]))
for i in range(1,n):
    if A[i]%mod!=0:
        print(0)
        sys.exit()
    if A[i]%mod==0 and (A[i]//mod)%2==0:
        print(0)
        sys.exit()
#print(A)
for i in range(n):
    A[i]//=2
#print(A)

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

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

L=A[0]   
for i in range(1,n):
    L=lcm(L,A[i])
#print(L)
if L>m:
    an=0
else:
    an=int(((m/L)-1)/2)+1
print(an)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Wed Sep  9 14:33:00 2020

@author: liang
"""
from math import gcd

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

flag = False
res = 1
for a in A:
    a //= 2
    res *= a//gcd(res,a)
    if res > M:
        flag = True
        break
    #print(res)
"""
存在チェック
２で割り切れる個数同じ？
"""

for a in A:
    if int(res/a) == res/a:
        flag = True
        
if flag:
    ans = 0
    print(ans)
else:
    #ans = (M - res(A)//2)//res + 1
    #ans = (M-1)//res//2 + 1
    ans= (M//res + 1)//2
    print(ans)

Submission status: Accepted

Solution code:
import queue
import numpy as np
import math

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

lcm = a[0]

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

hasAns = True
for i in a:
    if (lcm // i) % 2 == 0:
        hasAns = False
        break

ans = 0

if hasAns:
    ans = ((M // lcm) + 1 )// 2

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

#素数リスト
def prime_list(n=10**6+1):
    res = []
    tmp = [1 for _ in range(n)]
    tmp[0] = 0
    tmp[1] = 0
    i = 2
    while i < len(tmp):
        j = i*2
        while tmp[i] == 1 and j < len(tmp):
            tmp[j] = 0
            j += i
        i += 1

    for i, j in enumerate(tmp):
        if j:
            res.append(i)

    return res
prime_number = prime_list()

def prime_fact(n):
    primes = []
    for i in prime_number:
        tmp = 0
        while n % i == 0:
            tmp += 1
            n //= i
        if tmp != 0:
            primes.append([i, tmp])
        if i * i > n:
            break

    if n != 1:
        primes.append([n, 1])
    return primes

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

so = defaultdict(int)

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

    primes = prime_fact(i)
    for k, v in primes:
        if k == 2:
            if len(two) != 0 and two[-1] != v:
                print(0)
                exit()
            two.append(v)
        so[k] = max(so[k], v)

tmp = 1
for i, j in so.items():
    tmp *= i ** j
    if tmp > 2 * m:
        print(0)
        exit()

tmp //= 2
# print(tmp)
ans = m // tmp

if ans % 2 == 0:
    ans //= 2
else:
    ans //=2
    ans += 1

print(ans)

Submission status: Accepted

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

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

def gcdN(a):
    x = a[0]
    for i in range(1, len(a)):
        x = gcd(x, a[i])
    return x

def lcmN(a):
    x = a[0]
    for i in range(1, len(a)):
        x = lcm(x, a[i])
    return x


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

g = gcdN(a)
for i in a:
    if (i//g) % 2 == 0:
        print(0)
        break
else:
    l = lcmN(a) 
    k = 2*m // l
    print((k+1)//2)

Submission status: Accepted

Solution code:
import math

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

if n==1:
  a1=a[0]//2
  ans_m=m//a1
  if ans_m==0:
    print(0)
  else:
    print((ans_m-1)//2+1)
  
else:
  x=a[0]
  ch=0
  ch1=0
  while x%2==0:
    x=x//2
    ch+=1
  dob=2**ch
  for i in a:
    if i%dob==0 and i%(dob*2)!=0:
      ch1+=1
  if ch1!=n:
    print(0)
  else:
    ans=a[0]//2
    for j in range(1,n):
      ans=(ans*(a[j]//2))//math.gcd(ans,a[j]//2)
    ans_m=m//ans
    if ans_m==0:
      print(0)
    else:
      print((ans_m-1)//2+1)

Submission status: Accepted

Solution code:
import sys
import functools
from math import gcd


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


def lcm(x):
    return functools.reduce(lcm2, x)


def resolve(in_):
    N, M = map(int, next(in_).split())
    A = tuple(map(lambda x: int(x) // 2, next(in_).split()))

    a0 = A[0]
    x = 0
    while True:
        a0, b = divmod(a0, 2)
        if b:
            break
        x += 1
    x = 2 ** x
    for a in A[1:]:
        d, m = divmod(a, x)
        if m != 0 or not d % 2:
            return 0 

    l = lcm(A)
    l2 = l + l

    answer = len(range(l, M + 1, l2))

    return answer


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


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):
    while b > 0:
        a, b = b, a % b
    return a


G = A[0]/2
for a in A[1:]:
    G *= (a/2)/gcd(G,a//2)
for a in A:
    if G % a == 0:
        print(0)
        exit()
print(int(M//G - M//G//2))

Submission status: Accepted

Solution code:
from math import gcd
import sys

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

lcm = 1
for a in A:
    gcd_ = gcd(lcm, a//2)
    lcm = lcm * (a // 2 // gcd_)
for a in A:
    if (lcm // (a // 2)) % 2 == 0:
        print(0)
        sys.exit()

print(M // lcm - M // (2 * lcm))

Submission status: Accepted

Solution code:
import math
from functools import reduce

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

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

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

LCM=lcm(*A)
for a in A:
  if LCM//a%2==0:
    print(0)
    break
else:
  print((M//LCM+1)//2)

Submission status: Accepted

Solution code:
from fractions import gcd
def lcm(p, q):
  return (p * q // int(gcd(p, q)))
N, M = map(int, input().split())
A = list(map(int,input().split()))
B = []
for i in range(N):
  b = 0
  while A[i] % 2 == 0:
    A[i] >>= 1
    b += 1
  B.append(b)
S = set(B)
if len(S) != 1:
  print(0)
else:
  P = 1
  for i in range(N):
    P = lcm(P, A[i])
  print((M // (2 ** (list(S)[0] - 1)) + P) // (2 * P))

Submission status: Accepted

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

import math
lcm = 1
for i in range(n):
    b = a[i]//2
    lcm = lcm*b //math.gcd(lcm,b)
if any(2*lcm//i % 2 == 0 for i in a):
    print(0)
else:
    print((m-lcm)//(2*lcm) + 1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal
from argparse import ArgumentParser

args=ArgumentParser()
args.add_argument('-loc', '--local', type=bool,default=False)
LOCAL=args.parse_args().local

def input(): 
    x=sys.stdin.readline(); 
    if x[-1]=="\n": 
        return x.rstrip() 
    return x
    
def printe(*x):_=print("## ",*x,file=sys.stderr) if LOCAL else 0
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f


def lcm(A,M,f=0):
    
    cur=A[0]
    for a in A[1:]:
        d=a//math.gcd(a,cur)
        cur=cur*d
        if cur>M:
            return -1
    
    for a in A:
        if cur//a%2==0:
            return -1
        

    return cur

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, M = map(int, input().split())
    A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    m1=lcm(tuple(a//2 for a in A),M,1)
    if m1==-1:
        print(0)
        return
    m2=lcm(A,M)

    printe(m1,m2)
    if m2==-1:
        print(1)
        return
    ans=1+(M-m1)//m2
    print(ans)
    


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from math import gcd

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

memo = {}

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

b = 1

for a in A:
    b = lcm(a//2, b)
    if b > M:
        break

if any([2 * b // a % 2 == 0 for a in A]):
    print(0)
else:
    ans = M // b
    print(ans - ans // 2)

Submission status: Accepted

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

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

x = 1
for i in range(n):
    b = a[i] // 2
    x = x * b // gcd(x, b)
if any(2 * x // y % 2 == 0 for y in a):
    print(0)
    quit()
print((m - x) // (2 * x) + 1)

Submission status: Accepted

Solution code:
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] // math.gcd(LCM, A[i])

for i in range(N):
  temp = LCM//A[i]
  if temp%2 == 0: #存在しない
    print(0)
    exit()
MIN = LCM//2
nokori = M - MIN
#print(MIN,nokori,LCM)
ans = nokori//LCM + 1
print(ans)

Submission status: Accepted

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


INF=10**20
def get_lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


def solve(N: int, M: int, A: "List[int]"):
    lcm = A[0]
    for i,a in enumerate(A[1:]):
        lcm = get_lcm(a,lcm)

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

    for i,a in enumerate(A):
        b = lcm // a
        if b % 2 == 0:
            print(0)
            exit()
        
    ans = math.floor(M/lcm+1/2) - math.ceil(1/lcm+1/2) + 1
    print(ans)

    
    
    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:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


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


def read_float():
    return float(buff_readline())


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


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


def read_str_n():
    return readline().strip().split()

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


def mt(f):
    import time

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

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

    return wrap


@mt
def slv(N, M, A):
    b_lcm = 1


    d2 = set()
    for a in A:
        b = a // 2
        b_lcm = b_lcm//math.gcd(b_lcm, b) * b
        for i in range(100000000):
            if a % 2 == 0:
                a //= 2
            else:
                d2.add(i)
                break

    return -(-(M // b_lcm)//2) if len(d2) == 1 else 0





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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

def n_2(n):
  c=0
  while n%2==0:
    c+=1
    n>>=1
  return (n,c)

N,M=map(int,input().split())
A=list(map(int,input().split()))
A[0],a=n_2(A[0])
p=False
for i in range(1,N):
  A[i],b=n_2(A[i])
  if a!=b:
    p=True
    break
if p:
  print(0)
  exit()
n=1
for _ in range(a-1):
  n*=2
l=n
for a in A:
  l=l*a//math.gcd(l,a)
ans=M//l-M//(2*l)
print(ans)

Submission status: Accepted

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

a=[int(x) for x in input().split()]

kaisuu=0

for i in a:
    zantei=0
    while True:
        if i%2==0:
            zantei+=1
            i//=2
        else:
            break
    if kaisuu==0:
        kaisuu=zantei
    else:
        if kaisuu!=zantei:
            print(0)
            exit()

sks=a[0]//2

import math

for i in range(1,len(a)):
    sks=sks*(a[i]//2)//(math.gcd(sks,a[i]//2))

ans=int(m/(2*sks)+(1/2))

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a = list(map(int, input().split()))
for k in range(N):
  a[k] //= 2

foo = 1
while a[0]%2 == 0:
  foo *= 2
  a[0] //= 2
for k in range(1, N):
  if a[k] % foo == 0 and a[k]%(2*foo) !=0:
    a[k] //= foo
    continue
  else:
    print(0)
    exit()
ans = 0

for odd in [3]:
  flag = False
  for k in range(N):
    if a[k]%odd == 0:
      a[k] //= odd
      flag = True
  if flag:
    foo *= odd
 
 
import math

lcm = a.pop()
for k in range(1, N):
  b = a.pop()
  lcm = lcm * b // math.gcd(lcm, b)
  if lcm* foo > M:
    print(0)
    exit()
lcm *= foo
ans = int((M / lcm -1)//2 + 1)
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a = list(map(int, input().split()))
for k in range(N):
  a[k] //= 2

foo = 1
while a[0]%2 == 0:
  foo *= 2
  a[0] //= 2
for k in range(1, N):
  if a[k] % foo == 0 and a[k]%(2*foo) !=0:
    a[k] //= foo
    continue
  else:
    print(0)
    exit()
ans = 0

for odd in [3, 5, 7]:
  flag = False
  for k in range(N):
    if a[k]%odd == 0:
      a[k] //= odd
      flag = True
  if flag:
    foo *= odd
 
 
import math

lcm = a.pop()
for k in range(1, N):
  b = a.pop()
  lcm = lcm * b // math.gcd(lcm, b)
  if lcm* foo > M:
    print(0)
    exit()
lcm *= foo
ans = int((M / lcm -1)//2 + 1)
print(ans)