Day 027-Q1 — Stern-Brocot Tree（連分数・ファレイ数列・最近分数探索）

2026-05-10 赤色 Master / Phase 8+ ★★★★★★★★★ Stern-Brocot Tree

問題

整数 $P$, $Q$（$1 \leq Q \leq P \leq 10^{18}$, $\gcd(P, Q) = 1$）が与えられる。分母が $N$（$1 \leq N \leq 10^9$）以下の既約分数の中で、$P/Q$ に最も近い分数 $a/b$（$a/b \neq P/Q$ かつ $b \leq N$）を求めよ。複数存在する場合は分母が最小のもの、さらに同じなら $P/Q$ より小さい方を答えよ。

入力形式

P Q N

制約

$1 \leq Q \leq P \leq 10^{18}$
$\gcd(P, Q) = 1$
$1 \leq N \leq 10^9$

入出力例

入力例 1

5 3 10

出力例 1

7 4

入力例 2

1000000007 1000000006 1000000005

出力例 2

999999999 999999999

ヒント (段階的開示)

ヒント1: 方向性
Stern-Brocot Tree は有理数の木構造で、すべての既約正分数を一意に含む。根から目標分数までのパスを辿ることで、分母 $N$ 以下の最近分数候補が特定できる。
ヒント2: アプローチ
Stern-Brocot 探索の各ステップで「メジアント」$(a+c)/(b+d)$ を計算し、目標との大小比較でどちらの子に進むか決定する。分母が $N$ を超えた瞬間に探索を打ち切り、その時点の左・右境界を候補とする。連分数展開とほぼ等価で $O(\log \min(P,Q))$ ステップ。
ヒント3: 誘導 
def stern_brocot_nearest(P, Q, N):
    lo_num, lo_den = 0, 1
    hi_num, hi_den = 1, 0  # 無限大を表す
    best = None

    while True:
        med_num = lo_num + hi_num
        med_den = lo_den + hi_den
        if med_den > N:
            break
        if med_num * Q < P * med_den:   # med < P/Q
            lo_num, lo_den = med_num, med_den
        elif med_num * Q > P * med_den: # med > P/Q
            hi_num, hi_den = med_num, med_den
        else:
            ...

模範解答 (Python)

import math
import sys
input = sys.stdin.readline

def solve():
    P, Q, N = map(int, input().split())

    def dist2(a, b, p, q):
        return abs(a * q - p * b), b * q

    lo_n, lo_d = 0, 1
    hi_n, hi_d = 1, 0

    candidates = []

    while True:
        med_n = lo_n + hi_n
        med_d = lo_d + hi_d

        if med_d > N:
            if lo_d > 0:
                k = (N - lo_d) // hi_d if hi_d > 0 else 0
                if k > 0:
                    cand_n = lo_n + k * hi_n
                    cand_d = lo_d + k * hi_d
                    if cand_d <= N and not (cand_n * Q == P * cand_d):
                        candidates.append((cand_n, cand_d))
            if hi_d > 0 and hi_d <= N:
                if not (hi_n * Q == P * hi_d):
                    candidates.append((hi_n, hi_d))
            if lo_d <= N:
                if not (lo_n * Q == P * lo_d):
                    candidates.append((lo_n, lo_d))
            break

        cmp = med_n * Q - P * med_d
        if cmp < 0:
            lo_n, lo_d = med_n, med_d
        elif cmp > 0:
            hi_n, hi_d = med_n, med_d
        else:
            if lo_d <= N and lo_d > 0:
                candidates.append((lo_n, lo_d))
            if hi_d <= N and hi_d > 0:
                candidates.append((hi_n, hi_d))
            break

    def key_func(ab):
        a, b = ab
        diff_num = abs(a * Q - P * b)
        diff_den = b * Q
        return (diff_num, diff_den, b, -a * Q + P * b)

    candidates = [(a, b) for a, b in candidates if b >= 1]
    candidates.sort(key=key_func)

    if not candidates:
        if P >= Q:
            print(P // Q, 1)
        else:
            print(0, 1)
        return

    ans_a, ans_b = candidates[0]
    print(ans_a, ans_b)

solve()

Step-by-Step 解説

1Stern-Brocot Tree の構造
Stern-Brocot Tree はすべての正の既約分数を一度ずつ含む無限二分木。根: $1/1$。各ノード $(a+c)/(b+d)$（メジアント）は左の子 $a/b$ と右の子 $c/d$ から生成。分数 $P/Q$ を探すには根から左右を比較しながら降りていく。
2分母制約での打ち切り
メジアントの分母 $b+d > N$ になったら、これ以上進めない。その時点の $lo$ と $hi$ が最近候補。計算量は連分数展開と同等で $O(\log \max(P, Q))$。
3連分数加速
通常の Stern-Brocot は連分数の各係数分だけ同じ方向に進む。一方向に $k$ ステップ進む場合、直接 $k$ を計算することで加速できる（Euclid の互除法と同じ）。k = (N - lo_d) // hi_d。
4候補の比較
複数候補を |a/b - P/Q|（= |a*Q - P*b| / (b*Q)）で比較。同距離の場合は分母が小さい方、さらに同じなら $P/Q$ より小さい方を選ぶ。

よくあるミス

ミス原因正しい書き方
P/Q 自体を答えに含める問題文に「$a/b \neq P/Q$」とあるcmp == 0 の場合は隣接項のみ追加
分母比較で int オーバーフローC++ など固定精度の場合__int128 や多倍長整数を使う
メジアントの計算を毎回行う$O(P+Q)$ になる連分数加速で $O(\log \max(P,Q))$ に
候補が空になるN=1 や境界処理漏れ0/1 と floor(P/Q)/1 を必ず候補に

次のステップ

  • 発展問題: 分母 $N$ 以下の分数全列挙（Farey 数列）を $O(N)$ で構築し、指定範囲内の個数を求めよ

自己評価

自分の回答

気づき・メモ