int.mod.inv

整数 \(a\)\(m\) について \[a^{-1} \bmod m\] の存在のための必要十分条件は \(a,m\) が互いに素であること. 存在する時, これは拡張ユークリッドの互除法で次のように解ける.

int.mod.inv.rs

逆数が存在しない場合は None を返す.

fn intmod(a: i64, m: i64) -> Option<i64> {
    fn exgcd(r0: i64, a0: i64, b0: i64, r: i64, a: i64, b: i64) -> (i64, i64, i64) {
        if r > 0 {
            exgcd(r, a, b, r0 % r, a0 - r0 / r * a, b0 - r0 / r * b)
        } else {
            (a0, b0, r0)
        }
    }
    let (a, _, r) = exgcd(a, 1, 0, m, 0, 1);
    if r != 1 {
        None
    } else {
        Some(((a % m) + m) % m)
    }
}

int.mod.inv.cc

tuple<int, int, int> ex_gcd(int x, int y) {
  int r0 = x, a0 = 1, b0 = 0;
  for (int r = y, a = 0, b = 1; r > 0; ) {
    int r2 = r0 % r;
    int a2 = a0 - r0 / r * a;
    int b2 = b0 - r0 / r * b;
    r0 = r; r = r2;
    a0 = a; a = a2;
    b0 = b; b = b2;
  }
  return make_tuple(a0, b0, r0);
}

int modinv(int a, int m) {
  auto r = ex_gcd(a, m);
  if (get<2>(r) != 1) throw;
  int b = get<0>(r);
  while (b < 0) b += m;
  return b;
}