逆元(フェルマーの小定理,C++)

目的

素数$m$について、$ax=1\mod m$なる整数$x$を$O(\log m)$で求めます。

計算量

$O(\log m)$

使い方

long long inv(long long a, long long mo)
$a^{-1}\mod m$をreturnします。
long long pow(long long a, long long m)
$a^m\mod m$を$O(\log m)$でreturnします。

ソースコード

long long pow(long long a,long long n){
  long long ret=1;
  for(;n>0;n>>=1,a=a*a%m){
    if(n%2==1){
      ret=ret*a%m;

    }
  }
  return ret;
}

long long inv(long long a){
  return pow(a,m-2);
}