test/aoj/1208.test.cpp

View this file on GitHub
Last update: 2024-01-08 17:31:43+09:00
Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1208

Depends on

Stern-Brocot Tree (math/number-theory/stern_brocot_tree.hpp)

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1208"

#include "../../math/number-theory/stern_brocot_tree.hpp"

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);

    while (true) {
        int p, n;
        cin >> p >> n;
        if (p == 0 && n == 0) break;
        auto ans = stern_brocot_tree_search(n, [&](ll a, ll b) {
            return a * a < p * b * b;
        });
        auto [u, v] = ans.first;
        auto [x, y] = ans.second;
        cout << x << "/" << y << " " << u << "/" << v << endl;
    }
}

#line 1 "test/aoj/1208.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1208"

#line 2 "math/number-theory/stern_brocot_tree.hpp"
#include <utility>

/**
 * @brief Stern Brocot Tree
 */
template <typename F>
std::pair<std::pair<long long, long long>, std::pair<long long, long long>>
stern_brocot_tree_search(long long n, F cond) {
    long long a = 0, b = 1, c = 1, d = 0;
    while (true) {
        long long num = a + c, den = b + d;
        if (num > n || den > n) break;
        if (cond(num, den)) {
            long long k = 2;
            while ((num = a + c * k) <= n && (den = b + d * k) <= n &&
                   cond(num, den))
                k *= 2;
            k /= 2;
            a += c * k;
            b += d * k;
        } else {
            long long k = 2;
            while ((num = a * k + c) <= n && (den = b * k + d) <= n &&
                   !cond(num, den))
                k *= 2;
            k /= 2;
            c += a * k;
            d += b * k;
        }
    }
    return {{a, b}, {c, d}};
}
#line 4 "test/aoj/1208.test.cpp"

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);

    while (true) {
        int p, n;
        cin >> p >> n;
        if (p == 0 && n == 0) break;
        auto ans = stern_brocot_tree_search(n, [&](ll a, ll b) {
            return a * a < p * b * b;
        });
        auto [u, v] = ans.first;
        auto [x, y] = ans.second;
        cout << x << "/" << y << " " << u << "/" << v << endl;
    }
}