概要

すべての社員が参加できる会議室番号 \(j\) が存在するかを判定する問題です。これは、すべての \(P_i\) の最小公倍数（LCM）が \(M\) 以下かどうかを確認することで解けます。

考察

問題の言い換え

社員 \(i\) は「番号が \(P_i\) の倍数である会議室」に参加できます。つまり、会議室番号 \(j\) にすべての社員が参加できるためには、\(j\) がすべての \(P_i\) の倍数である必要があります。

重要な気づき

「すべての \(P_i\) の倍数である最小の正整数」は、\(P_1, P_2, \ldots, P_N\) の最小公倍数（LCM）です。

例えば、\(P = [2, 3, 4]\) の場合： - \(2\) の倍数: \(2, 4, 6, 8, 10, 12, \ldots\) - \(3\) の倍数: \(3, 6, 9, 12, \ldots\) - \(4\) の倍数: \(4, 8, 12, \ldots\) - すべての倍数: \(12, 24, 36, \ldots\)（LCM = 12）

したがって、\(\text{LCM}(P_1, P_2, \ldots, P_N) \leq M\) であれば Yes、そうでなければ No です。

素朴なアプローチの問題点

\(M\) は最大 \(10^{18}\) と非常に大きいため、\(1\) から \(M\) まで順に調べる方法では TLE になります。LCM を直接計算して比較する必要があります。

オーバーフローへの対策

\(P_i\) の値が大きい場合、LCM は非常に大きな値になる可能性があります。Python では整数のオーバーフローは起きませんが、計算に時間がかかることがあります。そこで、LCM の計算途中で \(M\) を超えた時点で早期終了します。

アルゴリズム

1. LCM の初期値を \(1\) とする
2. 各 \(P_i\) について、現在の LCM と \(P_i\) の LCM を計算する
   • \(\text{LCM}(a, b) = \frac{a}{\gcd(a, b)} \times b\)（オーバーフロー防止のため割り算を先に行う）
3. LCM が \(M\) を超えたら、その時点で No を出力して終了
4. すべての \(P_i\) を処理しても LCM が \(M\) 以下なら Yes を出力

具体例

入力: \(N=3, M=12, P=[2, 3, 4]\)

ステップ	処理	current_lcm
初期	-	\(1\)
1	\(\text{LCM}(1, 2) = 2\)	\(2\)
2	\(\text{LCM}(2, 3) = 6\)	\(6\)
3	\(\text{LCM}(6, 4) = 12\)	\(12\)

\(12 \leq 12\) なので Yes

計算量

• 時間計算量: \(O(N \log(\max P_i))\)
  • 各 \(P_i\) について GCD を計算するのに \(O(\log(\max P_i))\)
• 空間計算量: \(O(N)\)
  • 入力配列 \(P\) の格納に必要

実装のポイント

1. LCM の計算順序: \(a \times b / \gcd(a, b)\) ではなく、\(a / \gcd(a, b) \times b\) と書くことで、中間値の大きさを抑えられます。

2. 早期終了: LCM が \(M\) を超えた時点で即座に No を出力することで、不要な計算を避けられます。これにより、LCM が天文学的な数になる場合でも効率的に処理できます。

3. Python の math.gcd: Python 3.5 以降では math.gcd が標準で使えるため、GCD を自前で実装する必要はありません。

   ソースコード

import math
from functools import reduce

def solve():
    N, M = map(int, input().split())
    P = list(map(int, input().split()))
    
    # すべての社員が参加できる会議室番号jは、すべてのP_iの倍数である必要がある
    # つまり、jはすべてのP_iの最小公倍数(LCM)の倍数である必要がある
    # そのようなjが1からMの範囲に存在するかどうかを確認する
    # → LCM(P_1, P_2, ..., P_N) <= M であればYes
    
    def lcm(a, b):
        return a // math.gcd(a, b) * b
    
    # LCMを計算（オーバーフロー対策として、Mを超えたら早期終了）
    current_lcm = 1
    for p in P:
        current_lcm = lcm(current_lcm, p)
        if current_lcm > M:
            print("No")
            return
    
    print("Yes")

solve()

---

この解説は claude4.5opus によって生成されました。