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}