|
|
## 快速幂与快速乘
|
|
|
|
|
|
### 一、快速幂
|
|
|
|
|
|
现有两个整数$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$
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
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$
|
|
|
因此，解决了上述两个问题，我们就可以实现 **快速幂** 的算法代码了：
|
|
|
```cpp {.line-numbers}
|
|
|
#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;
|
|
|
}
|
|
|
```
|
|
|
|
|
|
### 二、快速乘
|
|
|
同理，易得 **快速乘** 的算法：
|
|
|
快速乘主要用于防止有两个较大的数相乘而直接乘爆, 因为是加法, 怎么都不可能加爆，所以目的就是为了防止爆范围。
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
#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$ |
