競プロノート

Appearance

有理数（Rational） ​

分数を既約分数として保持し、四則演算や大小比較を誤差なく行うライブラリ。

long long で分子・分母を保持し、計算途中では __int128 を利用する。

特徴 ​

項目内容
用途分数の厳密計算・比較
保持する型long long
中間計算__int128
正規化常に既約分数、分母は正
特殊値Inf、-Inf、NaN

考え方 ​

有理数を分子 num、分母 den で管理する。

cpp
Rational a(2, 4);  // 1/2
Rational b(3, -6); // -1/2
Rational c(0, 5);  // 0/1

構築時や演算後に自動で約分する。

有限値は den > 0 に統一する。

実装 ​

cpp

#pragma once
#include <bits/stdc++.h>
using namespace std;

struct Rational {
    using ll = long long;
    using i128 = __int128_t;
    ll num = 0, den = 1; // 有限値は den>0、den=0 は ±Inf / NaN

    static int sgn(ll x) { return (x > 0) - (x < 0); }
    static i128 abs128(i128 x) { return x < 0 ? -x : x; }
    static i128 gcd128(i128 a, i128 b) {
        while (b) { i128 r = a % b; a = b; b = r; }
        return a;
    }

    static pair<ll, ll> reduce(i128 n, i128 d) {
        if (d == 0) return {(ll)((n > 0) - (n < 0)), 0};
        if (n == 0) return {0, 1};
        if (d < 0) n = -n, d = -d;
        i128 g = gcd128(abs128(n), d);
        n /= g; d /= g;
        if (n < LLONG_MIN || n > LLONG_MAX || d > LLONG_MAX) throw overflow_error("Rational overflow");
        return {(ll)n, (ll)d};
    }

    static Rational make(i128 n, i128 d) {
        auto [a, b] = reduce(n, d);
        Rational r;
        r.num = a; r.den = b;
        return r;
    }

    Rational(ll n = 0, ll d = 1) { tie(num, den) = reduce(n, d); }
    static Rational NaN() { return Rational(0, 0); }
    static Rational Inf(int sign = 1) { return Rational(sign < 0 ? -1 : 1, 0); }

    bool is_nan() const { return den == 0 && num == 0; }
    bool is_inf() const { return den == 0 && num != 0; }
    int sign() const { return is_nan() ? 0 : sgn(num); }

    double to_double() const {
        if (is_nan()) return numeric_limits<double>::quiet_NaN();
        if (is_inf()) return num > 0 ? numeric_limits<double>::infinity() : -numeric_limits<double>::infinity();
        return (double)num / den;
    }
    explicit operator double() const { return to_double(); }

    Rational operator+() const { return *this; }
    Rational operator-() const { return is_nan() ? NaN() : make(-(i128)num, den); }

    static Rational add_finite(const Rational& a, const Rational& b, int s) {
        i128 g = gcd128(a.den, b.den);
        i128 n = (i128)a.num * (b.den / g) + (i128)s * b.num * (a.den / g);
        i128 d = (i128)(a.den / g) * b.den;
        return make(n, d);
    }

    friend Rational operator+(const Rational& a, const Rational& b) {
        if (a.is_nan() || b.is_nan()) return NaN();
        if (a.is_inf() && b.is_inf()) return a.num == b.num ? a : NaN();
        if (a.is_inf()) return a;
        if (b.is_inf()) return b;
        return add_finite(a, b, 1);
    }

    friend Rational operator-(const Rational& a, const Rational& b) {
        if (a.is_nan() || b.is_nan()) return NaN();
        if (a.is_inf() && b.is_inf()) return a.num == b.num ? NaN() : a;
        if (a.is_inf()) return a;
        if (b.is_inf()) return Inf(-b.num);
        return add_finite(a, b, -1);
    }

    friend Rational operator*(const Rational& a, const Rational& b) {
        if (a.is_nan() || b.is_nan()) return NaN();
        if (a.is_inf() || b.is_inf()) {
            if ((!a.is_inf() && a.num == 0) || (!b.is_inf() && b.num == 0)) return NaN();
            return Inf(a.sign() * b.sign());
        }
        return make((i128)a.num * b.num, (i128)a.den * b.den);
    }

