快速幂
快速幂，二进制取幂（Binary Exponentiation，也称平方法），是一个在 $O(logn)$ 的时间内计算 $a^n$ 的小技巧，而暴力的计算需要 $O(n)$ 的时间。而这个技巧也常常用在非计算的场景，因为它可以应用在任何具有结合律的运算中。
算法原理
计算 $a^n$ ，最简单的方法就是将 n 个 a 相乘:
typedef long long long_t;
long_t pow(const long_t& base, const long_t& index)
{
long_t res = 1;
for (auto i = 0; i < index; i++)
res *= base;
return res;
}但如果 $a$ 和 $n$ 的值比较大的时候，这个方法就不是很适用了。不过我们知道:
$$ a^{b+c} = a^b · a^c, a^{2b} = a^b · a^b = (a^b)^2 $$
这样的话，我们就可以将指数拆成二进制来减少运算次数。举个例子:
$$ 3^{13} = 3^{(1101)_2} = (1*3^1) * (0*3^2) * (1*3^4) * (1*3^8) $$
任意一个数 $n$ 都有 $log_2(n-1) + 1$ 个二进制位，所以如果我们知道了 $a^1$ , $a^2$ , $a^4$ , ... , $a^{2^{log_2n}}$ , 我们就只需
$O(log n)$ 次计算就可以算出 $a^n$ 。
那么问题就转化为了如何求出 $a^1$ , $a^2$ , $a^4$ , ... , $a^{2^{log_2n}}$。这个问题很简单，因为这个数列中任意一个数(除了第一个)都是其前一个数的平方。根据这个很容易得到计算这个数列的时间复杂度也是 $O(log n)$ 。
将上述过程说得形式化一些，如果把 $n$ 写作二进制为 $(n_tn_{t-1}...n_1n_0)_2$，那么有：
$$ n = n_t2^t + n_{t-1}2^{t-1} + ... + n_12^1 + n_02_0 $$
其中 $n_i \in \{0, 1\}$ 。那么就有
$$ a^n = a^{n_t2^t + n_{t-1}2^{t-1} + ... + n_12^1 + n_02_0} = a^{n_t2^t} \times a^{n_{t-1}2^{t-1}} \times ... \times a^{n_12^1} \times a^{n_02_0} $$
根据上式我们发现，原问题被我们转化成了形式相同的子问题的乘积，并且我们可以在常数时间内从 $2_i$ 项推出 $2_{i+1}$ 项。
算法实现
递归版本
typedef long long long_t;
long_t quick_pow(const long_t& base, const long_t& index)
{
if (index == 0)
return 1;
const long_t res = quick_pow(base, index / 2);
if (index % 2 == 1)
return res * res * base;
else
return res * res;
}非递归版本
typedef long long long_t;
long_t quick_pow(const long_t& _base, const long_t& _index)
{
long_t index = _index;
long_t base = _base;
long_t res = 1;
while (index != 0)
{
if ((index & 1) == 1)
res *= base;
index >>= 1;
base *= base;
}
return res;
}两种实现方法理论上计算次数是一样的。但由于递归会有一些额外的开销，所以非递归的版本会快一点。
快速幂模
我们知道取模不会干涉乘法的运算，所以我们直接在计算的过程中取模即可。
typedef long long long_t;
long_t quick_pow_mod(const long_t& _base, const long_t& _index, const long_t& m)
{
long_t index = _index % m;
long_t base = _base % m;
long_t res = 1;
while (index != 0)
{
if ((index & 1) == 1)
res = res * base % m;
index >>= 1;
base = base * base % m;
}
return res % m;
}模意义下的大整数乘法
与二进制取幂的思想一样，这次我们将其中的一个乘数表示为若干个 2 的整数次幂的和的形式。因为在对一个数做乘 2 并取模的运算的时侯，我们可以转化为加减操作防止溢出。
/**
* \brief 模意义下的大整数乘法
* \param factor_1 因数 1
* \param factor_2 因数 2
* \param m 取模, 值为0表示不取模
*/
inline long_t multiply_mod(const long_t& factor_1, const long_t& factor_2, const long_t& m = 0)
{
long_t a = factor_1 % m;
long_t b = factor_2 % m;
long_t res = 0;
while (b != 0)
{
if ((b & 1) == 1)
res = (m == 0 ? res + a : (res + a) % m);
a <<= 1;
if (m != 0 && a > m)
a %= m;
b >>= 1;
}
return res;
}