python/TangDou/Topic/快速幂、快速乘.md

## 快速幂与快速乘

### 一、快速幂

现有两个整数$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$