概要

すべての社員が参加可能な会議室が存在するかどうかを判定する問題です。各社員は特定の条件（番号が \(P_i\) の倍数の会議室に限る）を持っており、番号 \(1\) 以上 \(M\) 以下の会議室の中で、すべての条件を満たすものが存在するかを調べます。

考察

この問題の核心は、「すべての \(P_i\) の倍数であるような整数 \(j\) （ \(1 \leq j \leq M\) ）が存在するか？」という点です。

これは言い換えれば、「すべての \(P_i\) の最小公倍数（LCM）の倍数のうち、範囲 \([1, M]\) に含まれるものが存在するか？」と言い換えることができます。

例えば、\(P_1 = 4\), \(P_2 = 6\) のとき、これらの最小公倍数は \(12\) です。このとき、会議室番号が \(12, 24, 36, \ldots\) であれば両方とも参加できますが、会議室の上限 \(M\) が \(10\) ならそのような番号は存在せず、答えは No になります。

したがって、すべての \(P_i\) の最小公倍数を求め、それが \(M\) 以下であれば Yes、そうでなければ No となります。

ただし、\(P_i\) の最大値が \(10^9\)、\(N\) が最大 \(10^5\) なので、最小公倍数は非常に大きくなる可能性があります。途中で最小公倍数が \(M\) を超えた時点で、それ以降の計算は不要であり、No とすぐに判定できます。

アルゴリズム

1. 最初の \(P_1\) を最小公倍数の初期値とする。
2. 各 \(P_i\) に対して順番に最小公倍数を更新していく。
   • 最小公倍数の計算には、最大公約数（GCD）を用いる：
     $\( \mathrm{lcm}(a, b) = \frac{a \times b}{\mathrm{gcd}(a, b)} \)$
3. 計算中に最小公倍数が \(M\) を超えたら、即座に No を出力して終了。
4. 全ての \(P_i\) を処理しても最小公倍数が \(M\) 以下であれば Yes を出力。

計算量

• 時間計算量: \(O(N \log(\max(P_i)))\)
  各GCD計算が \(O(\log(\max(P_i)))\) で、それが最大 \(N\) 回行われる。
• 空間計算量: \(O(1)\)
  入力を除けば定数個の変数のみを使用。

実装のポイント

• GCDおよびLCMの計算を自前で実装することで、ライブラリ非依存で動作可能。
• 最小公倍数が途中で \(M\) を超えた時点で早期終了（枝刈り）することで、大きな入力にも耐えられる。
• Pythonの sys.stdin.read を使うことで高速な入力処理を実現している。

## ソースコード

```python
import math
from functools import reduce

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

def lcm(a, b):
    return a * b // gcd(a, b)

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    M = int(data[1])
    P = list(map(int, data[2:]))

    # Compute LCM of all P_i
    current_lcm = P[0]
    for i in range(1, N):
        current_lcm = lcm(current_lcm, P[i])
        # Early exit if LCM exceeds M
        if current_lcm > M:
            print("No")
            return

    # Check if there exists a multiple of LCM within [1, M]
    if current_lcm <= M:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。