pub trait GcdRecip: Sized {
// Required method
fn gcd_recip(self, other: Self) -> (Self, Self);
}Expand description
最大公約数と逆元。
次の条件を満たす唯一の $(g, r)$ を返す。
- $g = \gcd(a, b)$
- $a\cdot r \equiv g \pmod{b}$
- $0\le r \lt b/g$
$a = 0$ のとき $g = b$ であり、$0\le g \lt b$ とはならないことに注意せよ1。
Complexity
$O(\log(\min\{a, b\}))$ time.
Examples
use nekolib::math::GcdRecip;
let (g, r) = 27_u32.gcd_recip(30);
assert_eq!(g, 3);
assert_eq!(r, 9);
assert_eq!((27 * r) % 30, g);$g = 0$ とすると $b/g$ が定義できないため。 ↩