快速幂/快速乘(取模)

作为第一篇的模板介绍，就来讲一讲比较简单又常用的快速幂与快速乘取模吧。
~~虽然我觉得大家可能都会了~~

## 快速幂取模

快速幂取模是很多比赛都会用到的东西，尤其是一些推导数学公式并要取模的题目更是常见。就比如**广工 14 届校赛中的**[1007 简单数学题](https://hodam.top/index.php/archives/73/#1007%E7%AE%80%E5%8D%95%E6%95%B0%E5%AD%A6%E9%A2%98)，你可能通过推导求出了最后的公式 $(n-1)\times 2^{n-1}+1$，但是题目里面的 n 又是在 `1e18` 的范围内的，如果使用 `for` 这样的循环语句进行计算的话，可能就是计算 100 年也求不出答案。于是，对于题目中有要求我们求解 $a^b \mod p$ 这样的问题，快速幂取模就派上了用途。

**用途**：快速幂能让我们在 `log(b)` 的复杂度下获得 $a^b \mod p$ 的结果。

**原理**：

比如我们计算 $2^{129}$，朴素的做法是：

$$
\begin{aligned}
int\ \ ans&\ =2;\\
ans&*=2; \\
ans&*=2; \\
.&.. \\
ans&*=2;\\
return&\ \ ans;
\end{aligned}
$$

而快速幂呢，则是先将幂指数分解，例如 `129`，我们就可以分解成 $(10000001)_B$。
这样的话，我们对于二进制位上是 1 的次方进行相乘。

例如：

$$
\begin{aligned}
int\ \ &ans=1;\\
int\ \ &a=2;\\
2^1在不在&10000001里面？\\
在:ans&*=a;\\
a&*=a;\\
2^2在不在&10000001里面？\\
在:ans&*=a;\\
a&*=a;\\
.&...\\
2^{128}在不在&10000001里面？\\
在:ans&*=a;\\
a&*=a;\\
return\ \  &ans;
\end{aligned}
$$

显然在上面的朴素做法中，我们对 ans 乘以了 128 次 2，算法的复杂度是 $O(n)$ 的。
而下面的算法中呢？ans 只判断了要不要和

$$
2^1\\
2^2\\
2^4\\
2^8\\
...\\
2^{128}
$$

相乘，操作数仅为 `log(b)` 次。

计算 $a^b \mod p$ 模板代码为：

```cpp
typedef long long ll;
ll qmod(ll a,ll b,ll p)
{
    ll ans=1;
    while(b)
    {
        if(b&1){
            ans*=a;
            ans%=p;
        }
        b>>=1;
        a*=a;
        a%=p;
    }
    return ans;
}
```