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

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

Required Methods§

source

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

Implementations on Foreign Types§

source§

impl GcdRecip for isize

source§

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

source§

impl GcdRecip for i16

source§

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

source§

impl GcdRecip for i32

source§

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

source§

impl GcdRecip for i128

source§

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

source§

impl GcdRecip for u32

source§

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

source§

impl GcdRecip for u128

source§

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

source§

impl GcdRecip for u64

source§

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

source§

impl GcdRecip for i64

source§

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

source§

impl GcdRecip for i8

source§

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

source§

impl GcdRecip for usize

source§

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

source§

impl GcdRecip for u8

source§

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

source§

impl GcdRecip for u16

source§

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

Implementors§