-
Notifications
You must be signed in to change notification settings - Fork 1
/
rational.hpp
93 lines (88 loc) · 2.77 KB
/
rational.hpp
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#pragma once
#include "../template/template.hpp"
namespace lib {
struct rational {
rational() : p(0), q(1) {}
rational(ll n) : p(n), q(1) {}
rational(ll n, ll m) {
assert(m != 0);
if (m < 0) n = -n, m = -m;
ll g = gcd(n, m);
p = n / g;
q = m / g;
}
explicit operator const ld () const { return ld(p) / ld(q); }
rational& operator+=(const rational& rhs){
ll g = gcd(q, rhs.q);
ll np = rhs.q / g * p + q / g * rhs.p;
ll nq = q / g * rhs.q;
ll ng = gcd(np, nq);
p = np / ng, q = nq / ng;
return *this;
}
rational& operator-=(const rational& rhs) {
(*this) += rational(-rhs.p, rhs.q);
return *this;
}
rational& operator*=(const rational& rhs) {
ll g1 = gcd(q, rhs.p), g2 = gcd(p, rhs.q);
ll np = p / g2 * rhs.p / g1;
ll nq = q / g1 * rhs.q / g2;
p = np, q = nq;
return *this;
}
rational& operator/=(const rational& rhs) {
(*this) *= rational(rhs.q, rhs.p);
return *this;
}
rational operator+() const {
return *this;
}
rational operator-() const {
return rational() - *this;
}
friend rational operator+(const rational& lhs, const rational& rhs) {
return rational(lhs) += rhs;
}
friend rational operator-(const rational& lhs, const rational& rhs) {
return rational(lhs) -= rhs;
}
friend rational operator*(const rational& lhs, const rational& rhs) {
return rational(lhs) *= rhs;
}
friend rational operator/(const rational& lhs, const rational& rhs) {
return rational(lhs) /= rhs;
}
friend bool operator==(const rational& lhs, const rational& rhs) {
return lhs.p == rhs.p && lhs.q == rhs.q;
}
friend bool operator!=(const rational& lhs, const rational& rhs) {
return lhs.p != rhs.p || lhs.q != rhs.q;
}
friend bool operator<(const rational lhs, const rational rhs) {
return less_than(lhs, rhs);
}
friend bool operator>(const rational lhs, const rational rhs) {
return less_than(rhs, lhs);
}
friend bool operator<=(const rational lhs, const rational rhs) {
return lhs == rhs || lhs < rhs;
}
friend bool operator>=(const rational lhs, const rational rhs) {
return lhs == rhs || lhs > rhs;
}
friend std::ostream& operator<<(std::ostream& os, const rational& r) {
return os << r.p << " / " << r.q;
}
std::pair<ll,ll> val() const {
return {p, q};
}
private:
ll p, q;
static bool less_than(rational lhs, rational rhs) {
__int128_t lv = __int128_t(lhs.p) * __int128_t(rhs.q);
__int128_t rv = __int128_t(lhs.q) * __int128_t(rhs.p);
return lv < rv;
}
};
} // namespace lib