haar_lib/math/mod_ops/
enum_inv.rs

1//! 0,1,..,nの素数mod pでの逆元を列挙する。
2
3/// 0,1,..,nの素数mod pでの逆元を列挙する。
4///
5/// **Time complexity** $O(n)$
6#[inline]
7pub fn enumerate_mod_inv(n: usize, p: u64) -> Vec<u64> {
8    let mut ret = vec![0; n + 1];
9
10    ret[1] = 1;
11
12    for i in 2..=n {
13        ret[i] = (p / i as u64) * (p - ret[(p % i as u64) as usize]) % p;
14    }
15
16    ret
17}