DEV

C++ 割ったあまり

#C++#アルゴリズム

参考

「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜 - Qiita

分かりやすいmodの説明動画

— www.youtube.com

— www.youtube.com

基本

  • 掛け算、足し算、引き算は、計算途中で余りだす。
  • 引き算は、余りがマイナスになったらmodを足す。
  • 割り算は計算途中で余り出すのが通用しない。
  • 割り算は、逆元を出して、掛け算に変換する。

逆元

https://i.gyazo.com/d7b827885ebc4bfd89dadf462194c76b.png

  • 上記の式を満たすxのこと。
  • 例えば、mod 13の場合、1/7の逆元は2です。
  • 56 ÷ 7を13で割った余りを出すときに、56 x 2を考えればよくなります。

逆元の求め方

  • 1/a ≡ x (mod m) は、ax ≡ 1 (mod m) に変換できます。
  • 上記は、ax = my + 1 になるということです。
  • 変形すると、ax + my = 1 にできます。
  • aとmが互いに素であれば、整数x, yのペアが存在します。
  • xの出し方は、拡張ユークリッド互除法が使えます。

サンプルコード

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


LL extgcd(LL a, LL b, LL &x, LL &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  LL gcd = extgcd(b, a % b, x, y);
  LL oldX = x;
  x = y;
  y = oldX - a / b * y;
  return gcd;
}


LL modinv(LL a, LL m) {
  LL x, y;
  extgcd(a, m, x, y);
  return x;
}


int main() {
  LL a = 7, b = 13;
  LL x = modinv(a, b);
  cout << x << endl;
}

結果

2