繰り返し二乗法(C++)

目的

$a^n \mod m$を$O(\log m)$で求めます。

計算量

$O(\log m)$

使い方

long long pow(long long a,long long n)
$a^{n} \mod 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;
}