Problem:


Score : 400 points

Problem Statement

Given are a sequence A= {a_1,a_2,......a_N} of N positive even numbers, and an integer M.

Let a semi-common multiple of A be a positive integer X that satisfies the following condition for every k (1 \leq k \leq N):

There exists a non-negative integer p such that X= a_k \times (p+0.5).

Find the number of semi-common multiples of A among the integers between 1 and M (inclusive).

Constraints

1 \leq N \leq 10^5

1 \leq M \leq 10^9

2 \leq a_i \leq 10^9

a_i is an even number.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
a_1 a_2 ... a_N

Output

Print the number of semi-common multiples of A among the integers between 1 and M (inclusive).

Sample Input 1

2 50
6 10

Sample Output 1

2

15 = 6  \times 2.5 

15 = 10 \times 1.5 

45 = 6  \times 7.5 

45 = 10 \times 4.5 

Thus, 15 and 45 are semi-common multiples of A. There are no other semi-common multiples of A between 1 and 50, so the answer is 2.

Sample Input 2

3 100
14 22 40

Sample Output 2

0

The answer can be 0.

Sample Input 3

5 1000000000
6 6 2 6 2

Sample Output 3

166666667



Sample input:
2 50
6 10


Sample output:
2

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

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

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

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

Submission status: Accepted

Solution code:
import numpy as np
import copy
n,m = map(int,input().split())
A = np.array([int(i) for i in input().split()])//2
lcm_ = 1
def gcd(a,b):
    while b:
        a,b = b,a%b
    return a
def lcm(a,b):
    return a*b//gcd(a,b)

for i in A:
    lcm_ = lcm(lcm_,i)
c = 0
lcm_2 = copy.deepcopy(lcm_)
for _ in range(30):
    if lcm_2 % 2 == 0:
        c += 1
        lcm_2 = lcm_2//2
