Overview

This problem asks us to determine whether there exists a number \(j\) in the range from \(1\) to \(M\) that is a multiple of all \(N\) given integers \(P_1, P_2, \dots, P_N\) (i.e., a common multiple).

Analysis

Focusing on the Least Common Multiple

The smallest positive integer \(j\) satisfying the condition “\(j\) is a multiple of every \(P_i\)” is the Least Common Multiple (LCM) of \(P_1, P_2, \dots, P_N\).

If this LCM is at most \(M\), then the meeting room with that number (as well as meeting rooms whose numbers are multiples of the LCM) can be attended by everyone. Conversely, if the LCM exceeds \(M\), then every common multiple is also greater than \(M\), so no meeting room satisfies the condition.

Therefore, this problem can be rephrased as “Compute the LCM of \(P_1, \dots, P_N\) and determine whether it is at most \(M\).”

Handling Large Numbers

Looking at the constraints, \(M\) can be up to \(10^{18}\), but the LCM can easily exceed this (for example, multiplying many small primes together produces a very large value).

In languages like Python that support arbitrary-precision integers, it is possible to continue computation directly, but from the perspective of computational efficiency and memory, it is more efficient to use the following optimization: “If the LCM exceeds \(M\) during computation, immediately output No and terminate.”

Algorithm

1. Initialize a variable current_lcm that holds the current LCM to \(1\).
2. For each \(P_i\) (\(i = 1, 2, \dots, N\)), perform the following operations in order:
   • Compute the new LCM of current_lcm and \(P_i\).
   • The LCM of two numbers \(a, b\) can be computed using the Greatest Common Divisor (GCD) as \(\text{lcm}(a, b) = (a \times b) // \text{gcd}(a, b)\).
   • If current_lcm > M at any point during the computation, immediately output No and terminate the program.
3. After computing for all \(P_i\), output Yes if current_lcm \le M, and No otherwise.

Complexity

• Time complexity: \(O(N \log(\max P_i))\)
  • We compute the Greatest Common Divisor (GCD) for \(N\) elements. The GCD computation (Euclidean algorithm) runs in logarithmic time, so it is sufficiently fast.
• Space complexity: \(O(N)\)
  • \(O(N)\) is needed if the input values are stored as a list.

Implementation Notes

• Order of computation: Rather than writing (current_lcm * p) // g, computing (current_lcm // g) * p first prevents intermediate values from becoming unnecessarily large.

• Early termination: By including a check to break out of the loop the moment the value exceeds \(M\), we avoid unnecessary computation and mitigate the risk of computation slowdown due to excessively large numbers.

  Source Code

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()

This editorial was generated by gemini-3-flash-preview.