    friend Rational operator/(const Rational& a, const Rational& b) {
        if (a.is_nan() || b.is_nan()) return NaN();
        if (b.is_inf()) return a.is_inf() ? NaN() : Rational();
        if (a.is_inf()) return b.num == 0 ? NaN() : Inf(a.sign() * b.sign());
        if (b.num == 0) return a.num == 0 ? NaN() : Inf(a.sign());
        return make((i128)a.num * b.den, (i128)a.den * b.num);
    }

    Rational& operator+=(const Rational& x) { return *this = *this + x; }
    Rational& operator-=(const Rational& x) { return *this = *this - x; }
    Rational& operator*=(const Rational& x) { return *this = *this * x; }
    Rational& operator/=(const Rational& x) { return *this = *this / x; }

    friend bool operator==(const Rational& a, const Rational& b) {
        return !a.is_nan() && !b.is_nan() && a.num == b.num && a.den == b.den;
    }
    friend bool operator!=(const Rational& a, const Rational& b) { return !(a == b); }
    friend bool operator<(const Rational& a, const Rational& b) {
        if (a.is_nan() || b.is_nan()) return false;
        if (a.is_inf() && b.is_inf()) return a.num < b.num;
        if (a.is_inf()) return a.num < 0;
        if (b.is_inf()) return b.num > 0;
        return (i128)a.num * b.den < (i128)b.num * a.den;
    }
    friend bool operator>(const Rational& a, const Rational& b) { return b < a; }
    friend bool operator<=(const Rational& a, const Rational& b) { return a < b || a == b; }
    friend bool operator>=(const Rational& a, const Rational& b) { return b < a || a == b; }

    friend ostream& operator<<(ostream& os, const Rational& r) {
        if (r.is_nan()) return os << "NaN";
        if (r.is_inf()) return os << (r.num > 0 ? "Inf" : "-Inf");
        return os << r.num << '/' << r.den;
    }

    friend istream& operator>>(istream& is, Rational& r) {
        string s;
        if (!(is >> s)) return is;
        try {
            Rational v;
            if (s == "NaN" || s == "nan") v = NaN();
            else if (s == "Inf" || s == "+Inf" || s == "inf" || s == "+inf") v = Inf();
            else if (s == "-Inf" || s == "-inf") v = Inf(-1);
            else {
                auto parse = [](const string& t) -> ll {
                    size_t used = 0;
                    ll x = stoll(t, &used);
                    if (used != t.size()) throw invalid_argument("invalid Rational");
                    return x;
                };
                size_t p = s.find('/');
                v = p == string::npos ? Rational(parse(s)) : Rational(parse(s.substr(0, p)), parse(s.substr(p + 1)));
            }
            r = v;
        } catch (const exception&) { is.setstate(ios::failbit); }
        return is;
    }
};

使用例 ​

cpp
Rational a(1, 2), b(1, 3);

cout << a + b << '\n'; // 5/6
cout << a - b << '\n'; // 1/6
cout << a * b << '\n'; // 1/6
cout << a / b << '\n'; // 3/2

cout << (a > b) << '\n'; // 1
cout << Rational(2, 4); // 1/2

特殊値 ​

分母が0の場合は特殊値として扱う。

値内部表現
+Inf1/0
-Inf-1/0
NaN0/0
cpp
Rational::Inf();     // +Inf
Rational::Inf(-1);   // -Inf
Rational::NaN();     // NaN

性質判定 ​

cpp
r.is_inf();     // 無限大か
r.is_nan();     // NaNか
r.sign();       // -1、0、1
r.to_double();  // doubleへ変換

大小比較 ​

分母が正に正規化されているため、有限値では交差積で比較できる。

a/b < c/d は

ad < cb

と同値。

計算途中では __int128 を使用している。

cpp
Rational a(1, 3), b(2, 5);
cout << (a < b); // 1

注意点 ​

  • 計算結果は常に約分される。
  • long long に収まらない分数は overflow_error となる。
  • __int128 を使っても、任意精度の分数を表せるわけではない。
  • num・den を直接変更すると正規化が崩れるため、原則としてコンストラクタや演算子を使う。
  • NaN は自分自身とも等しくない。
  • NaN を含む値をそのまま std::sort しない。
  • 無限大・NaNの演算規則は、このライブラリで定義したもの。
  • 大量の分数演算は整数演算より高コストになるため、必要な場合だけ使用する。

関連 ​

  • GCD・LCM
  • 整数のオーバーフロー
  • 精度誤差