Overview

Determine whether there exists a meeting room number \(j(1\le j\le M)\) that all employees can attend, by checking whether the least common multiple of \(P_1,\dots,P_N\) is at most \(M\).

Discussion

The meeting rooms that employee \(i\) can attend are “those whose number is a multiple of \(P_i\).” In other words, a meeting room number \(j\) that everyone can attend must satisfy

• \(P_i \mid j\) for all \(i\)

This means “\(j\) is a common multiple of \(P_1,\dots,P_N\).”

There are infinitely many common multiples, but the smallest positive common multiple is the least common multiple \(L=\mathrm{lcm}(P_1,\dots,P_N)\).
Therefore,

• If \(L \le M\), we can choose \(j=L\) and everyone can attend, so the answer is Yes
• If \(L > M\), there is no common multiple less than \(L\), so the answer is No

Why the Naive Approach Fails

The approach of “trying every \(j\) from \(1\) to \(M\)” is impossible since \(M\) can be up to \(10^{18}\) (guaranteed TLE).

Also, if we compute the least common multiple directly, the value tends to grow rapidly, and depending on the language, there is a risk of overflow. Therefore, it is important to terminate early once the value exceeds \(M\).

Algorithm

1. Maintain \(l=1\) as the current least common multiple.
2. For each \(p=P_i\), update \(l\) as follows:
   • \(\gcd(l,p)=g\)
   • \(\mathrm{lcm}(l,p) = \dfrac{l}{g}\cdot p\)
3. As soon as the updated \(l\) exceeds \(M\), it can only increase further, so output No and terminate.
4. If \(l\le M\) after processing all elements, output Yes.

Concrete Example

• When \(P=[2,3,4]\):
  \(l=\mathrm{lcm}(2,3,4)=12\). If \(M=10\), then \(12>10\) so the answer is No; if \(M=20\), the answer is Yes (we can use \(j=12\)).

Complexity

• Time complexity: \(O\left(N\log(\max P_i)\right)\) (each \(\gcd\) computation takes logarithmic time)
• Space complexity: \(O(1)\) (constant aside from the input array)

Implementation Notes

• Computing the LCM as \(\mathrm{lcm}(a,b)=\dfrac{a}{\gcd(a,b)}\cdot b\) is safe (divide first, then multiply).

• Terminating immediately with No once \(l > M\) avoids computation with enormous numbers.

• Since \(M\) can be as large as \(10^{18}\), the intermediate value of \(l\) can also become very large. Python handles this natively with arbitrary-precision integers, but in other languages, overflow countermeasures are necessary.

  Source Code

import sys
import math

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, M = data[0], data[1]
    P = data[2:2+N]

    l = 1
    for p in P:
        g = math.gcd(l, p)
        l = (l // g) * p
        if l > M:
            print("No")
            return
    print("Yes" if l <= M else "No")

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.