kyopro_library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub dyktr06/kyopro_library

:heavy_check_mark: Rational Approximation (有理数近似)
(lib/math/rational_approximation.hpp)

Rational Approximation (有理数近似)

概要

分子、分母がともに $N$ 以下である既約分数において、分数 $p$ 以下で最大のものと $p$ より大きいもので最小のものを求めます。

見つからなかった場合には、$0/1$, $1/0$ がそれぞれ返り値となります。

計算量

Depends on

Verified with

Code

#pragma once

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

#include "../math/fraction.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 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);
}
Back to top page