if np.all(A%(2**c) == 0):
    c = m//lcm_
    print(c//2 + c%2)
else:
    print(0)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

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

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


def applied_lcm(x, y):
    g = gcd(x, y)
    x //= g
    y //= g
    if x % 2 == 0 or y % 2 == 0:
        return 0
    n = x * y * g
    if n >> 10 ** 9:
        return 0

    return n


p = reduce(applied_lcm, A)
if p == 0:
    ans = 0
else:
    ans = (M // p) - (M // (p + p))
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = set(i//2 for i in map(int, input().split()))
B = []
for i in A:
	B = B + [0]
	while i % 2 == 0:
		i //= 2
		B[-1] += 1
if len(set(B)) == 1:
	m = max(A)
	A.remove(m)
	base = 0
	for i in range(m,M+1,2*m):
		semi = True
		for j in A:
			if i % j != 0 or (i // j) % 2 == 0:
				semi = False
				break
		if semi:
			base = i
			break
	if base == 0:
		print(0)
	else:
		print(((M // base) + 1)//2)
else:
	print(0)

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 = [i >> 1 for i in a]

def applied_lcm(x, y):
    g = gcd(x, y)
    x //= g
    y //= g
    if x %2 == 0:
        return 0
    if y %2 == 0:
        return 0
    n = x * y * g
    if n >> 10**9:
        return 0

    return n

p = reduce(applied_lcm, a)
if p == 0:
    ans = 0
else:
    ans = (m//p) - (m//(p+p))
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
n,m=map(int,input().split())
a=[i//2 for i in set(list(map(int,input().split())))]
b=[]
for i in a:
    c=i
    p=0
    while c%2==0:
        c//=2
        p+=1
    b.append(p)
l=1
if len(set(b))==1:
    for i in a:
        l=l*i//gcd(i,l)
        if m<l:
            print(0)
            break
    else:
        print((m//l+1)//2)
else:
    print(0)

Submission status: Accepted

Solution code:
from sys import stdin
import numpy as np
from fractions import gcd


# noinspection PyShadowingBuiltinsInspection

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

def main():
    N, M = [int(x) for x in input().split()]
    a = sorted(list({int(x) for x in input().split()}), reverse=True)
    x = a[0]
    p2 = 1
    while x % 2 == 0:
        p2 *= 2
        x //= 2
    flag = False
    y = 1 # a//2 の最小公倍数
    for i in range(len(a)):
        if a[i] % p2 != 0 or (a[i] // p2) % 2 == 0:
            flag = True
            break
        a[i] //= 2
        y = lcm(a[i], y)
    if flag:
        return 0
    z = M // y
    return z // 2 if z % 2 == 0 else z // 2 + 1
    # b = [a[0]]
    # for i in range(1, len(a)):
    #     flag = False
    #     for x in b:
    #         if x % a[i] == 0:
    #             flag = True
    #             break
    #     if not flag:
    #         b.append(a[i])
    # # print(b)
    # y = 1
    # for x in b:
    #     # print(b)
    #     y *= x
    # z = M // y
    # # print(y, z*y)
    # ret = z // 2 if z % 2 == 0 else z // 2 + 1
    # # print(ret)
    #
    # return ret


if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
from fractions import gcd
def lcm(arr, n):
    ans = arr[0]
    for i in range(1, n):
        ans = ((arr[i] * ans) // gcd(arr[i], ans))
    return ans

n, m = [int(x) for x in raw_input().split()]
arr = [int(x) for x in raw_input().split()]
v = []
for x in arr:
    y = x
    cnt = 0
    while y % 2 == 0:
        y = y // 2
        cnt += 1
    v.append(cnt)
mx = max(v)
mn = min(v)
if mx != mn:
    print 0
else:
    strt = lcm(arr, n) // 2
    if strt > m:
        print 0
    else:
        print 1 + (m - strt) // (2 * strt)

Submission status: Accepted

Solution code:
from fractions import gcd
def lcm(arr, n):
    ans = arr[0]
    for i in range(1, n):
        ans = ((arr[i] * ans) // gcd(arr[i], ans))
    return int(ans)

n, m = [int(x) for x in raw_input().split()]
arr = [int(x) for x in raw_input().split()]
v = []
for x in arr:
    y = x
    cnt = 0
    while y % 2 == 0:
        y = y // 2
        cnt += 1
    v.append(cnt)
mx = max(v)
mn = min(v)
if mx != mn:
    print(0)
else:
    strt = lcm(arr, n) // 2
    if strt > m:
        print(0)
    else:
        print(int(1 + int((m - strt)) // int((2 * strt))))

Submission status: Accepted

Solution code:
import fractions
from functools import reduce
 
def gcd(*numbers):
    return reduce(fractions.gcd, numbers)
 
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)
 
def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
    
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
 
 
N, M = map(int,input().split())
A = list(map(int,input().split()))
 
#if gcd(*A) % 2 != 0:
    #print(0)
    #exit(0)
 
#sisu_2 = factorization(A[0])[0][1] 
 
#lcm_a = lcm(*A)
#lcm_a_half = lcm_a // 2
lcm_a = lcm(*A) // 2
 
l = []
sisu_a0 = 0
flag = 0
for i in range(N):
    sisu = 0
    while A[i]%2==0:
        A[i] //= 2
        sisu += 1
    
    if sisu_a0==0:
        sisu_a0 = sisu
    else:
        if sisu_a0!=sisu:
            flag = 1
#if (lcm_a % (2**sisu_2) == 0) or lcm_a > M:
#if factorization(lcm_a)[0][1] != sisu_2 or lcm_a_half > M:
if flag == 1 or lcm_a > M:
    print(0)
    exit(0)
else:
    print(int((M-lcm_a) // (lcm_a*2) + 1))

Submission status: Accepted

Solution code:
import fractions
from functools import reduce

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

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

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
    
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


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

#if gcd(*A) % 2 != 0:
    #print(0)
    #exit(0)

#sisu_2 = factorization(A[0])[0][1] 
sisu_2 = min([factorization(A[i])[0][1] for i in range(min(1000,N))])

#lcm_a = lcm(*A)
#lcm_a_half = lcm_a // 2
lcm_a = lcm(*A) // 2
'''
l = []
sisu_a0 = 0
for i in range(N):
    sisu = 0
    while A[i]%2==0:
        A[i] //= 2
        sisu += 1
    
    if sisu_a0==0:
        sisu_a0 = sisu
    else:
        if sisu_a0!=sisu:
            print(0)
            exit()
'''
if (lcm_a % (2**sisu_2) == 0) or lcm_a > M:
#factorization(lcm_a)[0][1] != sisu_2 or lcm_a_half > M:
#if lcm_a > M:
    print(0)
    exit(0)
else:
    print(int((M-lcm_a) // (lcm_a*2) + 1))

Submission status: Accepted

Solution code:
import fractions
from functools import reduce

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

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

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
    
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


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

#if gcd(*A) % 2 != 0:
    #print(0)
    #exit(0)

#sisu_2 = factorization(A[0])[0][1] 
sisu_2 = min([factorization(A[i])[0][1] for i in range(min(100,N))])

#lcm_a = lcm(*A)
#lcm_a_half = lcm_a // 2
lcm_a = lcm(*A) // 2
'''
l = []
sisu_a0 = 0
for i in range(N):
    sisu = 0
    while A[i]%2==0:
        A[i] //= 2
        sisu += 1
    
    if sisu_a0==0:
        sisu_a0 = sisu
    else:
        if sisu_a0!=sisu:
            print(0)
            exit()
'''
if (lcm_a % (2**sisu_2) == 0) or lcm_a > M:
#factorization(lcm_a)[0][1] != sisu_2 or lcm_a_half > M:
#if lcm_a > M:
    print(0)
    exit(0)
else:
    print(int((M-lcm_a) // (lcm_a*2) + 1))

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

def gcd_list(L):
    return reduce(gcd,L)

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

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

N,M=map(int,input().split())
a=list(map(int,input().split()))
a=list(map(lambda x:x//2,a))
ans=0

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

dev_pre=dev_cnt(a[0])

for i in range(1,N):
    if dev_pre!=dev_cnt(a[i]):
        print(0)
        exit()
    dev_pre=dev_cnt(a[i])

dev_num=dev_cnt(a[0])

a=list(map(lambda x:x//2**dev_num,a))
lcm_a=lcm_list(a)

i=1
X=lcm_a*i

ans=M//(2**dev_num)
ans=ans//lcm_a+1
ans=ans//2

print(ans)

Submission status: Accepted

Solution code:
import fractions
from functools import reduce

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

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

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
    
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


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

#if gcd(*A) % 2 != 0:
    #print(0)
    #exit(0)

#sisu_2 = factorization(A[0])[0][1] 

#lcm_a = lcm(*A)
#lcm_a_half = lcm_a // 2
lcm_a = lcm(*A) // 2

l = []
sisu_a0 = 0
for i in range(N):
    sisu = 0
    while A[i]%2==0:
        A[i] //= 2
        sisu += 1
    
    if sisu_a0==0:
        sisu_a0 = sisu
    else:
        if sisu_a0!=sisu:
            print(0)
            exit()
#if (lcm_a % (2**sisu_2) == 0) or lcm_a > M:
#if factorization(lcm_a)[0][1] != sisu_2 or lcm_a_half > M:
if lcm_a > M:
    print(0)
    exit(0)
else:
    print(int((M-lcm_a) // (lcm_a*2) + 1))

Submission status: Accepted

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

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

n,m = map(int, input().split())
a = list(map(lambda x:int(x)//2, input().split()))
t = f(a[0])
m >>= t
l = 1
for x in a:
    if f(x) != t:
        print(0)
        quit()
    x >>= t
    l = l // gcd(l,x) * x
    if l > m:
        print(0)
        quit()

print((m//l+2-1)//2) # round up

Submission status: Accepted

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

a = sorted(list(set(a)))

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

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

if len(a) == 1:
    ans = m // a[0]
    print(ans - ans // 2)
    exit()

temp = lcm(a[0], a[1])
if (temp // a[0]) % 2 == 0 or (temp // a[1]) % 2 == 0:
    print(0)
    exit()

for y in a[2:]:
    temp = lcm(temp, y)
    if (temp // y) % 2 == 0 or temp > m:
        print(0)
        exit()

ans = m // temp
print(ans - ans // 2)

Submission status: Accepted

Solution code:
from functools import reduce
N,M = map(int,input().split())
a = list(map(int,input().split()))
count = 0
while True:
    if a[0] % 2 == 1:
        break
    a[0] //= 2
    count += 1

flag = True
for i in range(1,N):
    if a[i] % (2**count) == 0 and a[i]% (2**(count+1)) != 0:
        a[i] //= 2**count
    else:
        flag = False
        break

def lcm(a, b): # 最小公倍数
    def gcd(a, b): # 最大公約数
        a = abs(a)
        b = abs(b)
        while b:
            a, b = b, a % b
        return a # int
    return a * b // gcd(a, b) # int
if not flag:
    print(0)
else:
    L = reduce(lcm,a)*2**(count-1)
    print((M//L+1)//2)

Submission status: Accepted

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

def input(): return sys.stdin.readline().rstrip()

def div2_cnt(n):
    m = n
    c = 0
    while m % 2 == 0:
        m /= 2
        c += 1
    return c

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

def main():
    _, m = map(int, input().split())
    a = [int(i) // 2 for i in set(input().split())]

    a0_c = div2_cnt(a[0])
    for i in a[1:]:
        if a0_c != div2_cnt(i):
            print(0)
            exit()

    first = reduce(lcm, a)
    if m < first:
        print(0)
    else:
        print((m - first) // first // 2 + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def lcm(a,b):
  if a>b:
    a,b=b,a
  if a==1:
     return b
  n=a*b
  while a!=0:
    b,a=a,b%a
  return n//b

f1,f2=a[0],a[0]
for i in range(1,N):
  f1|=a[i]
  f2&=a[i]
c=0
while f1&1==0:
  f1//=2
  c+=1
if f2&2**c==0:
  print(0)
  exit()

t=a[0]
for i in range(1,N):
  t=lcm(t,a[i])
  if t>M:
    print(0)
    break
else:
  print(M//t-M//(t*2))

Submission status: Accepted

Solution code:
import itertools

def main():
    input_line = map(int,input().split(' '))
    n,m = input_line
    a = list(map(lambda x:int(x)//2,input().split(' ')))

    pre_j = 0
    for i in range(len(a)):
        j=0
        while(a[i]%(2**j)==0):
            j+=1
        if i==0:
            pre_j=j
        if pre_j != j:
            print(0)
            return 0

    glc = 1
    for i in range(len(a)):
        glc = a[i]*glc//GCD(a[i],glc)
    print(((m//glc)+1)//2)
    return 


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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import os
import sys
from fractions import gcd

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N, M = list(map(int, sys.stdin.buffer.readline().split()))
A = list(map(int, sys.stdin.buffer.readline().split()))


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


A = np.array(A, dtype=int)
A //= 2

# l = reduce(lcm, A)
l = 1
for a in A:
    l = lcm(l, a)
    if l > M:
        print(0)
        exit()
for a in A:
    if l // a % 2 == 0:
        print(0)
        exit()
        

# cnt = math.ceil((M // l) / 2)
cnt = (M // l + 1) // 2
print(cnt)

Submission status: Accepted

Solution code:
import sys
from fractions import gcd
N, M = map(int, input().split())
an = list(map(lambda x: int(x)//2, input().split()))

lcm = an[0]
for a in an[1:]:
    l = lcm*a//gcd(lcm, a)
    if not (l//lcm % 2 == l//a % 2):
        print(0)
        sys.exit()
    lcm = l
print((M//lcm+1)//2)

Submission status: Accepted

Solution code:
n,m,*a=map(int,open(0).read().split())
c=[bin(i)[::-1].index("1") for i in a]
if sum(c)!=c[0]*n:
    print(0)
    exit()
from fractions import *
b=a[0]
for i in a:
    b=(i*b)//gcd(i,b)
    if b>2*m:
        print(0)
        exit()
print((m-b//2)//b+1)

Submission status: Accepted

Solution code:
n,m,*a=map(int,open(0).read().split())
c=[bin(i)[::-1].index("1") for i in a]
if sum(c)!=c[0]*n:
    print(0)
    exit()
import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
a=list(set(a))
b=a[0]
for i in a:
    b=lcm(i,b)
    if b>2*m:
        print(0)
        exit()
print((m-b//2)//b+1)

Submission status: Accepted

Solution code:
def f(n):
    a=0
    while n%2==0:
        n//=2
        a+=1
    return a    
n,m,*a=map(int,open(0).read().split())
c=[f(i) for i in a]
if sum(c)!=c[0]*n:
    print(0)
    exit()
import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
a=list(set(a))
a=[i//(2**c[0]) for i in a]
b=a[0]
for i in a:
    b=lcm(i,b)
    if b*(2**c[0])>2*m:
        print(0)
        exit()
b*=2**c[0]    
print(0 if b//2>m else (m-b//2)//b+1)

Submission status: Accepted

Solution code:
import sys

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

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

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


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

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

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

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

Submission status: Accepted

Solution code:
import fractions
def main():
    N, M = map(int, input().split())
    a = tuple(map(int, input().split()))
    s = a[0]
    s2 = a[0]
    s3 = 0
    while True:
        if s2 % 2 == 0:
            s2 /= 2
            s3 +=1
        else:
            break
    if s3 == 0:
        print(0)
        return 0
    for i in a:
        if i % (2 ** s3) != 0:
            print(0)
            return 0
        elif i % (2 ** (s3 + 1)) == 0:
            print(0)
            return 0
    for i in range(1,N):
        s = s * a[i] // fractions.gcd(s, a[i])
        if s > M*2:
            print(0)
            return 0
    s /= 2
    a = int(M // (2*s))
    if (M // s) % 2 == 0:
        print(a)
    else:
        print(a+1)
main()

Submission status: Accepted

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


def LCM(a, b):
    high = max(a, b)
    low = min(a, b)
    while low != 0:
        high, low = low, high % low
    gcd = high
    lcm = a * b // gcd
    return lcm


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


A_lcm = A[0]
c = Per2(A[0])
for a in A:
    if c != Per2(a):
        print(0)
        sys.exit()
for i in range(1, N):
    A_lcm = LCM(A_lcm, A[i])
    h_lcm = A_lcm // 2
    if h_lcm > M:
        print(0)
        sys.exit()

ans = (M - (A_lcm//2))//A_lcm + 1
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque
import re
import math
import functools
import itertools
import fractions

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))


INF = 1 << 29


def mk1d(n, val=INF):
    return [val for i in range(n)]

def mk2d(h, w, val=INF):
    return [[val for i in range(w)]for i in range(h)]

DIV = 998244353


def convolve(a, b):
    p, g = 1107296257, 5
    n0, n1 = len(a), len(b)
    n = 1 << (max(n0, n1) - 1).bit_length() + 1
    a = a + [0] * (n-n0)
    b = b + [0] * (n-n1)
    w = pow(g, (p - 1) // n, p)
    invw = pow(w, p-2, p)

    def fft(f):
        d = n // 2
        v = w
        while d >= 1:
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    f[j], f[j+d] = (f[j] + f[j+d]) % p, u * (f[j] - f[j+d]) % p
                u = u * v % p
            v = v * v % p
            d //= 2

    def ifft(f):
        d = 1
        while d < n:
            v = pow(invw, n // (2 * d), p)
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    f[j+d] *= u
                    f[j], f[j+d] = (f[j] + f[j+d]) % p, (f[j] - f[j+d]) % p
                u = u * v % p
            d *= 2

    fft(a), fft(b)
    for i in range(n):
        a[i] = a[i] * b[i] % p
    ifft(a)
    invn = pow(n, p - 2, p)
    return [a[i] * invn % p for i in range(n0 + n1 - 1)]


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

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


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


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

def main():
    N,M = isRaw()
    As = isRaw()
    As2 = [a//2 for a in As]
    div2X =2
    while True:
        divResult = sum([a%div2X==0 for a in As])
        if divResult != len(As2):
            if divResult != 0:
                return 0
            break
        div2X *=2
    lcm = lcm_list(As2)
    nCM = M//lcm
    return (nCM+1)//2

if __name__ == "__main__":
    print(main())

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
import math

def mod(a):
  result = 0
  while a % 2 == 0:
    a //= 2
    result += 1
  return result

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

A = list(map(lambda x: x // 2, A))

t = mod(A[0])

for i in range(N):
  if mod(A[i]) == t:
    A[i] >>= t
  else:
    print(0)
    exit()

M >>= t
M //= reduce(lcm, A)
print(math.ceil(M/2))

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

import fractions
from functools import reduce

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

N,M = II()
a = III()
b = []
for a0 in a:
    b.append(a0//2)
x = lcm_list(b)

for b0 in b:
    if (x//b0)%2==0:
        print(0)
        exit()

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

Submission status: Accepted

Solution code:
import fractions
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
ans = 0
lcm_half = A[0]//2
flag = 0
numofdiv2 = 0
for s in range(A[0]):
    if A[0] % 2 == 0:
        numofdiv2 += 1
        A[0] //= 2
    else:
        break

for i in range(1, N):

    if A[i] % (2**numofdiv2) != 0 or A[i] % (2**(numofdiv2+1)) == 0:
        flag = 1
        break
    gcd = fractions.gcd((A[i] // 2), lcm_half)
    lcm_half = (lcm_half * (A[i] // 2)) // gcd
    if lcm_half > M:
        flag = 1
        break
if flag == 1:
    ans = 0
else:
    M -= lcm_half
    ans = 1+M//(lcm_half*2)
# print(lcm_half)
print(ans)

Submission status: Accepted

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

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

n,m = inpl()
a = inpl()
g = f(a[0])
xx = a[0]

for i in range(1,n):
    if g != f(a[i]):
        print(0)
        quit()
    xx = xx*a[i]//fractions.gcd(xx,a[i])
if xx//2 > m:
    print(0)
else:
    print((m*2-xx)//(xx*2)+1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from functools import reduce
from math import ceil
# GCD
def gcd(a,b):
    while b!=0:
        a,b = b,a%b
    return a

# lのGCD
def lcmlist(l):
    res = l[0]
    for i in range(1,len(l)):
        g = gcd(res, l[i])
        res = res*l[i]//g
    return res


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

l = []
c = 0
for i in range(n):
    l.append(al[i]//2)
    cc = 0
    while al[i]%2==0:
        al[i] //= 2
        cc += 1

    if c==0:
        c = cc
    else:
        if c!=cc:
            print(0)
            exit()

g = lcmlist(l)
# if g%2==1:
#     print(0)
#     exit()

x = m//g
if x%2==1:
    print((x-1)//2+1)
else:
    print(x//2)

Submission status: Accepted

Solution code:
#ABC150_D

from fractions import gcd
N,M=map(int,input().split())
A=list(map(int,input().split()))
lcm=A[0]//2

for x in A:
    x//=2
    g=gcd(lcm,x)
    
    if (lcm//g)%2!=(x//g)%2:
        print(0)
        exit()
    
    lcm=lcm*x//g
print((M//lcm+1)//2)

Submission status: Accepted

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


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

    X = A[0]
    for i in range(1, N):
        a, b = X, A[i]
        X = a * b // gcd(a, b)
        if X > M:
            print(0)
            exit(0)

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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


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

    X = A[0]
    for i in range(1, N):
        a, b = X, A[i]
        X = a * b // gcd(a, b)
        if X > M:
            print(0)
            exit(0)

    cnt = 0
    tmp = X
    while tmp % 2 == 0:
        tmp = tmp // 2
        cnt += 1
    for a in A:
        if a % (2 ** cnt) == 0 and a % (2 ** (cnt + 1)) != 0:
            continue
        else:
            print(0)
            exit(0)
    print((M // X + 1) // 2)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=sorted(list(set(map(int,input().split()))))
df=l[0]

s=len(bin(df))-2
cnt=0
for i in range(s):
  if df%2:break
  df//=2
  cnt+=1
l=tuple(map(lambda x:x//(2**cnt),l))

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

def gcd(a,k):
  if k:return gcd(k,a%k)
  return a
an=l[0]
for i in l:
  an=an*i//gcd(an,i)

print(-(-(m//(an*2**(cnt-1)))//2))

Submission status: Accepted

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

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

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

def main():
    import sys
    readline = sys.stdin.buffer.readline
    N, M = map(int, readline().split())
    a = list(map(int, readline().split()))
    for i in range(N):
        a[i] //= 2

    t = f(a[0])
    for i in range(N):
        if f(a[i]) == t:
            a[i] >>= t
        else:
            print(0)
            return
    M >>= t

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

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

main()

Submission status: Accepted

Solution code:
# D - Semi Common Multiple

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

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

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

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

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

if all((l // x) % 2 != 0 for x in a):  # 全a_iの奇数倍
    n_scm = M // l
    n_scm = (n_scm + 1) // 2  # 奇数倍の倍数の個数
else:
    n_scm = 0

print(n_scm)

Submission status: Accepted

Solution code:
from fractions import gcd
N, M = map(int,input().split())
A = list(map(int,input().split()))
hA = list(map(lambda x:x//2,A))
def lcm_of_list(nums):
    lcm = nums[0]
    for i in range(1,len(nums)):
        lcm = (lcm * nums[i])//gcd(lcm,nums[i])
    return lcm


def calc_2dewareru(num):
    temp = 0
    cnt = 0
    while num%2 == 0:
        num /= 2
        cnt += 1
    return cnt
wareru2 = calc_2dewareru(A[0])
for i in range(1,N):
    if calc_2dewareru(A[i]) != wareru2:
        print(0)
        exit()
temp = (M //lcm_of_list(hA))
if temp %2 == 0:
    print(temp//2)
else:
    print(temp//2+1)

# if ans%2 !=0:
#     ans = ans//2+1
# print(ans)
# ans = 0
# cur = lcm_of_list(hA)
# odd = 1
# while True:
#
#     if cur*odd <= M:
#         ans += 1
#     else:break
#     odd += 2
#print(ans)

Submission status: Accepted

Solution code:
import sys
import fractions

def beki(k):
    tmp = 0
    while k % (2 ** tmp) == 0: tmp += 1
    return tmp - 1

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

g = 0
mx = 0
for i in a:
    mx = max(mx, beki(i))
    g = fractions.gcd(g, i)

if beki(g) != mx:
    print(0)
else:
    prod = 1
    lcm = 1
    for i in a:
        lcm = (lcm * (i // 2)) // fractions.gcd(lcm, i // 2)
    print((m // lcm + 1) // 2)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
A = list(map(int,input().split()))
s = set()
B = []
for a in A:
    t = a & -a
    s.add(t)
    if len(s) > 1:
        print(0)
        exit()
    B.append(a // t)

from fractions import gcd
l = 1
for b in B:
    l = b*l // gcd(b,l)

x = l*t // 2
ans = M//x - M//(2*x)
print(ans)