当前位置 博文首页 > m0_50623076的博客：慢速乘与快速幂
目录
?
慢速乘(防一次乘法就爆long long)：
快速幂(加快次方速度)：
混合用：
有可能两个数相乘直接爆掉long long。化乘为加。a*b
任意数都可以拆分二进制，如果对应位是1，加上，否则右移。注意b二进制右移一位，a就要乘2。因为二进制每一位权值对应*2。
注意ans初始化为0，因为0加任何数都不变。
ll mul(ll a,ll b){//a*b?? %p
?????? ll ans = 0;
?????? while(b){
????????????? if(b%2 == 1)?? ans = (ans+a)%p;
????????????? b>>=1;
????????????? a = (a+a)%p;
?????? }
?????? return ans;
}如果指数太大，for遍历时间复杂度O(n)。快速幂O(logn)。
a^p 如果p是偶数，就相当于(a^2)^(p/2)。如果p是奇数，就让p-1再转化。也就是拆分a^p=a^(p-1)*a。这时候把a乘到ans中去，再转化。
注意ans初始化为1，因为1乘任何数不变。
ll qpow(ll a,ll b){//a^b? %p
?????? ll ans = 1;
?????? while(b){
????????????? if(b&1)?? ans = ans*a;
????????????? b >>= 1;
????????????? a = a*a;
?????? }
?????? return ans;
}也就是当需要大数的乘法。p是1e9-1e14。这时候可能乘一下就爆long long.这时候就需要把快速幂的乘法转化为慢速乘。
ll mul(ll a,ll b){//a*b?? %p
?????? ll ans = 0;
?????? while(b){
????????????? if(b%2 == 1)?? ans = (ans+a)%p;
????????????? b>>=1;
????????????? a = (a+a)%p;
?????? }
?????? return ans;
}
ll qpow(ll a,ll b){//a^b? %p
?????? ll ans = 1;
?????? while(b){
????????????? if(b&1)?? ans = mul(ans,a);
????????????? b >>= 1;
????????????? a = mul(a,a);
?????? }
?????? return ans;
}?
cs