実は、 既約分数 \(\frac{A}{B},\frac{C}{D}\) に対して

\[\mathrm{lcm}\left(\frac{A}{B},\frac{C}{D}\right)=\frac{\mathrm{lcm}(A,C)}{\mathrm{gcd}(B,D)}\]

が成り立ち、右辺は既約分数となります。

証明はこの解説の後半に載せます。

この事実を認めれば実装は容易です。右辺が既約であることから、与えられる分数・最終的な LCM の分子分母がともに \(10^{18}\) に収まるなら、計算過程でも収まることが示せます。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n;
  cin >> n;

  auto lcm=[&](long long x, long long y){
    return x / __gcd(x, y) * y;
  };

  long long nume = 1, deno = 0;
  for(int i=0; i<n; i++){
    long long p, q;
    cin >> p >> q;
    nume = lcm(nume, p);
    deno = __gcd(deno, q);
  }
  cout << nume << ' ' << deno << endl;
}

実装例 (Python)

import math
N = int(input())

nume, deno = 1, 0
for _ in range(N):
  p, q = map(int, input().split())
  nume = math.lcm(nume, p)
  deno = math.gcd(deno, q)

print(nume, deno)

証明

STEP1：整数に対する \(p\) 進付値

1-1. 正整数 \(n\) と素数 \(p\) に対して、 \(n\) が \(p\) で何回割り切れるかを \(v_p(n)\) と表す。

1-2. 定義より、全ての正整数 \(n\) と全ての素数 \(p\) に対し \(v_p(n) \geq 0\) である。

1-3. 素因数分解の一意性より、正整数 \(n,m\) について、全ての素数 \(p\) で \(v_p(n)=v_p(m)\) であるならば、\(n=m\) である。

1-4. 定義より、正整数 \(n,m\) に対し \(v_p(nm)=v_p(n)+v_p(m)\) が成り立つ。

STEP2： \(p\) 進付値と gcd, lcm

2-1. 正整数\(n\) が正整数 \(m\) の倍数であることは、全ての \(p\) で \(v_p(n)\geq v_p(m)\) であることと同値。

• 証明： \(n\) が \(m\) の倍数であるとき、正整数 \(d\) を用いて \(n=dm\) と表せるため、1-2, 1-4 より \(v_p(n)=v_p(d)+v_p(m)\geq 0+v_p(m)\)

2-2. 正整数 \(n,m\) に対し、全ての素数 \(p\) で \(v_p(\mathrm{lcm}(n,m))=\max(v_p(n),v_p(m))\) である。

• 証明：全ての \(p\) で \(v_p(L)=\max(v_p(n),v_p(m))\) となる \(L\) をとる。2-1 より、\(L\) は \(n,m\) の公倍数である。逆に \(n,m\) の公倍数 \(L'\) は、全ての素数 \(p\) で \(v_p(L')\geq \max(v_p(n),v_p(m))=v_p(L)\) を満たすので、 \(L\) の倍数である。よって最小性から \(L=\mathrm{lcm}(n,m)\) となる。

2-3. 正整数 \(n,m\) に対し、全ての素数 \(p\) で \(v_p(\mathrm{gcd}(n,m))=\min(v_p(n),v_p(m))\) である。

• 証明： 2-2 と同様

STEP3：有理数に対する \(p\) 進付値

3-1. 有理数 \(\frac{a}{b}\) と素数 \(p\) に対し \(v_p(\frac{a}{b})=v_p(a)-v_p(b)\) と定める。これは \(a,b\) の取り方に依らないことが示せる。

• 証明：\(\frac{a}{b}=\frac{c}{d}\) ならば \(v_p(a)-v_p(b)=v_p(c)-v_p(d)\) であることを示せば良い。仮定から \(bc=ad\) なので 1-4 より \(v_p(b)+v_p(c)=v_p(a)+v_p(d)\) が成立。よって示せた。

3-2. 有理数 \(x\) について、全ての素数 \(p\) で \(v_p(x) \geq 0\) であることと、 \(x\) が整数であることは同値。

• 証明：整数⇒\(v_p(x)\geq 0\) は 1-2 より明らか。\(x\) が整数でないと仮定し、その既約分数表現を \(\frac{a}{b}\) とする。 \(b\) の素因数 \(p\) を任意にとると、定義より \(v_p(x)=v_p(a)-v_p(b) \leq 0-1\)

3-3. 定義より、有理数 \(x,y\) に対し \(v_p(xy)=v_p(x)+v_p(y)\) が成り立つ

3-4. 1-3 及び 3-3より、有理数 \(x,y\) について、全ての素数 \(p\) で \(v_p(x)=v_p(y)\) であるならば、 \(x=y\) である。

3-5. 有理数 \(x\) が有理数 \(y\) の倍数であることを、\(\frac{x}{y}\) が整数であることと定める。

3-6. 有理数 \(x\) が有理数 \(y\) の倍数であることは、全ての \(p\) で \(v_p(x)\geq v_p(y)\) であることと同値。

• 証明：仮定の下、3-3 より \(v_p(x)-v_p(y)=v_p\left(\frac{x}{y}\right) \geq 0\) なので 3-2 より \(\frac{x}{y}\) は整数であり、定義 3-5 より \(x\) は \(y\) の倍数となる。

STEP4：有理数に対する \(p\) 進付値と 有理数に対する lcm

4-1. 有理数 \(x.y\) の最小公倍数を、問題文中の定義通り \(\mathrm{lcm}(x,y)=\min\{L\in\mathbb{Q}\mid \frac{L}{x}, \frac{L}{y}\in\mathbb{Z}\}\) と定める。

4-2. 有理数 \(x,y\) に対して \(v_p(\mathrm{lcm}(x,y))=\max(v_p(x),v_p(y))\) が成立。

• 証明：3-6 を用いて 2-2 と同様に示せる

STEP5：本題の証明

既約分数 \(\frac{A}{B},\frac{C}{D}\) に対して \(\mathrm{lcm}\left(\frac{A}{B},\frac{C}{D}\right)=\frac{\mathrm{lcm}(A,C)}{\mathrm{gcd}(B,D)}\) が成り立つ。さらに右辺は既約。

証明：
等式の成立を示す。 3-4, 4-2 より、全ての \(p\) で \(\max(v_p(A/B),v_p(C/D))=\max(v_p(A),v_p(C))-\min(v_p(B),v_p(D))\) が成り立つことを示せば良い。以下、\(v_p(A)=a\) などのように略記する。
\(\frac{A}{B},\frac{C}{D}\) が既約なので 2-3 より \(\min(a,b)=\min(c,d)=0\) となるため、示すべきことは 「\(\min(a,b)=\min(c,d)=0\) のとき、\(\max(a-b,c-d)=\max(a,c)-\min(b,d)\) が成り立つ」である。
これは、\(a,c\) がそれぞれ \(0\) であるかどうか4通りをそれぞれ調べることで示せる。既約性についても同様。