概要

\(N\)個の花火発射装置の打ち上げ間隔が既約分数で与えられるので、すべての発射装置が時刻0以降で初めて同時に打ち上げる時刻（最小公倍数）を求める問題です。

考察

各発射装置\(i\)の打ち上げ間隔が\(T_i = \frac{P_i}{Q_i}\)（既約分数）で与えられます。時刻0以降で全てが同時に打ち上げる最も早い時刻\(L\)は、有理数に対する最小公倍数の定義により求められます。

重要な観察は、有理数の最小公倍数が\(\text{LCM}(P_1, P_2, \ldots, P_N) / \text{GCD}(Q_1, Q_2, \ldots, Q_N)\)で計算できることです。これは以下のように説明できます：

\(L = \frac{A}{B}\)が最小公倍数であるとき、任意の\(i\)について\(L / T_i = \frac{A}{B} \times \frac{Q_i}{P_i}\)が整数である必要があります。これを満たす最小の\(L\)として、分子にすべての\(P_i\)の最小公倍数、分母にすべての\(Q_i\)の最大公約数を取ることで達成できます。

アルゴリズム

1. すべての\(P_i\)の最小公倍数（LCM）を計算する
2. すべての\(Q_i\)の最大公約数（GCD）を計算する
3. \(L = \text{LCM}(P_i) / \text{GCD}(Q_i)\)を計算する
4. 得られた分数を約分して既約分数形式で出力する

最小公倍数の計算は、現在のLCM値と次の\(P_i\)のGCDを求め、現在のLCM値に\(P_i\)を掛けてGCDで割る操作を繰り返します。最大公約数は順次GCDを計算していきます。

計算量

• 時間計算量: \(O(N \log M)\)
  • \(M\)は\(P_i, Q_i\)の最大値（約\(10^9\)）
  • 各ステップでGCD計算に\(O(\log M)\)かかるため
• 空間計算量: \(O(N)\)
  • 入力データを格納するための空間

実装のポイント

• 入力は既約分数で与えられるため、約分処理は不要

• LCM計算の途中で数値が大きくなるが、問題の制約で答えは\(10^{18}\)以下に収まることが保証されている

• 最終的に得られた分数\(\frac{A}{B}\)が既約とは限らないため、GCDで約分する必要がある

• Pythonのmath.gcd関数を効率的に利用する

  ソースコード

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()

この解説は deepseekv3 によって生成されました。