Бинарное возведение в степень¶
Бинарное (двоичное) возведение в степень — это приём, позволяющий возводить любое число в \(n\)-ую степень за \(O(log(n))\) умножений (вместо \(n\) умножений при обычном подходе).
Алгоритм¶
\[\begin{split}a^{n} =
\begin{cases}
1 &n = 0\\
(a^{n/2}) ^2 = a^{n/2} \times a^{n/2} &n = 2k\\
a^{n-1} \times n &n \neq 2k
\end{cases}\end{split}\]
ll binpow (ll a, ll n) {
if (n == 0)
return 1;
if (n % 2 == 1)
return binpow(a, n - 1) * a;
else {
ll b = binpow(a, n / 2);
return b * b;
}
}
\(a^{n} (mod) p\)¶
Поскольку мы знаем, что \(mod\) не вмешивается в умножение
\[a\times b\equiv (a \bmod m)\times(b \bmod m) \pmod m\]
ll binpow (ll a, ll n, ll p) {
if (n == 0)
return 1;
if (n % 2 == 1)
return binpow(a, n - 1, p) * a % p;
else {
ll b = binpow(a, n / 2, p);
return b * b % p;
}
}