Overview

For each device’s period \(T_i=\frac{P_i}{Q_i}\) (in lowest terms), the earliest time at or after time \(0\) when all devices launch simultaneously is the least common multiple \(L\) of these rational numbers. We compute \(L\) as an irreducible fraction.

Analysis

Key Insight

Just like the least common multiple of integers, for rational numbers we need to find the smallest rational number \(L\) such that \(L\) is an integer multiple of every \(T_i\).

Since \(T_i\) are fractions, handling them with floating point will break due to precision errors (e.g., \(1/3\) cannot be represented exactly in finite digits). Therefore, we compute with fractions directly.

Why Naive Approaches Fail

• Simulating time step by step: Since periods are fractions, choosing a step size is difficult, and in the worst case it takes extremely long to find a coincidence (TLE).
• Directly computing \(D=\mathrm{lcm}(Q_i)\) to align all denominators: \(D\) can become enormous, causing intermediate computations to break down (overflow or heavy computation).

Solution

We use a formula that computes the LCM of two fractions using only the greatest common divisor (gcd), and apply it sequentially (folding \(N\) values into one).

Algorithm

We find the least common multiple of two irreducible fractions [ x=\frac{a}{b},\quad y=\frac{c}{d} ]

The condition for \(L\) to be a common multiple is [ \frac{L}{x}=\frac{Lb}{a}\in \mathbb{Z}{>0},\quad \frac{L}{y}=\frac{Ld}{c}\in \mathbb{Z}{>0} ] That is, \(L\) can be written as [ L=\frac{a}{b}\cdot k=\frac{c}{d}\cdot m \quad (k,m\in\mathbb{Z}_{>0}) ]

Now consider the following form: [ L=\frac{ac}{g} ] Then [ \frac{L}{a/b}=\frac{ac/g}{a/b}=\frac{bc}{g},\quad \frac{L}{c/d}=\frac{ac/g}{c/d}=\frac{ad}{g} ] So if \(\frac{bc}{g}\) and \(\frac{ad}{g}\) are integers, then \(L\) is a common multiple. This means \(g\) just needs to be a common divisor of \(ad\) and \(bc\), and to minimize \(L\) we should maximize \(g\), so the optimal choice is [ g=\gcd(ad,\,bc) ] Therefore, [ \mathrm{lcm}!\left(\frac{a}{b},\frac{c}{d}\right)=\frac{ac}{\gcd(ad,bc)} ] (reduced to lowest terms at the end).

In this problem, we apply this sequentially from left to right: - Let the current answer be \(\frac{A}{B}\) - Let the next period be \(\frac{P}{Q}\)

Then [ \text{den}=\gcd(AQ,\,BP),\quad \text{num}=AP,\quad L=\frac{\text{num}}{\text{den}} ] Finally, divide by \(\gcd(\text{num},\text{den})\) to reduce to lowest terms, giving the next \((A,B)\).

(Example) \(\frac{1}{2}\) and \(\frac{1}{3}\) \(\gcd(1\cdot 3,2\cdot 1)=\gcd(3,2)=1\), so \(L=\frac{1\cdot 1}{1}=1\). Indeed, the first simultaneous time is \(1\) second.

Complexity

• Time complexity: \(O(N \log M)\) (a few gcd operations per step; \(M\) is the magnitude of the numbers)
• Space complexity: \(O(1)\) (only the numerator and denominator of the answer are maintained)

Implementation Notes

• Always store as integers (numerator and denominator), never use floating point (precision errors cause WA).

• Reducing to lowest terms with \(\gcd\) at each step prevents numbers from growing unnecessarily large.

• Since the input size can be large, use sys.stdin.buffer.readline for faster I/O.

• Python handles arbitrary-precision integers safely, but in other languages, \(AP\) or \(AQ\) may exceed 64 bits, so be careful (this problem guarantees the final result is at most \(10^{18}\), but intermediate values can grow larger).

  Source Code

import sys
import math

def main():
    input = sys.stdin.buffer.readline
    gcd = math.gcd

    N = int(input())
    A, B = map(int, input().split())  # already reduced

    for _ in range(N - 1):
        P, Q = map(int, input().split())  # already reduced

        den = gcd(A * Q, B * P)
        num = A * P

        g = gcd(num, den)
        A = num // g
        B = den // g

    print(A, B)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.