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 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158
use std::ops::{MulAssign, AddAssign, DivAssign, Mul, Div}; use std::cmp::{Ordering, Ord, PartialOrd}; use std::fmt; fn gcd(mut ab: (i64, i64)) -> i64 { loop { match ab { (a, 0) => break a, (a, b) => ab = (b, a % b) } } } #[derive(Copy, Clone, Debug, Hash, Eq, PartialEq)] pub struct Rational { num: i64, denom: i64 } impl AddAssign<i64> for Rational { fn add_assign(&mut self, i: i64) { self.num += i * self.denom; self.normalize(); } } impl AddAssign for Rational { fn add_assign(&mut self, rhs: Rational) { let denom = self.denom * rhs.denom; self.num = self.num * rhs.denom + rhs.num * self.denom; self.denom = denom; self.normalize(); } } impl MulAssign<i64> for Rational { fn mul_assign(&mut self, n: i64) { self.num *= n; self.normalize(); } } impl MulAssign for Rational { fn mul_assign(&mut self, rhs: Rational) { self.num *= rhs.num; self.denom *= rhs.denom; self.normalize(); } } impl Mul for Rational { type Output = Rational; fn mul(self, rhs: Rational) -> Rational { Rational::new(self.num * rhs.num, self.denom * rhs.denom) } } impl DivAssign for Rational { fn div_assign(&mut self, rhs: Rational) { self.num *= rhs.denom; self.denom *= rhs.num; self.normalize(); } } impl DivAssign<i64> for Rational { fn div_assign(&mut self, n: i64) { self.denom *= n; self.normalize(); } } impl Div<Rational> for Rational { type Output = Rational; fn div(mut self, rhs: Rational) -> Rational { self /= rhs; self } } impl Rational { pub fn new(num: i64, denom: i64) -> Rational { let mut r = Rational { num, denom }; r.normalize(); r } fn normalize(&mut self) { let (n, d) = match (self.num, self.denom) { (0, 0) => panic!("undefined rational"), (_, 0) => panic!("infinite rational"), (0, _) => (0, 1), (n, 1) => (n, 1), (1, -1) => (1, 1), (mut n, mut d) => { if d < 0 { n = -n; d = -d; } let c = gcd((n, d)); (n/c, d/c) } }; self.num = n; self.denom = d; } pub fn frac(&self) -> (i64, i64) { (self.num, self.denom) } pub fn as_int(&self) -> Option<i64> { match self.frac() { (i, 1) => Some(i), _ => None } } pub fn is_zero(&self) -> bool { self.num == 0 } pub fn is_negative(&self) -> bool { (self.num < 0) ^ (self.denom < 0) } pub fn pow(&self, i: i32) -> Rational { match i.cmp(&0) { Ordering::Greater => Rational { num: self.num.pow(i as u32), denom: self.denom.pow(i as u32) }, Ordering::Equal => Rational::from(1), Ordering::Less => Rational { num: self.denom.pow(-i as u32), denom: self.num.pow(-i as u32) } } } pub fn to_f64(&self) -> f64 { self.num as f64 / self.denom as f64 } } impl Ord for Rational { fn cmp(&self, rhs: &Rational) -> Ordering { let a = self.num * rhs.denom; let b = rhs.num * self.denom; a.cmp(&b) } } impl PartialOrd for Rational { fn partial_cmp(&self, rhs: &Rational) -> Option<Ordering> { Some(self.cmp(rhs)) } } impl From<i64> for Rational { fn from(i: i64) -> Rational { Rational { num: i, denom: 1 } } } impl fmt::Display for Rational { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { match self.frac() { (n, 1) => write!(f, "{}", n), (n, d) => write!(f, "{}/{}", n, d), } } }