Struct URational

Source

pub struct URational<T>where
    T: Unsigned,{
    pub num: T,
    pub den: T,
}

Fields§

§num: T§den: T

Implementations§

Source §

impl<T> URational<T>
where T: Unsigned,

Source

pub fn new(num: T, den: T) -> Self

Examples found in repository ?

crates/competitive/src/algorithm/stern_brocot_tree.rs (line 145)

143    fn root() -> Self {
144        Self {
145            l: URational::new(T::zero(), T::one()),
146            r: URational::new(T::one(), T::zero()),
147        }
148    }

More examples

Hide additional examples

crates/competitive/src/num/urational.rs (line 78)

74    pub fn map<U>(self, mut f: impl FnMut(T) -> U) -> URational<U>
75    where
76        U: Unsigned,
77    {
78        URational::new(f(self.num), f(self.den))
79    }
80    pub fn map_unchecked<U>(self, mut f: impl FnMut(T) -> U) -> URational<U>
81    where
82        U: Unsigned,
83    {
84        URational::new_unchecked(f(self.num), f(self.den))
85    }
86    pub fn map_eval<U>(self, mut f: impl FnMut(T) -> U) -> <U as Div>::Output
87    where
88        U: Div,
89    {
90        f(self.num) / f(self.den)
91    }
92}
93
94impl<T> Bounded for URational<T>
95where
96    T: Unsigned,
97{
98    fn maximum() -> Self {
99        Self::new_unchecked(T::one(), T::zero())
100    }
101    fn minimum() -> Self {
102        Self::zero()
103    }
104}
105
106impl<T> Zero for URational<T>
107where
108    T: Unsigned,
109{
110    fn zero() -> Self {
111        Self::new_unchecked(T::zero(), T::one())
112    }
113}
114impl<T> One for URational<T>
115where
116    T: Unsigned,
117{
118    fn one() -> Self {
119        Self::new_unchecked(T::one(), T::one())
120    }
121}
122
123impl<T> Add for URational<T>
124where
125    T: Unsigned,
126{
127    type Output = Self;
128    fn add(self, rhs: Self) -> Self::Output {
129        Self::new(self.num * rhs.den + self.den * rhs.num, self.den * rhs.den)
130    }
131}
132impl<T> Sub for URational<T>
133where
134    T: Unsigned,
135{
136    type Output = Self;
137    fn sub(self, rhs: Self) -> Self::Output {
138        Self::new(self.num * rhs.den - self.den * rhs.num, self.den * rhs.den)
139    }
140}
141impl<T> Mul for URational<T>
142where
143    T: Unsigned,
144{
145    type Output = Self;
146    fn mul(self, rhs: Self) -> Self::Output {
147        Self::new(self.num * rhs.num, self.den * rhs.den)
148    }
149}
150impl<T> Div for URational<T>
151where
152    T: Unsigned,
153{
154    type Output = Self;
155    fn div(self, rhs: Self) -> Self::Output {
156        Self::new(self.num * rhs.den, self.den * rhs.num)
157    }

crates/library_checker/src/number_theory/stern_brocot_tree.rs (line 25)

18pub fn stern_brocot_tree(reader: impl Read, writer: impl Write) {
19    prepare_io!(reader, writer);
20    sc!(t);
21    for _ in 0..t {
22        sc!(query: Query);
23        match query {
24            Query::EncodePath { a, b } => {
25                let path = SbtPath::from(URational::new(a, b));
26                let len = if path.path.first() == Some(&0) {
27                    path.path.len() - 1
28                } else {
29                    path.path.len()
30                };
31                pp!(len, !);
32                for (i, count) in path.into_iter().enumerate() {
33                    if count == 0 {
34                        continue;
35                    }
36                    if i % 2 == 0 {
37                        pp!(@ns " R ", count, !);
38                    } else {
39                        pp!(@ns " L ", count, !);
40                    }
41                }
42                pp!();
43            }
44            Query::DecodePath { path, .. } => {
45                let node: SbtNode<u32> = if path.first().is_some_and(|t| t.0 == 'L') {
46                    [0].into_iter()
47                        .chain(path.into_iter().map(|(_, c)| c))
48                        .collect()
49                } else {
50                    path.into_iter().map(|(_, c)| c).collect()
51                };
52                let val = node.eval();
53                pp!(val.num, val.den);
54            }
55            Query::Lca { a, b, c, d } => {
56                let path1 = SbtPath::from(URational::new(a, b));
57                let path2 = SbtPath::from(URational::new(c, d));
58                let val = SbtNode::lca(path1, path2).eval();
59                pp!(val.num, val.den);
60            }
61            Query::Ancestor { k, a, b } => {
62                let mut path = SbtPath::from(URational::new(a, b));
63                let depth = path.depth();
64                if k <= depth {
65                    path.up(depth - k);
66                    let val = path.eval();
67                    pp!(val.num, val.den);
68                } else {
69                    pp!("-1");
70                }
71            }
72            Query::Range { a, b } => {
73                let node = SbtPath::from(URational::new(a, b)).to_node();
74                pp!(node.l.num, node.l.den, node.r.num, node.r.den);
75            }
76        }
77    }
78}

Source

pub fn new_unchecked(num: T, den: T) -> Self

Examples found in repository ?

crates/competitive/src/num/urational.rs (line 66)

64    pub fn new(num: T, den: T) -> Self {
65        let g = num.gcd(den);
66        Self::new_unchecked(num / g, den / g)
67    }
68    pub fn new_unchecked(num: T, den: T) -> Self {
69        Self { num, den }
70    }
71    pub fn eval(self) -> T {
72        self.num / self.den
73    }
74    pub fn map<U>(self, mut f: impl FnMut(T) -> U) -> URational<U>
75    where
76        U: Unsigned,
77    {
78        URational::new(f(self.num), f(self.den))
79    }
80    pub fn map_unchecked<U>(self, mut f: impl FnMut(T) -> U) -> URational<U>
81    where
82        U: Unsigned,
83    {
84        URational::new_unchecked(f(self.num), f(self.den))
85    }
86    pub fn map_eval<U>(self, mut f: impl FnMut(T) -> U) -> <U as Div>::Output
87    where
88        U: Div,
89    {
90        f(self.num) / f(self.den)
91    }
92}
93
94impl<T> Bounded for URational<T>
95where
96    T: Unsigned,
97{
98    fn maximum() -> Self {
99        Self::new_unchecked(T::one(), T::zero())
100    }
101    fn minimum() -> Self {
102        Self::zero()
103    }
104}
105
106impl<T> Zero for URational<T>
107where
108    T: Unsigned,
109{
110    fn zero() -> Self {
111        Self::new_unchecked(T::zero(), T::one())
112    }
113}
114impl<T> One for URational<T>
115where
116    T: Unsigned,
117{
118    fn one() -> Self {
119        Self::new_unchecked(T::one(), T::one())
120    }

More examples

Hide additional examples

crates/competitive/src/algorithm/stern_brocot_tree.rs (line 155)

154    fn eval(&self) -> URational<Self::T> {
155        URational::new_unchecked(self.l.num + self.r.num, self.l.den + self.r.den)
156    }

crates/library_checker/src/number_theory/rational_approximation.rs (line 10)

5pub fn rational_approximation(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(t);
8    for _ in 0..t {
9        sc!(n: u64, x: u64, y: u64);
10        let x = URational::new_unchecked(x, y);
11        let sbt = rational_binary_search::<u64>(|&a| a <= x, n);
12        if matches!(sbt.l.cmp(&x), std::cmp::Ordering::Equal) {
13            pp!(sbt.l.num, sbt.l.den, sbt.l.num, sbt.l.den);
14        } else {
15            pp!(sbt.l.num, sbt.l.den, sbt.r.num, sbt.r.den);
16        }
17    }
18}