Pangkat Cepat (modular)

Hitung $a^n \bmod m$ untuk $0 \le a \le 10^9$, $0 \le n \le 10^9$, $1 \le m \le 10^6$.

Mengalikan $a$ sebanyak $n$ kali terlalu lambat. Gunakan ide divide and conquer: $a^n = \left(a^{n/2}\right)^2$, sehingga hanya butuh $O(\log n)$ perkalian. Ambil mod setelah setiap perkalian agar angkanya tetap kecil (di bawah $10^{12}$, masih aman untuk number JavaScript).

power(2, 10, 1000) → 24      // 1024 mod 1000