haar_lib/num/modint/
mod.rs

1//! 実行時にmod Mが決まるModInt
2
3pub mod algebra;
4
5use crate::impl_ops;
6pub use crate::num::ff::*;
7use std::{
8    fmt,
9    fmt::{Debug, Display, Formatter},
10    ops::Neg,
11};
12
13/// [`ModInt`]を生成するための構造体。
14#[derive(Clone, Debug, PartialEq, Eq)]
15pub struct ModIntBuilder {
16    modulo: u32,
17}
18
19impl ModIntBuilder {
20    /// `modulo`を法とする`ModIntBuilder`を生成する。
21    pub fn new(modulo: u32) -> Self {
22        assert!(modulo > 0);
23        Self { modulo }
24    }
25}
26
27impl FF for ModIntBuilder {
28    type Element = ModInt;
29    fn from_u64(&self, value: u64) -> Self::Element {
30        ModInt::new((value % self.modulo as u64) as u32, self.modulo)
31    }
32
33    fn from_i64(&self, value: i64) -> Self::Element {
34        let value = ((value % self.modulo as i64) + self.modulo as i64) as u32;
35        ModInt::new(value, self.modulo)
36    }
37    fn modulo(&self) -> u32 {
38        self.modulo
39    }
40}
41
42/// `modulo`を法として剰余をとる構造体。
43#[derive(Copy, Clone, PartialEq, Eq)]
44pub struct ModInt {
45    value: u32,
46    modulo: u32,
47}
48
49impl FFElem for ModInt {
50    #[inline]
51    fn value(self) -> u32 {
52        self.value
53    }
54
55    #[inline]
56    fn modulo(self) -> u32 {
57        self.modulo
58    }
59
60    fn pow(self, mut p: u64) -> Self {
61        let mut ret: u64 = 1;
62        let mut a = self.value as u64;
63
64        while p > 0 {
65            if (p & 1) != 0 {
66                ret *= a;
67                ret %= self.modulo as u64;
68            }
69
70            a *= a;
71            a %= self.modulo as u64;
72
73            p >>= 1;
74        }
75
76        Self::new_unchecked(ret as u32, self.modulo)
77    }
78}
79
80impl ModInt {
81    /// `value`を値にもち、`modulo`を法とする`ModInt`を生成する。
82    pub fn new(value: u32, modulo: u32) -> Self {
83        assert!(modulo > 0);
84        let value = if value < modulo {
85            value
86        } else {
87            value % modulo
88        };
89        Self { value, modulo }
90    }
91
92    #[inline]
93    fn new_unchecked(value: u32, modulo: u32) -> Self {
94        Self { value, modulo }
95    }
96}
97
98impl Display for ModInt {
99    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
100        write!(f, "{}", self.value)
101    }
102}
103
104impl Debug for ModInt {
105    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
106        write!(f, "{} (mod {})", self.value, self.modulo)
107    }
108}
109
110impl_ops!(Add for ModInt, |x: Self, y: Self| {
111    assert_eq!(x.modulo, y.modulo);
112    let a = x.value + y.value;
113    Self::new_unchecked(
114        if a < x.modulo { a } else { a - x.modulo },
115        x.modulo,
116    )
117});
118impl_ops!(Sub for ModInt, |x: Self, y: Self| {
119    assert_eq!(x.modulo, y.modulo);
120    let a = if x.value < y.value {
121        x.value + x.modulo - y.value
122    } else {
123        x.value - y.value
124    };
125    Self::new_unchecked(a, x.modulo)
126});
127impl_ops!(Mul for ModInt, |x: Self, y: Self| {
128    assert_eq!(x.modulo, y.modulo);
129    let a = x.value as u64 * y.value as u64;
130    let value = if a < x.modulo as u64 {
131        a as u32
132    } else {
133        (a % x.modulo as u64) as u32
134    };
135
136    Self::new_unchecked(value, x.modulo)
137});
138impl_ops!(Div for ModInt, |x: Self, y: Self| x * y.inv());
139
140impl_ops!(AddAssign for ModInt, |x: &mut Self, y| *x = *x + y);
141impl_ops!(SubAssign for ModInt, |x: &mut Self, y| *x = *x - y);
142impl_ops!(MulAssign for ModInt, |x: &mut Self, y| *x = *x * y);
143impl_ops!(DivAssign for ModInt, |x: &mut Self, y| *x = *x / y);
144
145impl Neg for ModInt {
146    type Output = Self;
147    fn neg(self) -> Self {
148        Self::new_unchecked(
149            if self.value == 0 {
150                0
151            } else {
152                self.modulo - self.value
153            },
154            self.modulo,
155        )
156    }
157}
158
159impl From<ModInt> for u32 {
160    fn from(value: ModInt) -> Self {
161        value.value
162    }
163}
haar_lib/num/modint/mod.rs

haar_lib/num/modint/
mod.rs
