Loading... ## 快速幂 快速幂，二进制取幂（Binary Exponentiation，也称平方法），是一个在 $O(logn)$ 的时间内计算 $a^n$ 的小技巧，而暴力的计算需要 $O(n)$ 的时间。而这个技巧也常常用在非计算的场景，因为它可以应用在任何具有结合律的运算中。 ### 算法原理 计算 $a^n$ ，最简单的方法就是将 n 个 a 相乘: ```cpp 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}$ 项。 ### 算法实现 #### 递归版本 ```cpp 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; } ``` #### 非递归版本 ```cpp 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; } ``` > 两种实现方法理论上计算次数是一样的。但由于递归会有一些额外的开销，所以非递归的版本会快一点。 ## 快速幂模 我们知道取模不会干涉乘法的运算，所以我们直接在计算的过程中取模即可。 ```cpp 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 并取模的运算的时侯，我们可以转化为加减操作防止溢出。 ```cpp /** * \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; } ``` ## Referrer https://oi-wiki.org/math/quick-pow/ 最后修改：2019 年 10 月 19 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