快速幂

# 快速幂

模板题:[P1226 【模板】快速幂||取余运算 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)](https://www.luogu.com.cn/problem/P1226)

## 原理

$$
a^{n}=\left\{\begin{matrix}
  a^{n-1}\cdot a & n\space mod\space{2}=1 \\
  a^{\frac{n}{2}}\cdot a^{\frac{n}{2}}& n\space mod\space2=0 \space and \space n\ne 0\\
  1&n=0
\end{matrix}\right.
$$

$$
a^n = a^{{0\space or\space 1}\cdot 2^0}+a^{{0\space or\space 1}\cdot 2^1}+...+a^{{0\space or\space 1}\cdot 2^{\log_{2}{n}}}
$$

其中的$0\space or\space 1$取决于$(n)_2$的第$k$位上是0还是1

## 代码

```cpp
#include <iostream>
using namespace std;
long long a, b, p;
template <class T>
T EBS(T a, T b, const T p)
{
    T ans = 1 % p;
    a %= p;
    for (; b; b >>= 1)
    {
        if (b & 1) ans = 1ll * (ans * a) % p;
        a = 1ll * (a * a) % p;
    }
    return ans;
}
int main()
{
     cin >> a >> b >> p;
     printf("%d^%d mod %d=%d", a, b, p, EBS(a, b, p));
}
```

## 扩展

只要a的数据类型支持**乘法**且**满足结合律** ，快速幂的算法都是有效的

## 参考文章

[算法学习笔记(4)：快速幂 - 知乎 (zhihu.com)](https://zhuanlan.zhihu.com/p/95902286)

最后修改：2023 年 03 月 13 日