Edit

【pythonでABC150を解説】D - Semi Common Multiple

問題概要

問題ページ

D - Semi Common Multiple
D - Semi Common Multiple

問題ページへ移動する

問題文

長さ \(N\) の偶数からなる正の整数列 \(A= {a_1,a_2,...,a_N}\) と、整数 \(M\) が与えられます。

任意の \(k(1 \leq k \leq N)\) に対して以下の条件を満たす正の整数 \(X\) を \(A\) の「半公倍数」と定義します。

  • \(X= a_k \times (p+0.5)\) を満たす負でない整数 \(p\) が存在する。

\(1\) 以上 \(M\) 以下の整数のうちの \(A\) の半公倍数の個数を求めてください。

制約

  • \(1 \leq N \leq 10^5\)
  • \(1 \leq M \leq 10^9\)
  • \(2 \leq a_i \leq 10^9\)
  • \(a_i\) は偶数である。
  • 入力は全て整数である。

問題の考察

ACコード

import sys
import fractions


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, readline().split()))
    a = [v >> 1 for v in list(map(int, readline().split()))]
    lcm = a[0]
    for v in a[1:]:
        gcd = fractions.gcd(lcm, v)
        if lcm // gcd % 2 == 0 or v // gcd % 2 == 0:
            print(0)
            exit()
        else:
            lcm = lcm * v // gcd
        if lcm > m:
            print(0)
            exit()
    print(m // lcm - m // (lcm * 2))


if __name__ == '__main__':
    solve()

-Edit