More than 1 year has passed since last update.

【C++】分数クラスのすすめ＋無限大への拡張【競プロ】

Last updated at 2023-06-20Posted at 2023-03-10

はじめに

分数を扱えるクラスを実装したので解説します。競技プログラミングに関していうと、解法に対して直接的に使う機会はあまりありませんが、確率・期待値を求める問題でのデバッグや、2次元平面での傾きを管理するときなどに使えるので、持っていると便利だと思います。

注意書き

本コードは十分なverify ができていません。 使用する場合は自己責任でお願いします。

どんなことができる？

こういう感じのクラスを作ります。

int main(void){

    fraction a(3, 2); // a = 3 / 2;
    fraction b(4, 3); // b = 4 / 3;
    
    // 四則演算ができる
    cout << a + b << endl;
    cout << a - b << endl;
    cout << a * b << endl;
    cout << a / b << endl;

    // 整数型との計算もできる
    cout << a + 3 << endl;

    // (拡張版) 無限を表現！
    fraction c(1, 0); // c = inf;
    cout << c + a << endl;
    cout << c - a << endl;
    cout << c * a << endl;
    cout << c / a << endl;
    cout << c * (-c) << endl;
    
    // その他便利なインターフェース
    cout << a.inverse() << endl; // 逆数
    cout << a.mod(1000000007) << endl; // (分子) * (分母)^(-1) (mod (引数))
    cout << a.floor() << endl; // 切り捨て
    cout << a.ceil() << endl; // 切り上げ
    cout << a.real() << endl; // 小数での表示   

}

実行結果は以下の通りです。

17/6
1/6
2
9/8
9/2
inf
inf
inf
inf
-inf
2/3
500000005
1
2
1.5

通常の数値型と同じように扱えるので、std::map や std::set をはじめ、Segment-Tree等のデータ構造に乗せることもできます。

設計方針

・分数クラスは分子・分母を表す二つのメンバ変数を持つ。
・四則演算・大小比較を扱えるようにする。
・演算の結果、分子・分母がともに $64$bit 整数の範囲ならば正しく動作するようにする。
・分子・分母は常に約分された形で保持される。
・負の数は分子を負とすることで再現し、分母は常に $0$ でない正の数とする。
・$0$ は $0/1$ として扱う。

実装

まず約分する関数、メンバ変数とコンストラクタ、約分する関数を宣言します。
分子・分母（それぞれ num, den）は long long 型で持ちます。
std::gcd に __int128_t 型変数が渡せないみたいなので、gcd 関数は自分で作ります。衝突が怖いので適当に namespace 空間に定義しときます。


namespace internal {
// 内部実装
__int128_t __gcd(__int128_t a, __int128_t b) {
    if (a % b == 0)
        return b;
    return __gcd(b, a % b);
}
// こっちを呼ぶ。絶対値の GCD を返す。片方が 0 ならもう一方の絶対値。
__int128_t gcd(__int128_t a, __int128_t b) {
    if (b == 0)
        return (a >= 0 ? a : -a);
    return internal::__gcd((a >= 0 ? a : -a), (b >= 0 ? b : -b));
}
// 約分
inline void simplify(__int128_t &num, __int128_t &den) {
    __int128_t d = internal::gcd(num, den);
    num /= (den >= 0 ? d : -d);
    den /= (den >= 0 ? d : -d);
}
}; // namespace internal

class fraction{
  private:
    long long num, den;

  public:
    fraction(long long n) : num(n), den(1) {}
    fraction(__int128_t numerator, __int128_t denominator) {
        internal::simplify(numerator, denominator);
        num = numerator, den = denominator;
    }
    fraction() : num(0), den(1) {}
};

初期化の際には必ず約分を試みます。例えば、

int main(void){
    fraction a(2, 4);
}

