AOJ 1208 Rational Irrationals

前のこどふぉの問題を解こうとしたら Stern-Brocot 木というのを考えるらしいので AOJ で練習してみました。
Spaghetti Source - Stern-Brocot 木

既約分数を探索するのに都合が良さそうですね。

問題

Rational Irrationals | Aizu Online Judge

解法

Stern Brocot 木を使います。もし, 対応する分数が sqrt(p) より小さかったらそれ以降は今調べている分数より大きな分数のみを調べれば良く, 対応する分数が sqrt(p) より大きかったらそれ以降は今調べている分数より小さな分数のみを調べれば良いです。

ll p, n;
ll x, y, v, u;

void SternBrocot(ll pl = 0, ll ql = 1, ll pr = 1, ll qr = 0) {
    ll pm = pl+pr, qm = ql+qr;
    if (pm > n || qm > n) return;
    if (p*qm*qm < pm*pm) {
        u = pm, v = qm;
        SternBrocot(pl, ql, pm, qm);
    } else if (p*qm*qm > pm*pm) {
        x = pm, y = qm;
        SternBrocot(pm, qm, pr, qr);
    } else {
        x = u = pm;
        y = v = qm;
    }
}

int main() {
    while (cin >> p >> n) {
        if (p == 0 && n == 0) break;
        SternBrocot();
        printf("%lld/%lld %lld/%lld\n", u, v, x, y);
    }
    return 0;
}