有理数 (rational number)
(include/emthrm/math/rational.hpp)

• View this file on GitHub
• Last update: 2023-02-23 21:59:12+09:00
• Include: #include "emthrm/math/rational.hpp"

参考文献

• https://github.com/spaghetti-source/algorithm/blob/208bcfd781e9c37aedee117ce45d5a4a5bab5fa1/math/rational.cc
• https://github.com/eandbsoftware/libraryCPP/blob/master/!Ratio.cpp

TODO

• Stern–Brocot tree
  • https://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree
  • http://satashun.hatenablog.com/entry/2018/12/13/163524
  • http://blue-jam.hatenablog.com/entry/20110306/1299415086
  • https://rsk0315.hatenablog.com/entry/2023/04/17/022705
  • https://miscalc.hatenablog.com/entry/2023/12/22/213007
  • http://www.prefield.com/algorithm/math/stern_brocot_tree.html
  • https://tjkendev.github.io/procon-library/python/math/stern-brocot-tree.html
  • https://sotanishy.github.io/cp-library-cpp/math/stern_brocot_tree.hpp
  • https://judge.yosupo.jp/problem/stern_brocot_tree
  • https://judge.yosupo.jp/problem/rational_approximation
  • 問題例 “New Elements: Part 2”
  • 問題例 “Inv(0,1)ving Insert(1,0)n”
  • 問題例 “Fractions (hard)”
• ファレイ数列 (Farey sequence)
  • https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A1%E3%83%AC%E3%82%A4%E6%95%B0%E5%88%97
  • https://mathtrain.jp/farey
  • http://kagamiz.hatenablog.com/entry/2012/12/01/225751
  • https://sotanishy.github.io/cp-library-cpp/math/farey_sequence.hpp
• 連分数 (continued fraction)
  • https://ja.wikipedia.org/wiki/%E9%80%A3%E5%88%86%E6%95%B0
  • https://mathtrain.jp/renbunsu
  • https://github.com/spaghetti-source/algorithm/blob/master/math/continued_fraction.cc

Submissons

https://onlinejudge.u-aizu.ac.jp/solutions/problem/2589/review/4088153/emthrm/C++14

Verified with

• 数学/有理数 (test/math/rational.test.cpp)

Code

#ifndef EMTHRM_MATH_RATIONAL_HPP_
#define EMTHRM_MATH_RATIONAL_HPP_

// #include <cassert>
#include <compare>
#include <limits>
#include <numeric>
#include <ostream>

namespace emthrm {

template <typename T = long long>
struct Rational {
  T num, den;

  Rational() : num(0), den(1) {}
  Rational(const T num, const T den = 1) : num(num), den(den) {
    // assert(den != 0);
    reduce();
  }

  template <typename Real = long double>
  Real to_real() const { return static_cast<Real>(num) / den; }

  Rational& operator+=(const Rational& x) {
    const T g = std::gcd(den, x.den);
    num = num * (x.den / g) + x.num * (den / g);
    den *= x.den / g;
    reduce();
    return *this;
  }
  Rational& operator-=(const Rational& x) { return *this += -x; }

  Rational& operator*=(const Rational& x) {
    const T g1 = std::gcd(num, x.den), g2 = std::gcd(den, x.num);
    num = (num / g1) * (x.num / g2);
    den = (den / g2) * (x.den / g1);
    reduce();
    return *this;
  }
  Rational& operator/=(const Rational& x) {
    return *this *= Rational(x.den, x.num);
  }

  auto operator<=>(const Rational& x) const {
    return num * x.den <=> x.num * den;
  }
  bool operator==(const Rational& x) const {
    return num == x.num && den == x.den;
  }

  Rational& operator++() {
    if ((num += den) == 0) den = 1;
    return *this;
  }
  Rational operator++(int) {
    const Rational res = *this;
    ++*this;
    return res;
  }
  Rational& operator--() {
    if ((num -= den) == 0) den = 1;
    return *this;
  }
  Rational operator--(int) {
    const Rational res = *this;
    --*this;
    return res;
  }

  Rational operator+() const { return *this; }
  Rational operator-() const { return Rational(-num, den); }

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

  friend std::ostream& operator<<(std::ostream& os, const Rational& x) {
    if (x.den == 1) return os << x.num;
    return os << x.num << '/' << x.den;
  }

