sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#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; } }