このように既約でない分数を宣言した際に、値が約分されないまま $2/4$ として保持されると困ります。
設計方針に従い、分子と分母は必ず既約であるように保ちたいので、コンストラクタ内でsimplifyを呼んでいます。
約分が必要ないと保証されているときのために、そのまま代入する関数も作っときましょう。

    // 約分を省略して代入する
    fraction &raw_assign(long long _num, long long _den) {
        num = _num, den = _den;
        return *this;
    }

次に入出力ができるようにします。以下のように実装すればよいです。

    friend std::istream &operator>>(std::istream &is, fraction &a) {
        std::string buf;
        is >> buf;
        __int128_t num_tmp = 0, den_tmp = 0;
        int i = (buf[0] == '-'), sz = buf.size();
        for (; i < sz && buf[i] != '/'; i++)
            num_tmp = num_tmp * 10 + buf[i] - '0';
        if (i == sz)
            den_tmp = 1;
        else
            for (i = i + 1; i < sz; i++)
                den_tmp = den_tmp * 10 + buf[i] - '0';
        if (buf[0] == '-')
            num_tmp *= -1;
        internal::simplify(num_tmp, den_tmp);
        a.num = num_tmp, a.den = den_tmp;
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const fraction &a) {
        if (a.den == 1)
            os << a.num;
        else
            os << a.num << '/' << a.den;
        return os;
    }

入力では、文字列の先頭に '-'（マイナス）があるか、途中に '/'（スラッシュ）があるかを見ています。
出力に関しては簡単で、分母が $1$ なら整数として出力しているだけです。

次に四則演算です。

    friend fraction operator+(const fraction &a, const fraction &b) {
        return {(__int128_t)a.num * b.den + (__int128_t)b.num * a.den,
                (__int128_t)a.den * b.den};
    }
    friend fraction operator-(const fraction &a, const fraction &b) {
        return {(__int128_t)a.num * b.den - (__int128_t)b.num * a.den,
                (__int128_t)a.den * b.den};
    }
    friend fraction operator*(const fraction &a, const fraction &b) {
        long long gcd_tmp1 = std::gcd(a.num, b.den),
                  gcd_tmp2 = std::gcd(b.num, a.den);
        fraction ret;
        ret.raw_assign((a.num / gcd_tmp1) * (b.num / gcd_tmp2),
                       (a.den / gcd_tmp2) * (b.den / gcd_tmp1));
        return ret;
    }
    friend fraction operator/(const fraction &a, const fraction &b) {
        long long gcd_tmp1 = std::gcd(a.num, b.num),
                  gcd_tmp2 = std::gcd(b.den, a.den);
        fraction ret;
        ret.raw_assign(
            (b.num >= 0 ? 1 : -1) * (a.num / gcd_tmp1) * (b.den / gcd_tmp2),
            (b.num >= 0 ? 1 : -1) * (a.den / gcd_tmp2) * (b.num / gcd_tmp1));
        return ret;
    }

加減は見たまんまで、通分して足し引きします。return の際にコンストラクタが呼ばれて約分が行われます。long long どうしの掛け算を行うときにオーバーフローすることがあるので、面倒ですが都度 __int128_t にキャストします。
乗除については、掛け算してから約分するよりも、分子分母について個別に約分を済ませておく方が速そうです（未検証）。既に約分がされているので、raw_assign で代入してから return します。
除算は乗算とほぼ同じですが、負の数で割るときに分母が負にならないように気を付けます。

これであらかた出来上がりました。各種演算子を適切に定義してやると、次のような実装になります。
（mod 関数には mod の逆元を求める mod_inverse 関数を用いています。持っていない人はこちらの記事を参考に用意してください。）

namespace internal {
// 内部実装
__int128_t __gcd(__int128_t a, __int128_t b) {
  if (a % b == 0)
    return b;
  return __gcd(b, a % b);
}
// こっちを呼ぶ。絶対値の GCD を返す。片方が 0 ならもう一方の絶対値。
__int128_t gcd(__int128_t a, __int128_t b) {
  if (b == 0)
    return (a >= 0 ? a : -a);
  return internal::__gcd((a >= 0 ? a : -a), (b >= 0 ? b : -b));
}
// 約分
inline void simplify(__int128_t &num, __int128_t &den) {
  __int128_t d = internal::gcd(num, den);
  num /= (den >= 0 ? d : -d);
  den /= (den >= 0 ? d : -d);
}
}; // namespace internal

