haar_lib/math/mod_ops/
mod.rs

1//! mod mでの演算
2
3pub mod enum_inv;
4pub mod inv;
5pub mod inv_p;
6pub mod log;
7pub mod pow;
8pub mod sqrt;
9
10#[cfg(test)]
11mod tests {
12    use super::{enum_inv::*, inv::*, log::*, pow::*, sqrt::*};
13
14    #[test]
15    fn test_mod_pow() {
16        fn straight_forward(x: u64, p: u64, m: u64) -> u64 {
17            let mut ret = 1;
18            for _ in 0..p {
19                ret *= x;
20                ret %= m;
21            }
22            ret
23        }
24
25        for x in 1..10 {
26            for p in 0..10 {
27                for m in 1..10 {
28                    assert_eq!(mod_pow(x, p, m), straight_forward(x, p, m));
29                }
30            }
31        }
32    }
33
34    #[test]
35    fn test_mod_inv() {
36        let m = 19;
37
38        for x in 1..m {
39            assert_eq!(mod_inv(x, m).unwrap() * x % m, 1);
40        }
41
42        assert_eq!(mod_inv(4, 10), None);
43        assert_eq!(mod_inv(3, 10), Some(7));
44    }
45
46    #[test]
47    fn test_mod_log() {
48        // https://judge.yosupo.jp/problem/discrete_logarithm_mod
49        assert_eq!(mod_log(2, 1, 5), Some(0));
50        assert_eq!(mod_log(4, 7, 10), None);
51        assert_eq!(mod_log(8, 6, 10), Some(4));
52        assert_eq!(mod_log(5, 2, 11), None);
53        assert_eq!(mod_log(5, 9, 11), Some(4));
54        assert_eq!(mod_log(0, 0, 1), Some(0));
55        assert_eq!(mod_log(0, 2, 4), None);
56    }
57
58    #[test]
59    fn test_mod_sqrt() {
60        // https://judge.yosupo.jp/problem/sqrt_mod
61        assert_eq!(mod_sqrt(0, 5).map(|x| x.pow(2) % 5), Some(0));
62        assert_eq!(mod_sqrt(1, 5).map(|x| x.pow(2) % 5), Some(1));
63        assert_eq!(mod_sqrt(2, 5).map(|x| x.pow(2) % 5), None);
64        assert_eq!(mod_sqrt(3, 5).map(|x| x.pow(2) % 5), None);
65        assert_eq!(mod_sqrt(4, 5).map(|x| x.pow(2) % 5), Some(4));
66
67        let m = 1000000007;
68        for x in 0..100 {
69            if let Some(s) = mod_sqrt(x, m) {
70                assert_eq!(s * s % m, x);
71            }
72        }
73    }
74
75    #[test]
76    fn test_enumerate_mod_inv() {
77        #![allow(clippy::needless_range_loop)]
78        let m = 1000000007;
79        let n = 100;
80
81        let s = enumerate_mod_inv(n, m);
82        for i in 1..=n {
83            assert_eq!(i as u64 * s[i] % m, 1);
84        }
85    }
86}
haar_lib/math/mod_ops/mod.rs

haar_lib/math/mod_ops/
mod.rs
