Problem:


Score : 400 points

Problem Statement

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

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

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

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

Constraints

1 \leq N \leq 10^5

1 \leq M \leq 10^9

2 \leq a_i \leq 10^9

a_i is an even number.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
a_1 a_2 ... a_N

Output

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

Sample Input 1

2 50
6 10

Sample Output 1

2

15 = 6  \times 2.5 

15 = 10 \times 1.5 

45 = 6  \times 7.5 

45 = 10 \times 4.5 

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

Sample Input 2

3 100
14 22 40

Sample Output 2

0

The answer can be 0.

Sample Input 3

5 1000000000
6 6 2 6 2

Sample Output 3

166666667



Sample input:
2 50
6 10


Sample output:
2

Submission status: Wrong Answer

Solution code:
from fractions import gcd
from math import ceil

n, m = [int(x) for x in input().split()]

a_list = [int(x) for x in input().split()]
a_h_list = [a // 2 for a in a_list]

temp = 1
for a_h in a_h_list:
    temp *= a_h // gcd(a_h, temp)

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

Submission status: Wrong Answer

Solution code:
from fractions import gcd

n, m = [int(x) for x in input().split()]

a_list = [int(x) for x in input().split()]
a_h_list = [a // 2 for a in a_list]

temp = 1
for a_h in a_h_list:
    temp *= a_h // gcd(a_h, temp)

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

Submission status: Wrong Answer

Solution code:
from fractions import gcd

n, m = [int(x) for x in input().split()]

a_list = [int(x) for x in input().split()]
a_h_list = [a // 2 for a in a_list]

temp = 1
for a_h in a_h_list:
    temp *= a_h // gcd(a_h, temp)

def count(x, y):
    if x <= 2 * y:
        return 0
    return (x - y) // (y * 2) + 1

ans = count(m, temp) - count(max(a_list), temp)
print(ans)

Submission status: Wrong Answer

Solution code:
from fractions import gcd
from functools import reduce

n, m = [int(x) for x in input().split()]

a_list = [int(x) for x in input().split()]
a_h_list = [a // 2 for a in a_list]

temp = 1
for a_h in a_h_list:
    temp *= a_h // gcd(a_h, temp)

ans = (m - temp) // (temp * 2) + 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

n,m=map(int,input().split())
l=list(map(int,input().split()))
l=[i/2 for i in l]
  
def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a

s=set(l)
l=set(l)

if len(l)==1:
  lcm=l.pop()
  if (m//lcm)%2==0:
    print(int((m//lcm)/2))
  else:
    print(int((m//lcm+1)/2))
  exit()
a1=l.pop()
a2=l.pop()
g=gcd(a1,a2)
lcm=g*(a1/g)*(a2/g)
d=1

while l:
  a=l.pop()
  d=gcd(lcm,a)
  lcm=d*(a/d)*(lcm/d)
  print("##")
  
if lcm>m:
  print(0)
  exit()
  
for a in s:
  if (lcm/a)%2==0:
    print(0)
    break
else:
  if (m//lcm)%2==0:
    print(int((m//lcm)/2))
  else:
    print(int((m//lcm+1)/2))

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline

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

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

    N, M = (int(i) for i in input().split())
    A = [int(i)//2 for i in input().split()]
    if any(A[0] % 2 != a % 2 for a in A):
        return print(0)
    L = 1
    for a in A:
        L = lcm(L, a)

    ans = 0
    mul = 1
    while L*mul <= M:
        ans += 1
        mul += 2
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline

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

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

    N, M = (int(i) for i in input().split())
    A = [int(i)//2 for i in input().split()]
    L = 1
    for a in A:
        L = lcm(L, a)
    ans = 0
    mul = 1
    while L*mul <= M:
        ans += 1
        mul += 2
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    def gcd(x, y):
        if y == 0:
            return x
        while y != 0:
            x, y = y, x % y
        return x

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

    N, M = (int(i) for i in input().split())
    A = [int(i)//2 for i in input().split()]
    L = 1
    for a in A:
        L = lcm(L, a)
    print(0--M//(2*L) if L <= M else 0)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import fractions
from functools import reduce

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

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

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

halfas = []
for a in aes:
  if a % 2 != 0:
    print(0)
    sys.exit()
  halfas.append(a // 2)
  
lcm = lcm_list(halfas)
# print(lcm)
pp = m // lcm
if pp % 2 == 0:
  ans = int(pp / 2)
else: 
  ans = int((pp + 1) / 2)


print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import fractions
from functools import reduce

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

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

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

halfas = []
for a in aes:
  if a % 2 != 0:
    print(0)
    sys.exit()
  halfas.append(a // 2)
  
lcm = lcm_list(halfas)
# print(lcm)

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


print(ans)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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

g = a[0]
for i in range(nn):
    t = gcd(g,a[i])
    
x = a[0]
for i in range(1,nn):
    x *= a[i]
    x //= t
    
fl = 1
ff = x//2
for i in range(nn):
    if ff % a[i] != a[i] // 2:
        fl = 0
        
if fl == 1:
    xx = (m-ff) // x + 1
else:
    xx = 0
    
print(xx)

Submission status: Wrong Answer

Solution code:
"""
import random
import functools
import copy
import bisect
import array
import re
import collections
import heapq
import fractions
import itertools
import string
import math
from operator import itemgetter as ig
from bisect import bisect_left, bisect_right, insort_left, insort_right
from itertools import permutations, combinations, product, accumulate, groupby
from heapq import heappush, heappop
from collections import deque, defaultdict, Counter
import sys
sys.setrecursionlimit(10 ** 7)
# import numpy as np

inf = 10 ** 20
INF = float("INF")
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]
ddn9 = ddn + [(0, 0)]
'''for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:'''
"""
from collections import Counter
import sys
sys.setrecursionlimit(10 ** 7)


def wi(): return list(map(int, sys.stdin.readline().split()))
# WideIntPoint


def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]


def ws(): return sys.stdin.readline().split()


def si(): return int(sys.stdin.readline())  # SingleInt


def ss(): return input()


def hi(n): return [si() for _ in range(n)]


def hs(n): return [ss() for _ in range(n)]  # HeightString


def s_list(): return list(input())


def mi(n): return [wi() for _ in range(n)]  # MatrixInt


def mip(n): return [wip() for _ in range(n)]


def ms(n): return [ws() for _ in range(n)]


def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[
    0]] for _ in range(n)]  # NumberGrid


def grid(n): return [s_list() for _ in range(n)]


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


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


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


def main():
    N, M = wi()
    a = wi()

    for i in range(len(a)):
        if a[i] % 2 != 0:
            print('0')
            sys.exit()
        else:
            a[i] //= 2

    t = f(a[0])
    for i in range(N):
        if f(a[i]) != t:
            print(0)
            sys.exit()
        else:
            a[i] /= 2**t
    M //= 2**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(int(ans))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from fractions import gcd
def lcm(a,b):
    return a*b//gcd(a,b)
n,m=map(int,input().split())
a=list(map(int,input().split()))
h=[]
for i in range(n):
    t=a[i]
    while(t%2==0):
        t//=2
    h.append(t)
lch=1
lca=1
for i in range(n):
    lca=lcm(lch,a[i])
for i in range(n):
    lch=lcm(lch,h[i])
print(m//lch-m//lcm(lch,lca))

Submission status: Wrong Answer

Solution code:
import fractions
import math
a,b=map(int,input().split())
List=list(map(int,input().split()))
List=set(List)
def lcm(p,q):
    return(p*q/fractions.gcd(p,q))
l=1
for i in List:
  l=lcm(l,i)
l=l/2
s=b//l
print(math.ceil(s/2))

Submission status: Wrong Answer

Solution code:
#素因数分解
def soinsu_bunkai(m):
    pf={}

    for i in range(2,int(m**0.5)+1):
        while m%i==0:
            pf[i]=pf.get(i,0)+1
            m//=i
    if m>1:
        pf[m]=1
    return pf

#初期入力
N,M= (int(x) for x in input().split())
A= list(map(int, input().split()))

#
y ={}
han_saisyo_kobaisu =1
for i in A:
    x_dic =soinsu_bunkai(i) 
    for k,v in x_dic.items():
        if len(x_dic)==1:
            han_saisyo_kobaisu =0
            break
        elif k not in y:
            y[k] = v
        else:
            if y[k] < v:
                y[k] = v
#半＿最小公倍数
for i,v in y.items():
    han_saisyo_kobaisu *= i**v
han_saisyo_kobaisu //=2

#半公倍数の数( Mの中に半最小公倍数の数→偶数を削除のためさらに2で割る)
if han_saisyo_kobaisu != 0:
    han_kobaisu_num =( M // han_saisyo_kobaisu +1 )//2
else:
    han_kobaisu_num =0
print(han_kobaisu_num)

Submission status: Wrong Answer

Solution code:
import fractions
import math
a,b=map(int,input().split())
def lcm(p,q):
    return(p*q/fractions.gcd(p,q))
List=list(map(int,input().split()))
l=1
for i in range(a-1):
  l=lcm(l,lcm(List[i],List[i+1]))
l=l/2
s=b//l
print(math.ceil(s/2))

Submission status: Wrong Answer

Solution code:
#素因数分解
def soinsu_bunkai(m):
    pf={}

    for i in range(2,int(m**0.5)+1):
        while m%i==0:
            pf[i]=pf.get(i,0)+1
            m//=i
    if m>1:
        pf[m]=1
    return pf

#初期入力
N,M= (int(x) for x in input().split())
A= list(map(int, input().split()))

#
y ={}
for i in A:
    x_dic =soinsu_bunkai(i) 
    for k,v in x_dic.items():
        if k not in y:
            y[k] = v
        else:
            if y[k] < v:
                y[k] = v
#半＿最小公倍数
han_saisyo_kobaisu =1
for i,v in y.items():
    han_saisyo_kobaisu *= i**v
han_saisyo_kobaisu //=2

#半公倍数の数( Mの中に半最小公倍数の数→偶数を削除のためさらに2で割る)
han_kobaisu_num =( M // han_saisyo_kobaisu +1 )//2
print(han_kobaisu_num)

Submission status: Wrong Answer

Solution code:
from functools import reduce
n, m = map(int, input().split())
a = list(map(int, input().split()))
l = [set() for _ in range(n)]
for i in range(n):
    j = 1
    while ((a[i]//2) * j) < m:
        l[i].add((a[i]//2) * j)
        j += 2
print(len(reduce(lambda a, b:a&b,l)))