class fraction {
private:
  long long num, den;

public:
  fraction(long long n) : num(n), den(1) {}
  fraction(__int128_t numerator, __int128_t denominator) {
    internal::simplify(numerator, denominator);
    num = numerator, den = denominator;
  }
  fraction() : num(0), den(1) {}

  friend fraction operator+(const fraction &a) { return a; }
  friend fraction operator-(const fraction &a) {
    fraction ret;
    ret.raw_assign(-a.num, a.den);
    return ret;
  }

  friend fraction operator+(const fraction &a, const fraction &b) {
    return {a.num * b.den + b.num * a.den, a.den * b.den};
  }
  friend fraction operator-(const fraction &a, const fraction &b) {
    return {a.num * b.den - b.num * a.den, a.den * b.den};
  }
  friend fraction operator*(const fraction &a, const fraction &b) {
    __int128_t gcd_tmp1 = std::gcd(a.num, b.den),
               gcd_tmp2 = std::gcd(b.num, a.den);
    return {(a.num / gcd_tmp1) * (b.num / gcd_tmp2),
            (a.den / gcd_tmp2) * (b.den / gcd_tmp1), false};
  }
  friend fraction operator/(const fraction &a, const fraction &b) {
    __int128_t gcd_tmp1 = std::gcd(a.num, b.num),
               gcd_tmp2 = std::gcd(b.den, a.den);
    return {(b.num < 0 ? -1 : 1) * (a.num / gcd_tmp1) * (b.den / gcd_tmp2),
            (b.num < 0 ? -1 : 1) * (a.den / gcd_tmp2) * (b.num / gcd_tmp1),
            false};
  }

  friend bool operator==(const fraction &a, const fraction &b) {
    return a.num == b.num && a.den == b.den;
  }
  friend bool operator!=(const fraction &a, const fraction &b) {
    return a.num != b.num || a.den != b.den;
  }
  friend bool operator>(const fraction &a, const fraction &b) {
    return (__int128_t)a.num * b.den > (__int128_t)b.num * a.den;
  }
  friend bool operator>=(const fraction &a, const fraction &b) {
    return (__int128_t)a.num * b.den >= (__int128_t)b.num * a.den;
  }
  friend bool operator<(const fraction &a, const fraction &b) {
    return (__int128_t)a.num * b.den < (__int128_t)b.num * a.den;
  }
  friend bool operator<=(const fraction &a, const fraction &b) {
    return (__int128_t)a.num * b.den <= (__int128_t)b.num * a.den;
  }

public:
  fraction(long long n) : num(n), den(1) {}
  fraction(__int128_t numerator, __int128_t denominator) {
    internal::simplify(numerator, denominator);
    num = numerator, den = denominator;
  }
  fraction() : num(0), den(1) {}

  fraction &operator=(const fraction &a) = default;
  fraction &operator+=(const fraction &a) { return *this = *this + a; }
  fraction &operator-=(const fraction &a) { return *this = *this - a; }
  fraction &operator*=(const fraction &a) { return *this = *this * a; }
  fraction &operator/=(const fraction &a) { return *this = *this / a; }

  friend std::istream &operator>>(std::istream &is, fraction &a) {
    std::string buf;
    is >> buf;
    a.num = a.den = 0;
    int i = (buf[0] == '-');
    for (; i < buf.size() && buf[i] != '/'; i++)
      a.num = a.num * 10 + buf[i] - '0';
    if (i == buf.size())
      a.den = 1;
    else
      for (i = i + 1; i < buf.size(); i++)
        a.den = a.den * 10 + buf[i] - '0';
    if (buf[0] == '-')
      a.num *= -1;
    a.simplify();
    return is;
  }
  friend std::ostream &operator<<(std::ostream &os, const fraction &a) {
    if (a.den == 1)
      os << a.num;
    else
      os << a.num << '/' << a.den;
    return os;
  }

