Loading [Contrib]/a11y/accessibility-menu.js
$\newcommand{\O}{\mathrm{O}}$ My Algorithm : kopricky アルゴリズムライブラリ

kopricky アルゴリズムライブラリ

Continued Fraction Algorithm

コードについての説明(個人的メモ)

"有理数→連分数展開", "連分数展開→有理数" の変換および $２$ つの有理数 $p, q (p < q)$ が与えられたときに $p$ と $q$ の真に間に存在する有理数 $r$ で (分子) + (分母) が最も小さいものを返す(ここで有理数と言ったとき(非負の)有理数を指すこととする).

(関数)
rtocf$(val, res)$: 有理数 $val$ を 連分数展開形 $res$ に変換する(２種類ある).
cftor$(val)$: 連分数展開形 $val$ を有理数に変換し, それを返す.
find_rational$(val1, val2)$: $2$ つの有理数 $val1, val2 (val1 < val2)$ が与えられたときに $val1$ と $val2$ の真に間に存在する有理数で (分子) + (分母) が最も小さいものを返す. このとき (分子) + (分母) が最小のものは一意に定まることに注意する.

時間計算量: 各操作 $\O (\log A)$ ($A = \max(分子, 分母)$ とする.)

コード

  1. template<typename T> class Rational {
  2. private:
  3.     static Rational make(const T& x, const T& y){
  4.         Rational m; return m.num = x, m.den = y, m;
  5.     }
  6. public:
  7.     friend ostream& operator<<(ostream& os, const Rational& rn) {
  8.         return (os << rn.num << " / " << rn.den);
  9.     }
  10.     Rational& operator=(T val){ return *this = Rational(val); }
  11.     bool operator<(const Rational& val) const { return num*val.den < den*val.num; }
  12.     bool operator<(const T val) const { return *this < Rational(val); }
  13.     friend bool operator<(const T val1, const Rational& val2){ return Rational(val1) < val2; }
  14.     bool operator>(const Rational& val) const { return val < *this; }
  15.     bool operator>(const T val) const { return *this > Rational(val); }
  16.     friend bool operator>(const T val1, const Rational& val2){ return Rational(val1) > val2; }
  17.     bool operator<=(const Rational& val) const { return !(*this > val); }
  18.     bool operator<=(const T val) const { return *this <= Rational(val); }
  19.     friend bool operator<=(const T val1, const Rational& val2){ return Rational(val1) <= val2; }
  20.     bool operator>=(const Rational& val) const { return !(*this < val); }
  21.     bool operator>=(const T val) const { return *this >= Rational(val); }
  22.     friend bool operator>=(const T val1, const Rational& val2){ return Rational(val1) >= val2; }
  23.     bool operator==(const Rational& val) const { return num*val.den == den*val.num; }
  24.     bool operator==(const T val) const { return *this == Rational(val); }
  25.     friend bool operator==(const T val1, const Rational& val2){ return Rational(val1) == val2; }
  26.     bool operator!=(const Rational& val) const { return !(*this == val); }
  27.     bool operator!=(const T val) const { return *this != Rational(val); }
  28.     friend bool operator!=(const T val1, const Rational& val2){ return Rational(val1) != val2; }
  29.     explicit operator bool() const noexcept { return num; }
  30.     bool operator!() const noexcept { return !static_cast<bool>(*this); }
  31.     Rational operator+() const { return *this; }
  32.     Rational operator-() const { return make(-num, den); }
  33.     friend Rational abs(const Rational& val){ return make(abs(val.num), val.den); }
  34.     Rational operator+(const Rational& val) const { return make(num*val.den+val.num*den, den*val.den); }
  35.     Rational operator+(T val) const { return *this + Rational(val); }
  36.     friend Rational operator+(T a, const Rational& b){ return b + a; }
  37.     Rational& operator+=(const Rational& val){ return *this = *this + val; }
  38.     Rational& operator+=(const T& val){ return *this = *this + val; }
  39.     Rational& operator++(){ return *this += 1; }
  40.     Rational operator++(int){ return make(num + den, den); }
  41.     Rational operator-(const Rational& val) const { return make(num*val.den-val.num*den, den*val.den); }
  42.     Rational operator-(T val) const { return *this - Rational(val); }
  43.     friend Rational operator-(T a, const Rational& b){ return Rational(a) - b; }
  44.     Rational& operator-=(const Rational& val){ return *this = *this - val; }
  45.     Rational& operator-=(const T& val){ return *this = *this - val; }
  46.     Rational& operator--(){ return *this -= 1; }
  47.     Rational operator--(int){ return make(num - den, den); }
  48.     Rational operator*(const Rational& val) const { return make(num*val.num, den*val.den); }
  49.     Rational operator*(T val) const { return *this * Rational(val); }
  50.     friend Rational operator*(T a, const Rational& b){ return b * a; }
  51.     Rational& operator*=(const Rational& val){ return *this = *this * val;}
  52.     Rational& operator*=(const T& val){ return *this = *this * val; }
  53.     Rational operator/(const Rational& val) const { return make(num*val.den, den*val.num); }
  54.     Rational operator/(T val) const { return *this / Rational(val); }
  55.     friend Rational operator/(T a, const Rational& b){ return Rational(a) / b; }
  56.     Rational& operator/=(const Rational& val){ return *this / val; }
  57.     Rational& operator/=(const T& val){ return *this = *this / val; }
  58.  
  59.     T num, den;
  60.  
  61.     Rational(){}
  62.     Rational(T num_) : num(num_), den(1){}
  63.     Rational(T num_, T den_) : num(num_), den(den_){ if(den < 0) num = -num, den = -den; }
  64. };
  65.  
  66. template<typename T>
  67. bool is_valid(const Rational<T>& a, const Rational<T>& b, const Rational<T>& c)
  68. {
  69.     return (a < b && b < c);
  70. }
  71.  
  72. template<typename T>
  73. void rtocf(const Rational<T>& val, vector<vector<T> >& res)
  74. {
  75.     if(res.empty()) res.push_back(vector<T>());
  76.     res[0].push_back(val.num / val.den);
  77.     long long mod = val.num % val.den;
  78.     if(mod == 0){
  79.         res.push_back(res[0]);
  80.         if(res[0].back() == 1 && (int)res[0].size() > 1){
  81.             res[1].pop_back(), --res[1].back();
  82.         }else{
  83.             --res[0].back(), res[0].push_back(1);
  84.         }
  85.         return;
  86.     }else{
  87.         rtocf(Rational<T>(val.den, val.num-res[0].back()*val.den) , res);
  88.     }
  89. }
  90.  
  91. template<typename T>
  92. Rational<T> cftor(vector<T> val)
  93. {
  94.     T a = 1, b = 0;
  95.     while(!val.empty()){
  96.         swap(a, b);
  97.         a += val.back()*b;
  98.         val.pop_back();
  99.     }
  100.     return Rational<T>(a, b);
  101. }
  102.  
  103. template<typename T>
  104. Rational<T> find_rational(const Rational<T> val1, const Rational<T> val2)
  105. {
  106.     vector<vector<T> > l, r;
  107.     rtocf(val1, l), rtocf(val2, r);
  108.     vector<T> res;
  109.     for(vector<T>& lvec : l){
  110.         for(vector<T>& rvec : r){
  111.             vector<T> nw;
  112.             int i = 0, mn_size = min((int)lvec.size(), (int)rvec.size());
  113.             for(i = 0; i < mn_size; ++i){
  114.                 if(lvec[i] != rvec[i]){
  115.                     nw.push_back(min(lvec[i], rvec[i]) + 1);
  116.                     break;
  117.                 }else{
  118.                     nw.push_back(lvec[i]);
  119.                 }
  120.             }
  121.             if(i == mn_size){
  122.                 if((int)lvec.size() > mn_size){
  123.                     nw.push_back(lvec[mn_size]+1);
  124.                 }else{
  125.                     nw.push_back(rvec[mn_size]+1);
  126.                 }
  127.             }
  128.             Rational<T> cand = cftor(nw);
  129.             if(is_valid(val1, cand, val2)) return cand;
  130.         }
  131.     }
  132.     return Rational<T>();
  133. }

verify 用の問題

GCJ : New Elements: Part 2