概要

\(N\) 個の正の有理数 \(T_1, T_2, \ldots, T_N\)（既約分数で与えられる）の最小公倍数（LCM）を既約分数として求める問題です。

考察

整数の LCM から有理数の LCM へ

整数の最小公倍数は馴染み深いですが、有理数の最小公倍数はどう計算すればよいでしょうか？

まず定義を確認します。正の有理数 \(L\) が \(T_1, T_2, \ldots, T_N\) の公倍数であるとは、すべての \(i\) に対して \(\frac{L}{T_i}\) が正の整数であることです。その中で最小のものが LCM です。

重要な公式

既約分数で表された2つの有理数 \(\frac{a}{b}\) と \(\frac{c}{d}\)（ただし \(\gcd(a,b)=1\), \(\gcd(c,d)=1\)）に対して、次の公式が成り立ちます：

\[\mathrm{lcm}\!\left(\frac{a}{b},\, \frac{c}{d}\right) = \frac{\mathrm{lcm}(a, c)}{\gcd(b, d)}\]

公式の直感的な理解

分子の LCM を取ることで「両方の分子の倍数」になるようにし、分母の GCD を取ることで「両方の分母で割り切れる最大の分母」を維持します。

具体例で確認

• \(\mathrm{lcm}\!\left(\frac{1}{2},\, \frac{1}{3}\right) = \frac{\mathrm{lcm}(1,1)}{\gcd(2,3)} = \frac{1}{1} = 1\)
  • 検証: \(\frac{1}{1/2} = 2\) ✓、\(\frac{1}{1/3} = 3\) ✓
• \(\mathrm{lcm}\!\left(\frac{2}{3},\, \frac{4}{5}\right) = \frac{\mathrm{lcm}(2,4)}{\gcd(3,5)} = \frac{4}{1} = 4\)
  • 検証: \(\frac{4}{2/3} = 6\) ✓、\(\frac{4}{4/5} = 5\) ✓

N 個への拡張

LCM は結合的なので、左から順に2つずつ LCM を取っていけば全体の LCM が求まります。ただし、各ステップで結果を既約分数に約分する必要があります（公式が既約分数を前提としているため）。

アルゴリズム

1. 結果を \(\frac{A}{B} = \frac{P_1}{Q_1}\) で初期化する（入力が既約なのでそのまま使える）。
2. \(i = 2, 3, \ldots, N\) に対して、以下を繰り返す：
   • 新しい分子: \(A' = \mathrm{lcm}(A, P_i)\)
   • 新しい分母: \(B' = \gcd(B, Q_i)\)
   • \(g = \gcd(A', B')\) で約分して \(A = A'/g\), \(B = B'/g\) とする。
3. 最終的な \(A\) と \(B\) を出力する。

ここで \(\mathrm{lcm}(a, b) = \frac{a}{\gcd(a,b)} \times b\) として計算します（オーバーフロー対策で先に割る）。

計算量

• 時間計算量: \(O(N \log V)\)（\(V\) は値の上限、各ステップで GCD 計算が \(O(\log V)\)）
• 空間計算量: \(O(1)\)（入力を除けば定数個の変数のみ）

実装のポイント

• 既約分数の維持: 公式は両方の入力が既約分数であることを前提とするため、LCM を計算するたびに \(\gcd\) で約分して既約に保つ必要があります。

• オーバーフロー対策: lcm(A, P) の計算時に \(A \times P\) が非常に大きくなる可能性があるため、a // gcd(a, b) * b の順序で計算します。Python は多倍長整数なのでオーバーフローは起きませんが、C++ などでは注意が必要です。

• 入力の高速化: \(N\) が最大 \(2 \times 10^5\) なので、sys.stdin.buffer.read() でまとめて読み込むことで高速化しています。

  ソースコード

import sys
from math import gcd

def lcm(a, b):
    return a // gcd(a, b) * b

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    
    # T_i = P_i / Q_i
    # LCM of rationals: lcm(P1/Q1, P2/Q2) = lcm(P1,P2) / gcd(Q1,Q2)
    
    num = 1  # numerator of result (LCM of all P_i)
    den = 1  # denominator of result (GCD of all Q_i) -- wait, not exactly
    
    # More carefully:
    # LCM(a/b, c/d) = LCM(a,c) / GCD(b,d)
    # But we need to keep it in reduced form as we go to avoid issues.
    
    # Actually, let's think about it differently.
    # Result = A/B in reduced form.
    # We accumulate: start with A=P1, B=Q1 (reduced).
    # Then LCM(A/B, P_i/Q_i) = LCM(A, P_i) / GCD(B, Q_i)... 
    # Wait, this formula works for any two positive rationals, not just reduced ones?
    
    # The formula: For positive rationals r1 = a/b, r2 = c/d (in lowest terms),
    # LCM(r1, r2) = LCM(a,c) / GCD(b,d)
    # This is a known result. Let me verify:
    # LCM(1/2, 1/3) = LCM(1,1)/GCD(2,3) = 1/1 = 1. Check: 1/(1/2)=2 ✓, 1/(1/3)=3 ✓. Good.
    # LCM(2/3, 4/5) = LCM(2,4)/GCD(3,5) = 4/1 = 4. Check: 4/(2/3)=6 ✓, 4/(4/5)=5 ✓. Good.
    
    # But we need both fractions to be in lowest terms for this formula to work.
    # So after each step, we should reduce.
    
    A = int(input_data[idx]); idx += 1
    B = int(input_data[idx]); idx += 1
    # A/B is already in lowest terms per problem statement
    
    for i in range(1, N):
        P = int(input_data[idx]); idx += 1
        Q = int(input_data[idx]); idx += 1
        
        # LCM(A/B, P/Q) = LCM(A,P) / GCD(B,Q), then reduce
        new_A = lcm(A, P)
        new_B = gcd(B, Q)
        
        g = gcd(new_A, new_B)
        A = new_A // g
        B = new_B // g
    
    print(A, B)

main()

---

この解説は claude4.6opus-thinking によって生成されました。