  // ------------------------------- optional ------------------------------- //

  long long numerator() const { return num; }
  long long denomitnator() const { return den; }
  long long floor() const { return num / den; }
  long long ceil() const { return ((__int128_t)num + den - 1) / den; }
  double real() const { return (double)num / den; }
  fraction abs() const { return (*this >= 0 ? *this : -*this); }
  fraction inverse() const {
    fraction ret;
    ret.raw_assign((num >= 0 ? den : -den), (num >= 0 ? num : -num));
    return ret;
  }
  // mod_inverse 関数は適当に自分で用意してください
  /*int mod(int _mod) const {
      assert(_mod > 0);
      long long ret = num % _mod;
      if (ret < 0)
          ret += _mod;
      return (ret *= mod_inverse(den, _mod)) %= _mod;
  }*/
};

無限大への拡張

この記事メインはここからです。私が提案したいのは、「$0$ で割った値を無限としよう」ということです。モチベーションはこの問題です。
私はこの問題を二次元平面上の問題としてとらえ、原点と各イワシの座標の $2$ 点を通る直線の傾き $A[i] / B[i]$ をキーとして std::map で管理すれば良いと考えました。しかし、$B[i]$ が $0$ である場合、通常の分数クラスでは $0$ 除算が発生するため、場合分けが発生し、非常に面倒に感じました。
要するに、直線の傾きが $0$ のときの状態は持てるのに、$\infty $ の状態が持てないのは不揃いだと思ったのです。
そういうわけで、設計方針を次のように設定し直します。

・分数クラスは分子・分母を表す二つのメンバ変数を持つ。
・四則演算・大小比較を扱えるようにする。
・演算の結果、分子・分母がともに $64$bit 整数の範囲ならば正しく動作するようにする。
・分子・分母は常に約分された形で保持される。
・負の数は分子を負とすることで再現し、分母は非負整数とする。
・$0$ は $0/1$ として扱う。
・$\infty$ は $1/0$, $-\infty$ は $-1/0$ として扱う。
・不定形 ($\infty - \infty$, $\infty / \infty$, $0/0$ ) は計算不可とする。

これに従えば、以下のように実装できます。

#include <assert.h>

#include <iostream>
#include <numeric>

namespace internal {

__int128_t __gcd(__int128_t a, __int128_t b) {
    if (a % b == 0)
        return b;
    return __gcd(b, a % b);
}

// 絶対値の GCD を返す。片方が 0 ならもう一方の絶対値。
__int128_t gcd(__int128_t a, __int128_t b) {
    if (b == 0)
        return (a >= 0 ? a : -a);
    return internal::__gcd((a >= 0 ? a : -a), (b >= 0 ? b : -b));
}

inline void simplify(__int128_t &num, __int128_t &den) {
    __int128_t d = internal::gcd(num, den);
    num /= (den >= 0 ? d : -d);
    den /= (den >= 0 ? d : -d);
}
}; // namespace internal

// 演算結果の分子・分母がともに 64bit 整数の範囲でのみ動作を保証
class fraction {
  private:
    long long num, den;

    friend fraction operator+(const fraction &a) { return a; }
    friend fraction operator-(const fraction &a) {
        fraction ret;
        ret.raw_assign(-a.num, a.den);
        return ret;
    }

