const fn is_direct_table_mod<const P: u32>() -> boolExamples found in repository?
crates/competitive/src/math/fast_prime_mod.rs (line 16)
15const fn table_k<const P: u32>() -> usize {
16 if is_direct_table_mod::<P>() {
17 P as usize - 1
18 } else {
19 K
20 }
21}
22
23const fn table_len<const P: u32>() -> usize {
24 2 * table_k::<P>() + 1
25}
26
27/// Fast online inverse and power queries for a prime modulus.
28pub struct FastPrimeMod<const P: u32, const BUILD_INV: bool = true, const BUILD_POW: bool = true> {
29 root: u32,
30 pow_lo: Box<[u32]>,
31 pow_hi: Box<[u32]>,
32 frac: Box<[u32]>,
33 log: Box<[u32]>,
34 inv: Box<[u32]>,
35}
36
37impl<const P: u32, const BUILD_INV: bool, const BUILD_POW: bool>
38 FastPrimeMod<P, BUILD_INV, BUILD_POW>
39{
40 /// Builds the tables enabled by the const generic mode.
41 ///
42 /// # Panics
43 ///
44 /// Panics if `P` is not an odd prime or if `P >= 2^30`.
45 pub fn new() -> Self {
46 assert!(
47 BUILD_INV || BUILD_POW,
48 "at least one of BUILD_INV or BUILD_POW must be true"
49 );
50 assert!(P < 1 << 30, "P must be less than 2^30");
51 assert!(
52 P % 2 == 1 && miller_rabin(P as u64),
53 "P must be an odd prime"
54 );
55
56 let (root, pow_lo, pow_hi, log) = if BUILD_POW {
57 let root = if P == 998_244_353 {
58 3
59 } else {
60 primitive_root(P as u64) as u32
61 };
62 let (pow_lo, pow_hi) = build_pow::<P>(root);
63 let log = build_log::<P>(root, &pow_lo, &pow_hi);
64 (root, pow_lo, pow_hi, log)
65 } else {
66 (
67 0,
68 Vec::new().into_boxed_slice(),
69 Vec::new().into_boxed_slice(),
70 Vec::new().into_boxed_slice(),
71 )
72 };
73 let inv = if BUILD_INV {
74 build_inv::<P>()
75 } else {
76 Vec::new().into_boxed_slice()
77 };
78 let frac = if is_direct_table_mod::<P>() {
79 Vec::new().into_boxed_slice()
80 } else {
81 build_frac::<P>()
82 };
83 Self {
84 root,
85 pow_lo,
86 pow_hi,
87 frac,
88 log,
89 inv,
90 }
91 }
92
93 /// Returns the prime modulus.
94 #[inline]
95 pub fn modulus(&self) -> u32 {
96 P
97 }
98
99 #[inline(always)]
100 fn small_fraction(&self, x: u32) -> (usize, u32) {
101 let k = table_k::<P>();
102 if is_direct_table_mod::<P>() {
103 debug_assert!(1 <= x && x < P);
104 return (k + x as usize, 1);
105 }
106 let packed = self.frac[(x >> FRAC_SHIFT) as usize];
107 let a = packed >> 16;
108 let b = packed & 0xffff;
109 let t = x.wrapping_mul(b).wrapping_sub(a.wrapping_mul(P));
110 debug_assert!({
111 let t = x as i64 * b as i64 - a as i64 * P as i64;
112 t != 0 && -(k as i64) <= t && t <= k as i64
113 });
114 ((k as u32).wrapping_add(t) as usize, b)
115 }