繰り返し二乗法

#Purpose

Calculates $a^n \ \ (\text{mod}\ \ mod)$ in $O(\log(n))$.

#Time Complexity

$O(\log n)$

#Usage

mop(a,b,mod) returns $a^n \ \ (\text{mod}\ \ mod)$.

#Implementation

1
int mop(int a, int n, int mod = LLONG_MAX) {
2
  int res = 1;
3
  while (n > 0) {
4
    if (n & 1)
5
      res = res * a % mod;
6
    a = a * a % mod;
7
    n >>= 1;
8
  }
9
  return res;
10
}

#Verify

//TODO