Overview

This problem asks us to determine whether there exists a meeting room number \(j\) that all employees can attend. This can be solved by checking whether the least common multiple (LCM) of all \(P_i\) is at most \(M\).

Analysis

Rephrasing the Problem

Employee \(i\) can attend “meeting rooms whose numbers are multiples of \(P_i\)”. In other words, for all employees to be able to attend meeting room number \(j\), \(j\) must be a multiple of all \(P_i\).

Key Insight

“The smallest positive integer that is a multiple of all \(P_i\)” is the least common multiple (LCM) of \(P_1, P_2, \ldots, P_N\).

For example, if \(P = [2, 3, 4]\): - Multiples of \(2\): \(2, 4, 6, 8, 10, 12, \ldots\) - Multiples of \(3\): \(3, 6, 9, 12, \ldots\) - Multiples of \(4\): \(4, 8, 12, \ldots\) - Common multiples: \(12, 24, 36, \ldots\) (LCM = 12)

Therefore, if \(\text{LCM}(P_1, P_2, \ldots, P_N) \leq M\), output Yes; otherwise, output No.

Problem with the Naive Approach

Since \(M\) can be as large as \(10^{18}\), checking each number from \(1\) to \(M\) sequentially would result in TLE. We need to compute the LCM directly and compare.

Handling Overflow

When values of \(P_i\) are large, the LCM can become extremely large. While Python doesn’t have integer overflow issues, computation can become slow. Therefore, we terminate early as soon as the LCM exceeds \(M\) during calculation.

Algorithm

1. Initialize LCM to \(1\)
2. For each \(P_i\), compute the LCM of the current LCM and \(P_i\)
   • \(\text{LCM}(a, b) = \frac{a}{\gcd(a, b)} \times b\) (perform division first to prevent overflow)
3. If LCM exceeds \(M\), output No and terminate immediately
4. If LCM remains at most \(M\) after processing all \(P_i\), output Yes

Concrete Example

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

Step	Operation	current_lcm
Initial	-	\(1\)
1	\(\text{LCM}(1, 2) = 2\)	\(2\)
2	\(\text{LCM}(2, 3) = 6\)	\(6\)
3	\(\text{LCM}(6, 4) = 12\)	\(12\)

Since \(12 \leq 12\), output Yes

Complexity

• Time complexity: \(O(N \log(\max P_i))\)
  • Computing GCD for each \(P_i\) takes \(O(\log(\max P_i))\)
• Space complexity: \(O(N)\)
  • Required to store the input array \(P\)

Implementation Notes

1. Order of LCM calculation: Writing \(a / \gcd(a, b) \times b\) instead of \(a \times b / \gcd(a, b)\) keeps intermediate values smaller.

2. Early termination: By immediately outputting No as soon as LCM exceeds \(M\), we avoid unnecessary computation. This allows efficient handling even when the LCM would become astronomically large.

3. Python’s math.gcd: Since Python 3.5, math.gcd is available in the standard library, so there’s no need to implement GCD yourself.

Source Code

import math
from functools import reduce

def solve():
    N, M = map(int, input().split())
    P = list(map(int, input().split()))
    
    # Meeting room number j that all employees can attend must be a multiple of all P_i
    # In other words, j must be a multiple of the LCM of all P_i
    # Check whether such j exists in the range from 1 to M
    # → If LCM(P_1, P_2, ..., P_N) <= M, then Yes
    
    def lcm(a, b):
        return a // math.gcd(a, b) * b
    
    # Calculate LCM (with early termination if it exceeds M to handle overflow)
    current_lcm = 1
    for p in P:
        current_lcm = lcm(current_lcm, p)
        if current_lcm > M:
            print("No")
            return
    
    print("Yes")

solve()

---

This editorial was generated by claude4.5opus.