概要

全社員が参加できる会議室番号 \(j(1\le j\le M)\) が存在するかを、\(P_1,\dots,P_N\) の最小公倍数が \(M\) 以下かどうかで判定します。

考察

社員 \(i\) が参加できる会議室は「番号が \(P_i\) の倍数」です。つまり、全員が参加できる会議室番号 \(j\) とは

• すべての \(i\) について \(P_i \mid j\)

を満たす数です。これは「\(j\) が \(P_1,\dots,P_N\) の共通の倍数」であることを意味します。

共通の倍数は無数にありますが、最小の正の共通の倍数は 最小公倍数 \(L=\mathrm{lcm}(P_1,\dots,P_N)\) です。
したがって、

• \(L \le M\) なら、\(j=L\) を選べば全員参加できるので Yes
• \(L > M\) なら、\(L\) 未満に共通の倍数は存在しないため No

となります。

素朴な方法がダメな理由

「\(1\) から \(M\) まで全部の \(j\) を試す」方法は、\(M\) が最大 \(10^{18}\) なので不可能です（確実に TLE）。

また、最小公倍数をそのまま計算していくと値が急増しやすく、言語によってはオーバーフローの危険があります。そこで 途中で \(M\) を超えたら打ち切るのが重要です。

アルゴリズム

1. \(l=1\) を現在の最小公倍数として持つ。
2. 各 \(p=P_i\) について、次で \(l\) を更新する：
   • \(\gcd(l,p)=g\)
   • \(\mathrm{lcm}(l,p) = \dfrac{l}{g}\cdot p\)
3. 更新した \(l\) が \(M\) を超えた時点で、これ以上増えるだけなので No を出力して終了。
4. 最後まで \(l\le M\) なら Yes。

具体例

• \(P=[2,3,4]\) のとき
  \(l=\mathrm{lcm}(2,3,4)=12\)。もし \(M=10\) なら \(12>10\) なので No、\(M=20\) なら Yes（\(j=12\) が使える）。

計算量

• 時間計算量: \(O\left(N\log(\max P_i)\right)\)（各回の \(\gcd\) 計算が対数時間）
• 空間計算量: \(O(1)\)（入力配列を除けば定数）

実装のポイント

• 最小公倍数は \(\mathrm{lcm}(a,b)=\dfrac{a}{\gcd(a,b)}\cdot b\) で計算すると安全（先に割ってから掛ける）。

• \(l > M\) になったら即 No で打ち切ると、巨大な数の計算を避けられます。

• \(M\) が \(10^{18}\) と大きいので、途中経過の \(l\) も大きくなり得ます。Python は多倍長整数なのでそのまま扱えますが、他言語ではオーバーフロー対策が必要です。

  ソースコード

import sys
import math

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, M = data[0], data[1]
    P = data[2:2+N]

    l = 1
    for p in P:
        g = math.gcd(l, p)
        l = (l // g) * p
        if l > M:
            print("No")
            return
    print("Yes" if l <= M else "No")

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。