3.8 KiB
快速幂与快速乘
一、快速幂
现有两个整数$m、n$，求m^n 除以$1000000007$之后的余数。
输入：输入整数$m、n$，用$1$个空格隔开，占$1$行。
输出：输出$m^n$除以$1000000007$之后的余数，占$1$行。
限制：$1<=m<=100$，1<=n<=10^9
输入示例：
5 8
输出实例：
390625
解决算法复杂度问题
如果用最直接的方法求$x^n$，我们需要进行$n-1$次乘法运算，算法复杂度为$O(n)$。
快速幂的思想其实是二进制的思想：
(21)_{10}=(10101)_2
从右到左遍历每一个二进制数位,分两条线进行：
- 数字$a$每次平方后写入
a,即a*=a - 每个数位检查当前二进制数位是否为
1,如果为1,则需要多累乘一个当前的a
int qmi(int a, int b){
int ans = 1;
while(b){
if(b&1) ans*= a; //当b为奇数时，乘以余下的一个a
b >>= 1;//位运算，右移1位，相当于除以2
a*= a;
}
return ans;
}
这样，递归函数的参数$n$逐次减半，因此算法复杂度为$O(logn)$。
这样，递归函数的参数n逐次减半，因此算法复杂度为O(logn)。
#### 解决取模运算问题 在遇到 求某计算结果除以$M$（本题中是$1000000007$）之后的余数 这类题时，可以按下述方法计算（这里$a$除以$b$之后的余数记作$a%b$）。
- 计算加法时，每相加一次执行一次
\%M - 计算减法时，给被减数加上$M$之后，先算减法，后算
\%M - 计算乘法时，每相乘一次执行一次
\%M
引理$1$：积的取余等于取余的积的取余
(a*b)\%M=[(a\%M)*(b\%M)]\%M
证明： 设$a$除以$M$的余数和商分别为$ar$、$aq$， $b$除以$M$的余数和商分别为$br、bq$， 即 $a/M=aq……ar$， $b/M=bq……br$，
则有：
$a∗b =(aq∗M+ar)∗(bq∗M+br) =aq∗bq∗M^2 +ar∗bq∗M+aq∗br∗M+ar∗br =(aq∗bq∗M+ar∗bq+aq∗br)∗M+ar∗br$
即易得：
(a*b)\%M=(ar*br) \%M=[(a\%M)*(b\%M)]\%M
引理2:幂的取余等于取余的幂再取余
公式：a^b\%M=(a\%M)^b\%M
证明：
(a\%M)^b\%M\\= [(a*1)\%M]^b\%M\\=\{[(a\%M)*(1\%M)]\%M\}^b\%M\\=[(a\%M)\%M]^b\%M
由上面公式迭代：
[(a\%M)^b]\%M=a^b\%M
因此，解决了上述两个问题，我们就可以实现 快速幂 的算法代码了：
#include <iostream>
using namespace std;
typedef long long LL;
const LL mod = 1e9 + 7;
/*
测试用例：
5 8
结果：
390625
*/
//快速幂
LL ksm(LL a, LL b) {
LL ans = 1;
a %= mod;
while (b) {
if (b & 1) ans = (ans * a) % mod;
b >>= 1; //位运算，右移1位，相当于除以2
a = (a * a) % mod;
}
return ans;
}
int main() {
LL a, b;
cin >> a >> b;
printf("%lld\n", ksm(a, b));
return 0;
}
二、快速乘
同理，易得 快速乘 的算法： 快速乘主要用于防止有两个较大的数相乘而直接乘爆, 因为是加法, 怎么都不可能加爆，所以目的就是为了防止爆范围。
#include <iostream>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
/*
测试用例:
10000000 10000000
答案：
999300007
*/
//快速乘，计算a*b%mod
LL ksc(LL a, LL b) {
LL ans = 0;
a %= mod;
while (b) {
if (b & 1) ans = (ans + a) % mod;
b >>= 1; //位运算，右移1位，相当于除以2
a = (a + a) % mod;
}
return ans;
}
int main() {
LL a, b;
cin >> a >> b;
printf("%lld\n", ksc(a, b));
return 0;
}
三、总结
-
快速幂 解决
a^b\%mod -
快速乘 解决
a*b\%mod