pub fn extgcd_recurse(a: i64, b: i64) -> (i64, i64, i64)Examples found in repository?
crates/competitive/src/math/gcd.rs (line 44)
40pub fn extgcd_recurse(a: i64, b: i64) -> (i64, i64, i64) {
41 if b == 0 {
42 (a, 1, 0)
43 } else {
44 let (g, x, y) = extgcd_recurse(b, a % b);
45 (g, y, x - (a / b) * y)
46 }
47}
48
49#[codesnip::entry]
50pub fn extgcd(mut a: i64, mut b: i64) -> (i64, i64, i64) {
51 let (mut u, mut v, mut x, mut y) = (1, 0, 0, 1);
52 while a != 0 {
53 let k = b / a;
54 x -= k * u;
55 y -= k * v;
56 b -= k * a;
57 std::mem::swap(&mut x, &mut u);
58 std::mem::swap(&mut y, &mut v);
59 std::mem::swap(&mut b, &mut a);
60 }
61 (b, x, y)
62}
63
64pub fn extgcd_binary(mut a: i64, mut b: i64) -> (i64, i64, i64) {
65 if b == 0 {
66 return (a, 1, 0);
67 } else if a == 0 {
68 return (b, 1, 0);
69 }
70 let k = (a | b).trailing_zeros();
71 a >>= k;
72 b >>= k;
73 let (c, d) = (a, b);
74 let (mut u, mut v, mut s, mut t) = (1, 0, 0, 1);
75 while a & 1 == 0 {
76 a /= 2;
77 if u & 1 == 1 || v & 1 == 1 {
78 u += d;
79 v -= c;
80 }
81 u /= 2;
82 v /= 2;
83 }
84 while a != b {
85 if b & 1 == 0 {
86 b /= 2;
87 if s & 1 == 1 || t & 1 == 1 {
88 s += d;
89 t -= c;
90 }
91 s /= 2;
92 t /= 2;
93 } else if b < a {
94 std::mem::swap(&mut a, &mut b);
95 std::mem::swap(&mut u, &mut s);
96 std::mem::swap(&mut v, &mut t);
97 } else {
98 b -= a;
99 s -= u;
100 t -= v;
101 }
102 }
103 (a << k, s, t)
104}
105
106pub fn modinv_recurse(a: u64, m: u64) -> u64 {
107 (extgcd_recurse(a as i64, m as i64).1 % m as i64 + m as i64) as u64 % m
108}