haar_lib/math/mod_ops/
inv.rs

1//! mod mでの逆元
2
3use crate::math::gcd_lcm::GcdLcm;
4use std::mem::swap;
5
6/// mod mでの逆元
7///
8/// **Time complexity** $O(\log m)$
9#[inline]
10pub fn mod_inv(mut a: u64, m: u64) -> Option<u64> {
11    if a.gcd(m) != 1 {
12        return None;
13    }
14
15    let mut b = m;
16    let mut u = 1;
17    let mut v = 0;
18
19    while b > 0 {
20        let t = a / b;
21
22        a -= t * b;
23        swap(&mut a, &mut b);
24
25        if u < t * v {
26            u += m - (t * v) % m;
27            if u >= m {
28                u -= m;
29            }
30        } else {
31            u -= t * v;
32        }
33        swap(&mut u, &mut v);
34    }
35
36    Some(u)
37}