逆元 (modinv)

目的

mod m の世界において、aに対する逆元a^-1を計算する。
これを利用することで、剰余同士の割り算が可能になる。

制約

aとmは互いに素である。

オーダー

コード

//拡張ユークリッド互除法
long long int ext_gcd(long long int a, long long int b, long long int &x, long long int &y)
{
  if (b == 0)
  {
    x = 1;
    y = 0;
    return a;
  }
  long long int q = a / b;
  long long int g = ext_gcd(b, a-q*b, x, y);
  long long int z = x-q*y;
  x = y;
  y = z;
  return g;
}

//aとmは互いに素, a^(-1) mod m
long long int modinv(long long int a, long long int m) 
{
  long long int x, y;
  ext_gcd(a, m, x, y);
  x %= m;
  if (x < 0)
    x += m;
  return x;
}

コードテスト

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
const ll MOD = pow(10, 9) + 7;

//拡張ユークリッド互除法
long long int ext_gcd(long long int a, long long int b, long long int &x, long long int &y)
{
  if (b == 0)
  {
    x = 1;
    y = 0;
    return a;
  }
  long long int q = a / b;
  long long int g = ext_gcd(b, a-q*b, x, y);
  long long int z = x-q*y;
  x = y;
  y = z;
  return g;
}

//aとmは互いに素, a^(-1) mod m
long long int modinv(long long int a, long long int m) 
{
  long long int x, y;
  ext_gcd(a, m, x, y);
  x %= m;
  if (x < 0)
    x += m;
  return x;
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);

  long long int a = 12345678900000;
  long long int b = 100000;

  a %= MOD;

  cout << a * modinv(b, MOD) % MOD << endl;
}

123456789

出典

kirika-comp.hatenablog.com

qiita.com