概要

各装置の周期 \(T_i=\frac{P_i}{Q_i}\)（既約）に対し、時刻 \(0\) 以降で全装置が同時に打ち上がる最初の時刻は、これら有理数の最小公倍数 \(L\) です。\(L\) を既約分数で求めます。

考察

重要な気づき

整数の最小公倍数と同様に、有理数でも「ある有理数 \(L\) がすべての \(T_i\) の整数倍になる」ような最小の \(L\) を求めればよいです。

ここで \(T_i\) は分数なので、浮動小数で扱うと誤差で壊れます（例：\(1/3\) は有限桁で表せない）。よって分数のまま計算します。

素朴解がダメな理由

• 時刻を順にシミュレーションする：周期が分数なので刻み幅が難しく、最悪いつ一致するか非常に遅い（TLE）。
• 分母を全部そろえるために \(D=\mathrm{lcm}(Q_i)\) を直接作る：\(D\) が巨大になりやすく、途中計算が破綻（オーバーフローや計算が重い）。

解決策

2つの分数の最小公倍数を、最大公約数（gcd）だけで計算できる公式を使い、それを順に畳み込み（\(N\) 個を1つに統合）します。

アルゴリズム

2つの既約分数 [ x=\frac{a}{b},\quad y=\frac{c}{d} ] の最小公倍数を求めます。

\(L\) が公倍数である条件は [ \frac{L}{x}=\frac{Lb}{a}\in \mathbb{Z}{>0},\quad \frac{L}{y}=\frac{Ld}{c}\in \mathbb{Z}{>0} ] です。つまり \(L\) は [ L=\frac{a}{b}\cdot k=\frac{c}{d}\cdot m \quad (k,m\in\mathbb{Z}_{>0}) ] と書けます。

ここで次の形を考えます： [ L=\frac{ac}{g} ] このとき [ \frac{L}{a/b}=\frac{ac/g}{a/b}=\frac{bc}{g},\quad \frac{L}{c/d}=\frac{ac/g}{c/d}=\frac{ad}{g} ] となるので、\(\frac{bc}{g}\) と \(\frac{ad}{g}\) が整数なら \(L\) は公倍数です。
つまり \(g\) は \(ad\) と \(bc\) の共通の約数であればよく、\(L\) を最小にするには \(g\) を最大にすればよいので [ g=\gcd(ad,\,bc) ] を選ぶのが最適です。よって [ \mathrm{lcm}!\left(\frac{a}{b},\frac{c}{d}\right)=\frac{ac}{\gcd(ad,bc)} ] （最後に既約化）で求まります。

本問題ではこれを左から順に適用します： - 現在の答えを \(\frac{A}{B}\) - 次の周期を \(\frac{P}{Q}\) として [ \text{den}=\gcd(AQ,\,BP),\quad \text{num}=AP,\quad L=\frac{\text{num}}{\text{den}} ] を作り、最後に \(\gcd(\text{num},\text{den})\) で既約化して次の \((A,B)\) にします。

（例）\(\frac{1}{2}\) と \(\frac{1}{3}\)
\(\gcd(1\cdot 3,2\cdot 1)=\gcd(3,2)=1\) より \(L=\frac{1\cdot 1}{1}=1\)。確かに最初の同時刻は \(1\) 秒です。

計算量

• 時間計算量: \(O(N \log M)\)（各ステップで gcd を数回。\(M\) は数の大きさ）
• 空間計算量: \(O(1)\)（答えの分子分母のみ保持）

実装のポイント

• 必ず整数（分子分母）で持ち、浮動小数を使わない（誤差で WA）。

• 各ステップで \(\gcd\) により既約化しておくと数が無駄に大きくなりにくい。

• 入力サイズが大きいので sys.stdin.buffer.readline を使って高速化する。

• Python は多倍長整数で安全だが、他言語では \(AP\) や \(AQ\) が 64bit を超える可能性があるため注意（この問題は最終結果は \(10^{18}\) 以下保証だが途中は増えうる）。

  ソースコード

import sys
import math

def main():
    input = sys.stdin.buffer.readline
    gcd = math.gcd

    N = int(input())
    A, B = map(int, input().split())  # already reduced

    for _ in range(N - 1):
        P, Q = map(int, input().split())  # already reduced

        den = gcd(A * Q, B * P)
        num = A * P

        g = gcd(num, den)
        A = num // g
        B = den // g

    print(A, B)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。