Overview

This is a problem of determining whether there exists a meeting room that all employees can attend. Each employee has a specific condition (they can only use meeting rooms whose number is a multiple of \(P_i\)), and we need to check whether there exists a room among those numbered \(1\) to \(M\) that satisfies all conditions.

Analysis

The core of this problem is: “Does there exist an integer \(j\) (\(1 \leq j \leq M\)) that is a multiple of all \(P_i\)?”

This can be rephrased as: “Does there exist a multiple of the least common multiple (LCM) of all \(P_i\) that falls within the range \([1, M]\)?”

For example, when \(P_1 = 4\) and \(P_2 = 6\), their least common multiple is \(12\). In this case, both employees can attend if the meeting room number is \(12, 24, 36, \ldots\), but if the upper limit \(M\) is \(10\), no such number exists, and the answer is No.

Therefore, we compute the LCM of all \(P_i\), and if it is at most \(M\), the answer is Yes; otherwise, it is No.

However, since the maximum value of \(P_i\) is \(10^9\) and \(N\) can be up to \(10^5\), the LCM can become extremely large. Once the LCM exceeds \(M\) during computation, no further calculation is needed, and we can immediately determine the answer as No.

Algorithm

1. Set the initial LCM value to \(P_1\).
2. Update the LCM sequentially for each \(P_i\).
   • Use the greatest common divisor (GCD) to compute the LCM:
     $\( \mathrm{lcm}(a, b) = \frac{a \times b}{\mathrm{gcd}(a, b)} \)$
3. If the LCM exceeds \(M\) during computation, immediately output No and terminate.
4. If the LCM remains at most \(M\) after processing all \(P_i\), output Yes.

Complexity

• Time complexity: \(O(N \log(\max(P_i)))\)
  Each GCD computation takes \(O(\log(\max(P_i)))\), and this is performed at most \(N\) times.
• Space complexity: \(O(1)\)
  Only a constant number of variables are used aside from the input.

Implementation Notes

• By implementing GCD and LCM computations manually, the solution can run without library dependencies.

• Early termination (pruning) when the LCM exceeds \(M\) during computation allows the solution to handle large inputs efficiently.

• Using Python’s sys.stdin.read enables fast input processing.

  Source Code

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

This editorial was generated by qwen3-coder-480b.