Loading... # 快速幂 模板题:[P1226 【模板】快速幂||取余运算 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)](https://www.luogu.com.cn/problem/P1226) ## 原理 1. $$ 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. $$ 2. $$ 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 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 0 如果觉得我的文章对你有用,请随意赞赏