    friend fraction operator+(const fraction &a, const fraction &b) {
        assert(!(a.is_infinity() && b.is_infinity() &&
                 a.num * b.num == -1)); // 不定形はダメ
        if (a.is_infinity()) {
            return a;
        } else if (b.is_infinity()) {
            return b;
        } else {
            return {(__int128_t)a.num * b.den + (__int128_t)b.num * a.den,
                    (__int128_t)a.den * b.den};
        }
    }
    friend fraction operator-(const fraction &a, const fraction &b) {
        assert(!(a.is_infinity() && b.is_infinity() &&
                 a.num * b.num == 1)); // 不定形はダメ
        if (a.is_infinity()) {
            return a;
        } else if (b.is_infinity()) {
            return -b;
        } else {
            return {(__int128_t)a.num * b.den - (__int128_t)b.num * a.den,
                    (__int128_t)a.den * b.den};
        }
    }
    friend fraction operator*(const fraction &a, const fraction &b) {
        assert(a.num != 0 || b.den != 0);
        assert(a.den != 0 || b.num != 0);
        long long gcd_tmp1 = std::gcd(a.num, b.den),
                  gcd_tmp2 = std::gcd(b.num, a.den);
        fraction ret;
        ret.raw_assign((a.num / gcd_tmp1) * (b.num / gcd_tmp2),
                       (a.den / gcd_tmp2) * (b.den / gcd_tmp1));
        return ret;
    }
    friend fraction operator/(const fraction &a, const fraction &b) {
        assert(a.num != 0 || b.num != 0);
        assert(a.den != 0 || b.den != 0);
        long long gcd_tmp1 = std::gcd(a.num, b.num),
                  gcd_tmp2 = std::gcd(b.den, a.den);
        fraction ret;
        ret.raw_assign(
            (b.num >= 0 ? 1 : -1) * (a.num / gcd_tmp1) * (b.den / gcd_tmp2),
            (b.num >= 0 ? 1 : -1) * (a.den / gcd_tmp2) * (b.num / gcd_tmp1));
        return ret;
    }

    friend bool operator==(const fraction &a, const fraction &b) {
        return a.num == b.num && a.den == b.den;
    }
    friend bool operator!=(const fraction &a, const fraction &b) {
        return a.num != b.num || a.den != b.den;
    }

    friend int compare_to(const fraction &a, const fraction &b) {
        if ((a.num >= 0) ^ (b.num >= 0))
            return a.num > b.num ? 1 : -1;
        __int128_t lhs = (__int128_t)a.num * b.den;
        __int128_t rhs = (__int128_t)b.num * a.den;
        if (lhs == rhs)
            return 0;
        return lhs > rhs ? 1 : -1;
    }

    friend bool operator>(const fraction &a, const fraction &b) {
        return compare_to(a, b) > 0;
    }
    friend bool operator>=(const fraction &a, const fraction &b) {
        return compare_to(a, b) >= 0;
    }
    friend bool operator<(const fraction &a, const fraction &b) {
        return compare_to(a, b) < 0;
    }
    friend bool operator<=(const fraction &a, const fraction &b) {
        return compare_to(a, b) <= 0;
    }

  public:
    fraction(long long n) : num(n), den(1) {}
    fraction(__int128_t numerator, __int128_t denominator) {
        internal::simplify(numerator, denominator);
        num = numerator, den = denominator;
    }
    fraction() : num(0), den(1) {}

    fraction &operator=(const fraction &a) = default;
    fraction &operator+=(const fraction &a) { return *this = *this + a; }
    fraction &operator-=(const fraction &a) { return *this = *this - a; }
    fraction &operator*=(const fraction &a) { return *this = *this * a; }
    fraction &operator/=(const fraction &a) { return *this = *this / a; }

    friend std::istream &operator>>(std::istream &is, fraction &a) {
        std::string buf;
        is >> buf;
        __int128_t num_tmp = 0, den_tmp = 0;
        int i = (buf[0] == '-'), sz = buf.size();
        for (; i < sz && buf[i] != '/'; i++)
            num_tmp = num_tmp * 10 + buf[i] - '0';
        if (i == sz)
            den_tmp = 1;
        else
            for (i = i + 1; i < sz; i++)
                den_tmp = den_tmp * 10 + buf[i] - '0';
        if (buf[0] == '-')
            num_tmp *= -1;
        internal::simplify(num_tmp, den_tmp);
        a.num = num_tmp, a.den = den_tmp;
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const fraction &a) {
        if (a.den == 0)
            os << (a.num >= 0 ? "inf" : "-inf");
        else if (a.den == 1)
            os << a.num;
        else
            os << a.num << '/' << a.den;
        return os;
    }

