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

ll binpow(ll a, ll b) {
  ll res = 1;
  while (b > 0) {
    if (b & 1) res *= a;
    a *= a;
    b >>= 1;
  }
  return res;
}

ll binpow(ll a, ll b, ll m) {
  if (m == 1) return 0;
  a %= m;
  ll res = 1;
  while (b > 0) {
    if (b & 1) res = (__int128)res * a % m;
    a = (__int128)a * a % m;
    b >>= 1;
  }
  return res;
}

25 linesutf-8

$cat explanation_notes.md

notes_viewer --renderedmarkdown (math enabled)

Binary Exponentiation

Compute $a^n$ in $O(\log n)$ multiplications by decomposing the exponent into its binary representation:

a^n = \prod_{i:\, b_i = 1} a^{2^i}

How It Works

Start with

\text{result} = 1

While

n > 0

: if the lowest bit of

n

is 1, multiply result by current base

Square the base and right-shift

n

each iteration

For the modular version, reduce mod

m

after every multiplication

When to Use

Computing

a^n \bmod m

for very large

n

Matrix exponentiation for Fibonacci / linear recurrences

Permutation exponentiation — applying a permutation

k

times

Counting walks of length

k

via adjacency matrix powers

Complexity

Time —

O(\log n)

multiplications

Space —

O(1)