Algoogle

Algorithm for Programming Contest

有理数

基本情報


解説


分数で各種演算を行えるクラス.
容易にオーバーフローするので見積もりを誤らないように.

コード


(fraction.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
struct frac {
    long long num, den;
    frac(){}
    frac(long long a) : num(a) { den = 1; }
    frac(long long a, long long b) : num(a), den(b) { normalize(); }
    void normalize() {
        if(num == 0) {
            den = 1;
            return;
        }
        if(den < 0) {
            num *= -1;
            den *= -1;
        }
        long long t = __gcd(abs(num),den);
        num /= t; den /= t;
    }
    frac operator*=(const frac &f) {
        long long t = __gcd(den,abs(f.num)), u = __gcd(f.den,abs(num));
        num = num/u*f.num/t;
        den = den/t*f.den/u;
        return *this;
    }
    frac operator*(const frac &f) const { return frac(*this) *= f; }
    frac operator/=(const frac &f){ return frac(*this)*=frac(f.den,f.num); }
    frac operator/(const frac &f) const { return frac(*this)/=f; }
    frac operator+=(const frac &f) {
        long long t = __gcd(den,f.den);
        num = f.den/t*num+den/t*f.num;
        den = den/t*f.den;
        normalize();
        return *this;
    }
    frac operator+(const frac &f) const { return frac(*this)+=f; }
    frac operator-=(const frac &f) {
        long long t = __gcd(den,f.den);
        num = f.den/t*num-den/t*f.num;
        den = den/t*f.den;
        normalize();
        return *this;
    }
    frac operator-(const frac &f) const { return frac(*this)-=f; }
    bool operator<(const frac &f) const { return num*f.den < den*f.num; }
    bool operator>(const frac &f) const { return num*f.den > den*f.num; }
    bool operator==(const frac &f) const { return num*f.den == den*f.num; }
    double to_double() const { return 1.*num/den; }
    frac abs() const { return frac(abs(f.num),f.den); }
};
ostream &operator<<(ostream &os, const frac &f) {
    os<<f.num<<"/"<<f.den;
    return os;
}

Comments