    // 約分を省略して代入する
    fraction &raw_assign(long long _num, long long _den) {
        num = _num, den = _den;
        return *this;
    }

    // ------------------------------- optional ------------------------------- //

    long long numerator() const { return num; }
    long long denomitnator() const { return den; }
    long long floor() const { return num / den; }
    long long ceil() const { return ((__int128_t)num + den - 1) / den; }
    double real() const { return (double)num / den; }
    fraction abs() const { return (*this >= 0 ? *this : -*this); }
    fraction inverse() const {
        fraction ret;
        ret.raw_assign((num >= 0 ? den : -den), (num >= 0 ? num : -num));
        return ret;
    }
    /*int mod(int _mod) const {
        assert(_mod > 0);
        long long ret = num % _mod;
        if (ret < 0)
            ret += _mod;
        return (ret *= mod_inverse(den, _mod)) %= _mod;
    }*/
    bool is_infinity() const { return (den == 0); }

    static const fraction M_INF, INF;
};
const fraction fraction::M_INF(-1, 0), fraction::INF(1, 0); // -∞, ∞ を表す定数

これによって、傾きが $\infty$ の座標を場合分けすることなく、統一的に扱うことが可能になりました。（ただし、傾き $-\infty$ は $\infty$ と等価であるため、これらを統合する必要がありますが……）

この拡張によって、この問題のコードをスッキリさせることができます。以下がそのコードです。
~~いうほど変わってなくないか？~~

// 拡張なし
int main(void){
 
    int N;
    cin >> N;
    map<fraction, ll> mp;
    int z_z = 0, n_z = 0, z_n = 0;
    rep(i,0,N){
        ll a, b;
        cin >> a >> b;
        if(a == 0 && b == 0) z_z++;
        else if(b == 0) n_z++; // y 軸または 
        else if(a == 0) z_n++; // x 軸に平行な場合
        else mp[{a, b}]++;
    }
 
    set<fraction> used;
    mint ans = power(2, n_z, MOD) + power(2, z_n, MOD) - 1; // 煩わしい初期値！
    for(auto [f, cnt] : mp){
        if(used.count(f)) continue;
        fraction dislike = -f.inverse();
        if(mp.count(dislike)){
            ans *= power(2, mp[f], MOD) + power(2, mp[dislike], MOD) - 1;
            used.insert(dislike);
        }else{
            ans *= power(2, mp[f], MOD);
        }
    }
 
    ans += z_z;
    ans -= 1;
    cout << ans << endl;
 
}

// 拡張あり
int main(void){

    int N;
    cin >> N;
    map<fraction, ll> mp;
    int z_z = 0;
    rep(i,0,N){
        ll a, b;
        cin >> a >> b;
        if(a == 0 && b == 0) z_z++;
        else if(b == 0) mp[{-abs(a), 0}]++; // inf は -inf に統一
        else mp[{a, b}]++;
    }
 
    set<fraction> used;
    mint ans = 1; // 初期値が自明でスッキリ！
    for(auto [f, cnt] : mp){
        if(used.count(f)) continue;
        fraction dislike = -f.inverse();
        if(mp.count(dislike)){
            ans *= power(2, mp[f], MOD) + power(2, mp[dislike], MOD) - 1;
            used.insert(dislike);
        }else{
            ans *= power(2, mp[f], MOD);
        }
    }
 
    ans += z_z;
    ans -= 1;
    cout << ans << endl;
    
}

ちょっとした懸念

どうしてもこういう仕様になっちゃいました。

int main(void){
    cout << fraction::M_INF.inverse().inverse() << endl;
}

inf

分子の値で正負を管理しているため、$-\infty$ の逆数の逆数が $\infty$ になってしまいます。うーん。。。
マイナスかどうかを管理するフラグを持つべきなのかな。でも実装が面倒そうでやってないです。
使うときは気を付けてくださーい。

参考

C++で分数class

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up