概要

複数の周期で動作する花火発射装置について、すべてが再び同時に花火を打ち上げる最も早い時刻を求める問題です。これは、与えられた有理数の最小公倍数を求めることに対応します。

考察

各発射装置 \(i\) は周期 \(T_i = \frac{P_i}{Q_i}\) で花火を打ち上げます。すべての装置が同時に打ち上げる時刻は、すべての \(T_i\) の公倍数となっています。その中で最も早い時刻は、最小公倍数 \(L\) です。

ここで重要なのは、有理数の最小公倍数の求め方です。一般に、分数の最小公倍数は以下のように求めることができます：

\[ \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)} \]

この公式により、すべての分子の最小公倍数をとり、すべての分母の最大公約数を取ることで、答えの分数を得ることができます。この分数はまだ約分できる可能性があるため、最後に分子と分母の最大公約数で割って既約分数にします。

この方法を使うことで、各周期の分数を逐一通分したり比較したりすることなく、効率的に最小公倍数を求めることができます。

アルゴリズム

1. 各分数の分子 \(P_i\) と分母 \(Q_i\) を読み込む。
2. すべての分子の最小公倍数（LCM）を求める。
3. すべての分母の最大公約数（GCD）を求める。
4. 結果の分数 \(\frac{\mathrm{LCM}}{\mathrm{GCD}}\) を計算し、さらにその分子と分母の最大公約数で約分して既約分数にする。
5. 最終的な分子と分母を出力する。

Pythonの functools.reduce を使うことで、複数の数の GCD や LCM を効率的に計算できます。

計算量

• 時間計算量: \(O(N \log(\max(P_i, Q_i)))\)
  • 各 GCD/LCM の計算が \(O(\log(\max(P_i, Q_i)))\) で、それが \(N\) 回程度行われる。
• 空間計算量: \(O(N)\)
  • 分子・分母をリストで保持するため。

実装のポイント

• 分子の LCM と分母の GCD を別々に計算するのがポイント。

• Python の math.gcd と自前での lcm 関数を組み合わせて使用。

• 最後に得られた分数は必ず既約分数にするために、再度 GCD で割っている。

• 入力が大きいので、int 型の範囲に注意（Python では自動的に多倍長整数になるため問題なし）。

  ソースコード

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

この解説は qwen3-coder-480b によって生成されました。