Overview

Given \(N\) firework launchers with launch intervals expressed as irreducible fractions, the problem asks to find the earliest time after time 0 when all launchers fire simultaneously (i.e., the least common multiple).

Analysis

Each launcher \(i\) has a launch interval \(T_i = \frac{P_i}{Q_i}\) (given as an irreducible fraction). The earliest time \(L\) after time 0 when all launchers fire simultaneously can be found using the definition of the least common multiple for rational numbers.

The key observation is that the least common multiple of rational numbers can be computed as \(\text{LCM}(P_1, P_2, \ldots, P_N) / \text{GCD}(Q_1, Q_2, \ldots, Q_N)\). This can be explained as follows:

When \(L = \frac{A}{B}\) is the least common multiple, for every \(i\), \(L / T_i = \frac{A}{B} \times \frac{Q_i}{P_i}\) must be an integer. The smallest such \(L\) is achieved by taking the LCM of all \(P_i\) as the numerator and the GCD of all \(Q_i\) as the denominator.

Algorithm

1. Compute the least common multiple (LCM) of all \(P_i\)
2. Compute the greatest common divisor (GCD) of all \(Q_i\)
3. Compute \(L = \text{LCM}(P_i) / \text{GCD}(Q_i)\)
4. Reduce the resulting fraction and output it in irreducible fraction form

The LCM is computed iteratively: find the GCD of the current LCM value and the next \(P_i\), then multiply the current LCM value by \(P_i\) and divide by that GCD. The GCD is computed by sequentially applying the GCD operation.

Complexity

• Time complexity: \(O(N \log M)\)
  • \(M\) is the maximum value among \(P_i, Q_i\) (approximately \(10^9\))
  • Each step requires \(O(\log M)\) for the GCD computation
• Space complexity: \(O(N)\)
  • Space needed to store the input data

Implementation Notes

• Since the inputs are given as irreducible fractions, no initial reduction is needed

• Intermediate values during LCM computation can become large, but the problem constraints guarantee that the answer fits within \(10^{18}\)

• The final fraction \(\frac{A}{B}\) may not necessarily be irreducible, so it must be reduced by dividing by the GCD

• Efficiently utilize Python’s math.gcd function

  Source Code

import math
import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    n = int(data[0])
    fractions = []
    index = 1
    for i in range(n):
        P = int(data[index])
        Q = int(data[index+1])
        index += 2
        fractions.append((P, Q))
    
    # 各分数を約分済みなので、分母のLCMと分子のGCDを求める
    # まず、各分数 T_i = P_i / Q_i を考える
    # 求めるLは、各iについて L / T_i = L * (Q_i / P_i) が整数
    # つまり、L * Q_i / P_i が整数 → L * Q_i が P_i で割り切れる
    
    # 別のアプローチ: 分数のLCMは、分子のLCM / 分母のGCD として定義できる
    # ただし、ここでの分子は元の分数の分子、分母は元の分数の分母
    
    # 実際: L = LCM(P_i) / GCD(Q_i) ではない
    # 正しい方法: 各分数を既約分数で表したとき、最小公倍数Lは
    # L = LCM(P_i) / GCD(Q_i) とは限らない
    
    # 標準的な方法: 各分数 T_i = a_i / b_i (既約) とする
    # L が T_i の公倍数である ⇔ L * b_i / a_i が整数
    # つまり、L は a_i で割り切れ、かつ b_i で割り切れるような数? ではない
    
    # 実際には: L = LCM( a_i ) / GCD( b_i ) は間違い
    # 代わりに: 各分数を素因数分解して考えるのが確実だが、制約が大きい
    
    # 別のアイデア: L = LCM( P_i ) / GCD( Q_i ) は間違っている例がある
    # 正解は: 各 i について、L = k_i * T_i (k_iは整数) なので、
    # L = (LCM_{i} (P_i) ) / (GCD_{i} (Q_i)) ではない
    
    # 実際の正しい解法:
    # 各分数 T_i = P_i / Q_i を既約分数で表す（入力は既約なのでそのまま）
    # 最小公倍数 L は、分子が各T_iの分子の最小公倍数、分母が各T_iの分母の最大公約数
    # つまり、L = LCM(P_i) / GCD(Q_i)  で本当に正しいのか？
    # しかし、これは有理数の最小公倍数の定義として正しいことが知られている
    
    # 確認: 定義より、L / T_i = L * (Q_i / P_i) が整数
    # L = LCM(P_i) / GCD(Q_i) とすると、
    # L / T_i = [LCM(P_i) / GCD(Q_i)] * [Q_i / P_i] = [LCM(P_i) * Q_i] / [GCD(Q_i) * P_i]
    # これが整数であるためには、分母が分子を割り切る必要がある
    # 実際、GCD(Q_i) は各 Q_i の約数なので、Q_i / GCD(Q_i) は整数
    # また、P_i は LCM(P_i) の約数なので、LCM(P_i) / P_i は整数
    # したがって、全体は整数になる
    
    # また、これが最小であることも証明できる
    
    # したがって、L = LCM(P_i) / GCD(Q_i) が正解
    
    # ただし、注意点: LCM(P_i) と GCD(Q_i) を計算するとき、数が非常に大きくなる可能性がある
    # 制約: n<=200000, P_i, Q_i<=10^9
    # 答えの分子分母は10^18以下に収まることが保証されている
    
    # まず、すべてのP_iのLCMを計算する
    lcm_p = 1
    gcd_q = 0
    
    for i, (P, Q) in enumerate(fractions):
        if i == 0:
            gcd_q = Q
        else:
            gcd_q = math.gcd(gcd_q, Q)
        
        g = math.gcd(lcm_p, P)
        lcm_p = lcm_p * P // g
        
        # 途中でlcm_pが10^18を超えたら、それ以上計算する必要はない?
        # ただし、答えの分子はlcm_pであり、10^18以下であることが保証されているので、超えることはない
        # しかし、計算途中では超える可能性がある? 実際、保証されているので大丈夫
    
    A = lcm_p
    B = gcd_q
    
    # ただし、これで得られた分数 A/B は既約とは限らない
    g = math.gcd(A, B)
    A //= g
    B //= g
    
    print(f"{A} {B}")

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.