haar_lib/math/mod_ops/
inv_p.rs

1//! 素数mod pでの逆元
2
3use std::mem::swap;
4
5/// 素数mod pでの逆元
6///
7/// **Time complexity** $O(\log p)$
8#[inline]
9pub fn mod_inv_p(mut a: u64, p: u64) -> u64 {
10    let mut b = p;
11    let mut u = 1;
12    let mut v = 0;
13
14    while b > 0 {
15        let t = a / b;
16
17        a -= t * b;
18        swap(&mut a, &mut b);
19
20        if u < t * v {
21            u += p - (t * v) % p;
22            if u >= p {
23                u -= p;
24            }
25        } else {
26            u -= t * v;
27        }
28        swap(&mut u, &mut v);
29    }
30
31    u
32}