 private:
  void reduce() {
    const T g = std::gcd(num, den);
    num /= g;
    den /= g;
    if (den < 0) {
      num = -num;
      den = -den;
    }
  }
};

}  // namespace emthrm

namespace std {

template <typename T>
emthrm::Rational<T> abs(emthrm::Rational<T> x) {
  if (x.num < 0) x.num = -x.num;
  return x;
}

template <typename T>
emthrm::Rational<T> max(const emthrm::Rational<T>& a,
                        const emthrm::Rational<T>& b) {
  return a < b ? b : a;
}

template <typename T>
emthrm::Rational<T> min(const emthrm::Rational<T>& a,
                        const emthrm::Rational<T>& b) {
  return a < b ? a : b;
}

template <typename T> struct numeric_limits<emthrm::Rational<T>> {
  static constexpr emthrm::Rational<T> max() {
    return std::numeric_limits<T>::max();
  }
  static constexpr emthrm::Rational<T> lowest() {
    return std::numeric_limits<T>::lowest();
  }
};

}  // namespace std

#endif  // EMTHRM_MATH_RATIONAL_HPP_

#line 1 "include/emthrm/math/rational.hpp"



// #include <cassert>
#include <compare>
#include <limits>
#include <numeric>
#include <ostream>

namespace emthrm {

template <typename T = long long>
struct Rational {
  T num, den;

  Rational() : num(0), den(1) {}
  Rational(const T num, const T den = 1) : num(num), den(den) {
    // assert(den != 0);
    reduce();
  }

  template <typename Real = long double>
  Real to_real() const { return static_cast<Real>(num) / den; }

  Rational& operator+=(const Rational& x) {
    const T g = std::gcd(den, x.den);
    num = num * (x.den / g) + x.num * (den / g);
    den *= x.den / g;
    reduce();
    return *this;
  }
  Rational& operator-=(const Rational& x) { return *this += -x; }

  Rational& operator*=(const Rational& x) {
    const T g1 = std::gcd(num, x.den), g2 = std::gcd(den, x.num);
    num = (num / g1) * (x.num / g2);
    den = (den / g2) * (x.den / g1);
    reduce();
    return *this;
  }
  Rational& operator/=(const Rational& x) {
    return *this *= Rational(x.den, x.num);
  }

  auto operator<=>(const Rational& x) const {
    return num * x.den <=> x.num * den;
  }
  bool operator==(const Rational& x) const {
    return num == x.num && den == x.den;
  }

  Rational& operator++() {
    if ((num += den) == 0) den = 1;
    return *this;
  }
  Rational operator++(int) {
    const Rational res = *this;
    ++*this;
    return res;
  }
  Rational& operator--() {
    if ((num -= den) == 0) den = 1;
    return *this;
  }
  Rational operator--(int) {
    const Rational res = *this;
    --*this;
    return res;
  }

  Rational operator+() const { return *this; }
  Rational operator-() const { return Rational(-num, den); }

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

  friend std::ostream& operator<<(std::ostream& os, const Rational& x) {
    if (x.den == 1) return os << x.num;
    return os << x.num << '/' << x.den;
  }

 private:
  void reduce() {
    const T g = std::gcd(num, den);
    num /= g;
    den /= g;
    if (den < 0) {
      num = -num;
      den = -den;
    }
  }
};

}  // namespace emthrm

namespace std {

template <typename T>
emthrm::Rational<T> abs(emthrm::Rational<T> x) {
  if (x.num < 0) x.num = -x.num;
  return x;
}

template <typename T>
emthrm::Rational<T> max(const emthrm::Rational<T>& a,
                        const emthrm::Rational<T>& b) {
  return a < b ? b : a;
}

template <typename T>
emthrm::Rational<T> min(const emthrm::Rational<T>& a,
                        const emthrm::Rational<T>& b) {
  return a < b ? a : b;
}

template <typename T> struct numeric_limits<emthrm::Rational<T>> {
  static constexpr emthrm::Rational<T> max() {
    return std::numeric_limits<T>::max();
  }
  static constexpr emthrm::Rational<T> lowest() {
    return std::numeric_limits<T>::lowest();
  }
};

}  // namespace std

Back to top page