ACM模板——快速模幂算法

2019-04-13 14:52发布

站内文章 / 模拟电子
17135 0 959

注释版：

#include #include #define mem(a,b) memset(a,b,sizeof a); using namespace std; typedef long long ll; /* 快速模幂 - 详解 对于任何一个整数的模幂运算： a^b%c 对于b可以拆成二进制的形式（b0对应的是b二进制的第一位）： b=b0+b1*2+b2*2^2+...+bn*2^n 那么我们的a^b运算就可以拆解成： a^b0 * a^(b1*2^1) *...* a^(bn*2^n) 对于b来说，二进制位不是0就是1，那么对于bx为0的项我们的计算结果是1就不用考虑了，我们真正想要的其实是b的非0二进制位。 那么假设除去了b的0的二进制位之后我们得到的式子是： a^(bx*2^x) *...* a(bn*2^n) 这里我们再应用我们一开始提到的公式，那么我们的a^b%c运算就可以转化为： (a^(bx*2^x)%c) *...* (a^(bn*2^n)%c) 这样的话，我们就很接近快速幂的本质了，我们会发现令： A1=(a^(bx*2^x)%c) ... An=(a^(bn*2^n)%c) 这样的话，An 始终是 A(n-1) 的【平方倍】，依次递推。 */ // 快速模幂 // 朴素的时间复杂度：O(n) // 快速幂时间复杂度：O(logn) ll power(ll a,ll b,ll c) { ll ans=1; // 记录结果 a=a%c; // 预处理，使得a处于c的数据范围之下 while(b!=0) // ~while(b) { if(b&1) ans=ans*a%c; // 如果b的二进制位不是0，那么我们的结果是要参与运算的         else ans=ans*1%c; // b的二进制位是1 b>>=1; // 不断遍历b的二进制位 a=a*a%c; // 不断加倍 } return ans; }

简化版：

#include #include #define mem(a,b) memset(a,b,sizeof a); using namespace std; typedef long long ll; ll power(ll a,ll b,ll c) { ll ans=1; a=a%c; while(b) { if(b&1) ans=ans*a%c; b>>=1; a=a*a%c; } return ans; }

热门文章