分数

分数を扱える構造体

+ - * / ができる

あまり大きくしすぎると壊れる

比較演算とsortがそのまま使える

初期化

ft x = {3,4} // ４分の３

class ft{
public:
    long long si, bo; // si/bo

    ft(long long s=0, long long b=1){
        si = s; bo = b;
        normalize();
    }

    void normalize(){
        if(bo < 0) si = -si, bo = -bo;
        long long g = gcd(llabs(si), llabs(bo));
        si /= g;
        bo /= g;
    }

    // 加算
    ft operator+(const ft& x) const {
        long long g = gcd(bo, x.bo);
        __int128 nb = (__int128)bo / g * x.bo;
        __int128 ns =
            (__int128)si * (x.bo / g)
          + (__int128)x.si * (bo / g);
        return ft((long long)ns, (long long)nb);
    }

    // 減算
    ft operator-(const ft& x) const {
        long long g = gcd(bo, x.bo);
        __int128 nb = (__int128)bo / g * x.bo;
        __int128 ns =
            (__int128)si * (x.bo / g)
          - (__int128)x.si * (bo / g);
        return ft((long long)ns, (long long)nb);
    }

    // 乗算
    ft operator*(const ft& x) const {
        long long g1 = gcd(llabs(si), llabs(x.bo));
        long long g2 = gcd(llabs(x.si), llabs(bo));
        __int128 ns = (__int128)(si/g1) * (x.si/g2);
        __int128 nb = (__int128)(bo/g2) * (x.bo/g1);
        return ft((long long)ns, (long long)nb);
    }

    // 除算
    ft operator/(const ft& x) const {
        assert(x.si != 0);
        long long g1 = gcd(llabs(si), llabs(x.si));
        long long g2 = gcd(llabs(x.bo), llabs(bo));
        __int128 ns = (__int128)(si/g1) * (x.bo/g2);
        __int128 nb = (__int128)(bo/g2) * (x.si/g1);
        return ft((long long)ns, (long long)nb);
    }

    // 比較
    bool operator<(const ft& x) const {
        return (__int128)si * x.bo < (__int128)x.si * bo;
    }
    bool operator==(const ft& x) const {
        return si == x.si && bo == x.bo;
    }
};