快速幂取模算法
问题引入
快速幂用于求解 \(a ^ n\ mod\ m\) 的结果。
朴素的做法是直接用循环求解，时间复杂度 \(O(n)\)。
typedef long long ll;
ll power(ll a, ll n, ll m) {
ll result = 1;
for (int i = 0; i < n; ++i) {
result = (result * a) % m;
}
return result;
} 缺点很明显，一是效率低，容易超时，二是指数爆炸，容易爆 \(long\ long\)。
快速幂 分治思想
可以将问题分解成如下的子问题：
\[ a^n\ mod\ m = \begin{cases} 1\ mod\ m, & n = 0\\ (a^{n/2} \cdot a^{n/2}) \ mod\ m, & n是偶数\\ (a \cdot a^{n/2} \cdot a^{n/2})\ mod\ m, & n是奇数 \\ \end{cases} \]
写成递归的形式
\[ power(a, n, m) = \begin{cases} 1\% m, & n = 0\\ power(a^2, n/2, m) \% m, & n是偶数\\ (a * power(a^2, n/2, m)) \% m, & n是奇数 \\ \end{cases} \]
代码如下
typedef long long ll;
ll quick_mod(ll a, ll n, ll m) {
if (n == 0)
return 1;
else if (n % 2 == 0)
return quick_mod(a * a, n / 2, m) % m;
else
return ((a % m) * quick_mod(a * a, n / 2, m)) % m;
} 上述代码就是快速幂了。
朴素方法计算 \(a ^ n\) 其实计算了两遍 \(a ^ {n / 2}\) 再相乘，其实计算一次 \(a ^ {n / 2}\) 就够了，因为 \(a ^ {n / 2}\) 的平方就是 \(a ^ n\)。而计算 \(a ^ {n / 2}\) 又等价于计算 \(a ^ {n / 4}\) 的平方...，因此只需 \(log(n)\) 次就可以计算出结果。采用分而治之的方法将时间复杂度降为 \(O(log(n))\)。
由于递归比较慢，且容易爆栈，因此改成非递归的形式。
typedef long long ll;
ll quick_mod(ll a, ll n, ll m) {
if(n == 0)
return 1 % m;
ll res = 1;
while (n > 0) {
if (n % 2 == 0) {
a = (a * a) % m;
n = n / 2;
} else {
res = (res * a) % m;
a = (a * a) % m;
n = n / 2;
}
}
return res;
} 可以发现上述代码有重复部分，还可以简化。
typedef long long ll;
ll quick_mod(ll a, ll n, ll m) {
if(n == 0)
return 1 % m;
ll res = 1;
while (n > 0) {
if(n % 2) {
res = (res * a) % m;
}
a = (a * a) % m;
n = n / 2;
}
return res;
} 进一步优化
typedef long long ll;
ll quick_mod(ll a, ll n, ll m) {
if(!n)
return 1 % m;
ll res = 1;
while (n) {
if(n & 1) { // 二进制最后一位为 1是奇数
res = (res * a) % m;
}
a = (a * a) % m;
n >>= 1; // 右移一位就是整除 2
}
return res;
} 