Stern-Brocot 木がちょうどよく使える

問題へのリンク

問題概要

正の整数 $P, N$ が与えられる。分子・分母がともに $N$ 以下の正の整数であって、既約分数であるような分数の集合を $Q_{N}$ と表すことにする。

$\frac{x}{y} \lt \sqrt P$ を満たす最大の $Q_{N}$ の要素 $\frac{x}{y}$
$\sqrt P \lt \frac{x}{y}$ を満たす最小の $Q_{N}$ の要素 $\frac{x}{y}$

をそれぞれ求めよ。

制約

$1 \le P, N \le 10^{4}$
$N \gt \sqrt{P}$ (解の存在が保証される)

考えたこと

単純な解法としては、分母を固定して分子の値を二分探索する方法が考えられる。それで十分通せる。

しかし、Stern-Brocot 木を知っていればかなり楽に通せる。Stern-Brocot 木とは、下図 (ここ引用) のように

すべての既約分数がちょうど一度ずつ現れる
扱う既約分数は単調増加である
より深い既約分数は、分子または分母の値がより大きい

という特徴がある。今回の問題にはピッタリである。

f:id:drken1215:20201220223732p:plain

通常はこんな感じの実装でできる。

void SternBrocot(long long N, long long sl = 0, long long bl = 1, long long sr = 1, long long br = 0) {
    long long s = sl + sr, b = bl + br;
    if (s > N || b > N) return;

    // left
    SternBrocot(N, sl, bl, s, b);

    // consider s/b (monotone increasing)
    {

    }

    // right
    SternBrocot(N, s, b, sr, br);
}

ただし今回は高速化のため

$\frac{s}{b} \lt \sqrt{P}$ のときは、左側の探索を枝刈りする
$\frac{s}{b}$ は単調増加で登場するので、初めて $\sqrt{P}$ を超えた時点で探索を打ち切る

という工夫を実施した。

コード

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

long long P;
long long x, y, u, v;
bool exist_bigger = false;

// consider s/b
void SternBrocot(long long N, long long sl = 0, long long bl = 1, long long sr = 1, long long br = 0) {
    long long s = sl + sr, b = bl + br;
    if (s > N || b > N) return;

    // left (only when bigger case)
    if (s*s > b*b*P) SternBrocot(N, sl, bl, s, b);

    // consider s/b (monotone increasing)
    {
        if (s*s < b*b*P) u = s, v = b;
        else {
            if (!exist_bigger) x = s, y = b, exist_bigger = true;
            return;
        }
    }

    // right
    SternBrocot(N, s, b, sr, br);
}

int main() {
    long long N;
    while (cin >> P >> N, P) {
        exist_bigger = false;
        SternBrocot(N);
        cout << x << "/" << y << " " << u << "/" << v << endl;
    }
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 1208 Rational Irrationals (ICPC アジア 1999 A)

問題概要

制約

考えたこと

コード