Trait nekolib::math::GcdRecip

pub trait GcdRecip: Sized {
    // Required method
    fn gcd_recip(self, other: Self) -> (Self, Self);
}

最大公約数と逆元。

次の条件を満たす唯一の $(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$ とはならないことに注意せよ¹。

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);

---

1. $g = 0$ とすると $b/g$ が定義できないため。 ↩

Required Methods

fn gcd_recip(self, other: Self) -> (Self, Self)

Implementations on Foreign Types

impl GcdRecip for isize

fn gcd_recip(self, other: Self) -> (Self, Self)

impl GcdRecip for i16

fn gcd_recip(self, other: Self) -> (Self, Self)

impl GcdRecip for i32

fn gcd_recip(self, other: Self) -> (Self, Self)

impl GcdRecip for i128

fn gcd_recip(self, other: Self) -> (Self, Self)

impl GcdRecip for u32

fn gcd_recip(self, other: Self) -> (Self, Self)

impl GcdRecip for u128

fn gcd_recip(self, other: Self) -> (Self, Self)

impl GcdRecip for u64

fn gcd_recip(self, other: Self) -> (Self, Self)

impl GcdRecip for i64

fn gcd_recip(self, other: Self) -> (Self, Self)

impl GcdRecip for i8

fn gcd_recip(self, other: Self) -> (Self, Self)

impl GcdRecip for usize

fn gcd_recip(self, other: Self) -> (Self, Self)

impl GcdRecip for u8

fn gcd_recip(self, other: Self) -> (Self, Self)

impl GcdRecip for u16

fn gcd_recip(self, other: Self) -> (Self, Self)

Implementors