Overview

Given multiple firework launchers operating at different periods, we need to find the earliest time at which all launchers fire simultaneously again. This corresponds to finding the least common multiple of the given rational numbers.

Analysis

Each launcher \(i\) fires at a period of \(T_i = \frac{P_i}{Q_i}\). The times at which all launchers fire simultaneously are the common multiples of all \(T_i\). The earliest such time is the least common multiple \(L\).

The key insight here is how to compute the least common multiple of rational numbers. In general, the LCM of fractions can be computed as follows:

\[ \mathrm{LCM}\left( \frac{a_1}{b_1}, \frac{a_2}{b_2}, \ldots, \frac{a_n}{b_n} \right) = \frac{\mathrm{LCM}(a_1, a_2, \ldots, a_n)}{\mathrm{GCD}(b_1, b_2, \ldots, b_n)} \]

Using this formula, we can obtain the resulting fraction by taking the LCM of all numerators and the GCD of all denominators. Since this fraction may not yet be in lowest terms, we finally divide both the numerator and denominator by their GCD to reduce it to an irreducible fraction.

By using this method, we can efficiently compute the LCM without having to find common denominators or compare individual periodic fractions one by one.

Algorithm

1. Read the numerator \(P_i\) and denominator \(Q_i\) of each fraction.
2. Compute the least common multiple (LCM) of all numerators.
3. Compute the greatest common divisor (GCD) of all denominators.
4. Compute the resulting fraction \(\frac{\mathrm{LCM}}{\mathrm{GCD}}\), then further reduce it to an irreducible fraction by dividing both the numerator and denominator by their GCD.
5. Output the final numerator and denominator.

By using Python’s functools.reduce, we can efficiently compute the GCD and LCM over multiple numbers.

Complexity

• Time complexity: \(O(N \log(\max(P_i, Q_i)))\)
  • Each GCD/LCM computation takes \(O(\log(\max(P_i, Q_i)))\), and this is performed approximately \(N\) times.
• Space complexity: \(O(N)\)
  • Because the numerators and denominators are stored in lists.

Implementation Notes

• The key point is to compute the LCM of the numerators and the GCD of the denominators separately.

• We combine Python’s math.gcd with a custom lcm function.

• The resulting fraction is always reduced to an irreducible fraction by dividing by the GCD one final time.

• Since the input values can be large, care must be taken with int range (in Python this is not an issue since arbitrary-precision integers are handled automatically).

  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():
    N = int(input())
    fractions = []
    for _ in range(N):
        p, q = map(int, input().split())
        fractions.append((p, q))
    
    # LCM of fractions is given by:
    # LCM(a1/b1, a2/b2, ..., an/bn) = LCM(a1, a2, ..., an) / GCD(b1, b2, ..., bn)
    
    numerators = [f[0] for f in fractions]
    denominators = [f[1] for f in fractions]
    
    lcm_numerators = reduce(lcm, numerators)
    gcd_denominators = reduce(gcd, denominators)
    
    # Result is lcm_numerators / gcd_denominators in reduced form
    numerator = lcm_numerators
    denominator = gcd_denominators
    
    g = gcd(numerator, denominator)
    numerator //= g
    denominator //= g
    
    print(numerator, denominator)

if __name__ == "__main__":
    main()

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