test/library_checker/number_theory/rational_approximation.test.cpp

View this file on GitHub
Last update: 2024-11-04 03:12:13+09:00
Problem: https://judge.yosupo.jp/problem/rational_approximation

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/rational_approximation"
#include <bits/stdc++.h>
using namespace std;

#include "../../../lib/math/rational_approximation.hpp"

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; cin >> T;
    while(T--){
        long long n, x, y; cin >> n >> x >> y;
        fraction<long long> f(x, y);
        auto [l, r] = rationalApproximation(n, f);
        if(f == l) r = l;
        cout << l.p << " " << l.q << " " << r.p << " " << r.q << "\n";
    }
}

#line 1 "test/library_checker/number_theory/rational_approximation.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/rational_approximation"
#include <bits/stdc++.h>
using namespace std;

#line 2 "lib/math/rational_approximation.hpp"

/**
 * @brief Rational Approximation (有理数近似)
 * @docs docs/math/rational_approximation.md
 */

#line 2 "lib/math/fraction.hpp"

/**
 * @brief Fraction
 * @docs docs/math/fraction.md
 */

template <typename T>
struct fraction{
    T p, q; // long long or BigInt
    fraction(T P = 0, T Q = 1) : p(P), q(Q){
        normalize();
    }
    void normalize(){
        T g = __gcd(p, q);
        p /= g, q /= g;
        if(q < 0) p *= -1, q *= -1;
    }
    inline bool operator==(const fraction &other) const {
        return p * other.q == other.p * q;
    }
    inline bool operator!=(const fraction &other) const {
        return p * other.q != other.p * q;
    }
    inline bool operator<(const fraction &other) const {
        return p * other.q < other.p * q;
    }
    inline bool operator<=(const fraction &other) const {
        return p * other.q <= other.p * q;
    }
    inline bool operator>(const fraction &other) const {
        return p * other.q > other.p * q;
    }
    inline bool operator>=(const fraction &other) const {
        return p * other.q >= other.p * q;
    }
    inline fraction operator+(const fraction &other) const { return fraction(p * other.q + q * other.p, q * other.q); }
    inline fraction operator-(const fraction &other) const { return fraction(p * other.q - q * other.p, q * other.q); }
    inline fraction operator*(const fraction &other) const { return fraction(p * other.p, q * other.q); }
    inline fraction operator/(const fraction &other) const { return fraction(p * other.q, q * other.p); }
    inline fraction &operator+=(const fraction &rhs) noexcept {
        *this = *this + rhs;
        return *this;
    }
    inline fraction &operator-=(const fraction &rhs) noexcept {
        *this = *this - rhs;
        return *this;
    }
    inline fraction &operator*=(const fraction &rhs) noexcept {
        *this = *this * rhs;
        return *this;
    }
    inline fraction &operator/=(const fraction &rhs) noexcept {
        *this = *this / rhs;
        return *this;
    }
    friend inline istream &operator>>(istream &is, fraction &x) noexcept {
        is >> x.p;
        x.q = 1;
        return is;
    }
    friend inline ostream &operator<<(ostream &os, const fraction &x) noexcept { return os << x.p << "/" << x.q; }
};
#line 9 "lib/math/rational_approximation.hpp"

template <typename T>
pair<fraction<T>, fraction<T>> rationalApproximation(T n, fraction<T> p){
    fraction<T> a(0, 1), b(1, 0);
    fraction<T> x(0, 1), y(1, 0);
    bool ok_left = true, ok_right = true;
    while(ok_left && ok_right){
        fraction<T> m(a.p + b.p, a.q + b.q);
        if(p < m){
            T ok = 0, ng = n;
            while(ng - ok > 1){
                T mid = (ok + ng) / 2;
                fraction<T> m2(a.p * mid + b.p, a.q * mid + b.q);
                if(p < m2 && m2.p <= n && m2.q <= n){
                    ok = mid;
                    m = m2;
                } else{
                    ng = mid;
                }
            }
            b = m;
            if(m.p <= n && m.q <= n){
                y = m;
            } else{
                ok_left = false;
            }
        } else{
            T ok = 0, ng = n;
            while(ng - ok > 1){
                T mid = (ok + ng) / 2;
                fraction<T> m2(a.p + b.p * mid, a.q + b.q * mid);
                if(p >= m2 && m2.p <= n && m2.q <= n){
                    ok = mid;
                    m = m2;
                } else{
                    ng = mid;
                }
            }
            a = m;
            if(m.p <= n && m.q <= n){
                x = m;
            } else{
                ok_right = false;
            }
        }
    }
    return make_pair(x, y);
}
#line 6 "test/library_checker/number_theory/rational_approximation.test.cpp"

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; cin >> T;
    while(T--){
        long long n, x, y; cin >> n >> x >> y;
        fraction<long long> f(x, y);
        auto [l, r] = rationalApproximation(n, f);
        if(f == l) r = l;
        cout << l.p << " " << l.q << " " << r.p << " " << r.q << "\n";
    }
}