概要

この問題は、与えられた \(N\) 個の整数 \(P_1, P_2, \dots, P_N\) すべての倍数（公倍数）となっているような番号 \(j\) が、\(1\) 以上 \(M\) 以下の範囲に存在するかどうかを判定する問題です。

考察

最小公倍数に着目する

条件「\(j\) がすべての \(P_i\) の倍数である」を満たす最小の正の整数 \(j\) は、 \(P_1, P_2, \dots, P_N\) の最小公倍数（LCM: Least Common Multiple）です。

もし、この最小公倍数が \(M\) 以下であれば、その番号の会議室（およびその倍数の番号の会議室）に全員が参加できることになります。逆に、最小公倍数が \(M\) を超えてしまう場合は、どのような公倍数も \(M\) より大きくなってしまうため、条件を満たす会議室は存在しません。

したがって、この問題は「\(P_1, \dots, P_N\) の最小公倍数を求め、それが \(M\) 以下か判定する」という問題に言い換えられます。

数値の増大への対処

制約を確認すると、\(M\) は最大で \(10^{18}\) ですが、最小公倍数はこれを容易に超える可能性があります（例えば、小さな素数をたくさん掛け合わせるだけで非常に大きな値になります）。

Pythonなどの多倍長整数を扱う言語ではそのまま計算を続けることも可能ですが、計算効率やメモリの観点から、「計算の途中で最小公倍数が \(M\) を超えたら、その時点で No と判定して終了する」という工夫を行うのが効率的です。

アルゴリズム

1. 現在の最小公倍数を保持する変数 current_lcm を \(1\) で初期化します。
2. 各 \(P_i\) (\(i = 1, 2, \dots, N\)) について、順に以下の操作を行います：
   • current_lcm と \(P_i\) の新しい最小公倍数を計算します。
   • 2つの数 \(a, b\) の最小公倍数は、最大公約数（GCD）を用いて \(\text{lcm}(a, b) = (a \times b) // \text{gcd}(a, b)\) と計算できます。
   • もし計算の途中で current_lcm > M となったら、即座に No を出力してプログラムを終了します。
3. すべての \(P_i\) について計算し終えたとき、current_lcm \le M であれば Yes を、そうでなければ No を出力します。

計算量

• 時間計算量: \(O(N \log(\max P_i))\)
  • \(N\) 個の要素に対して最大公約数（GCD）を求めます。GCDの計算（ユークリッドの互除法）は対数時間で終わるため、十分高速です。
• 空間計算量: \(O(N)\)
  • 入力値をリストとして保持する場合に \(O(N)\) 必要です。

実装のポイント

• 計算順序: (current_lcm * p) // g と書くよりも、先に (current_lcm // g) * p と計算することで、途中の値が不必要に大きくなるのを防ぐことができます。

• 早期終了: \(M\) を超えた瞬間にループを抜ける処理を入れることで、無駄な計算を省くとともに、数値が巨大になりすぎて計算速度が低下するリスクを回避しています。

  ソースコード

import math
import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白で分割してリストにする
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 社員の人数 N と 会議室の数 M を取得
    n = int(input_data[0])
    m = int(input_data[1])
    
    # 最小公倍数 (LCM) を計算していく
    # 全社員が参加できる最小の会議室番号は、すべての P_i の最小公倍数である
    current_lcm = 1
    
    for i in range(n):
        p = int(input_data[i + 2])
        
        # current_lcm と p の最小公倍数を求める
        # lcm(a, b) = (a * b) // gcd(a, b)
        # 途中で M を超える場合は、それ以上計算しても M 以下になることはないので打ち切る
        g = math.gcd(current_lcm, p)
        current_lcm = (current_lcm // g) * p
        
        if current_lcm > m:
            print("No")
            return
            
    # 全ての P_i の最小公倍数が M 以下であれば、その番号の会議室が存在する
    if current_lcm <= m:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    solve()

この解説は gemini-3-flash-preview によって生成されました。