模板代码:
typedef long long ll;
ll quick_pow(ll a,ll b){
ll res = 1;
while(b > 0){
if(b & 1){
res *= a;
}
a *= a;
b >>= 1;
}
return res;
}
这里以a^10为例,说一下对快速幂代码的理解。
右下角的o表示这是十进制数 这里写错了,图片中不应该是o,应该d,d表示这是十进制数 ,b表示这是二进制数。可以得到以下的几个式子,都是逐步变换得出来的。
最后一个式子可以很好的理解模板代码,可以看到,等号右侧有4项,这4项的幂次是1010,也就是10的二进制表达的每一位。所以,这就要求出幂指数10的二进制的每一位,而且,最后一个式子中,幂次是0的项(第二项和第四项)其实是1,对结果没有贡献,那我们就可以考虑,求出幂指数10的每一位以后,进行判断,如果这一位是0,那就不予考虑了,如果是1的话,就把这一项乘到原有的结果中,也就是代码中的这几行
if(b & 1){
res *= a;
}
}
每次判断以后,要把幂次10向右移1位,准备进行下一次的判断。
b >>= 1;
观察第四个式子,看每一项的括号里边,当前项就是他右边项的平方,所以这还需要一个变量来控制这个东西,每次自己乘自己就可以了,代码里用的底数a本身。
a *= a;
同理,可以得到快速乘法的代码
int qmul(int a, int b){
int ans = 0;
while(b){
if(b & 1){
ans += a;
}
a += a;
b >>= 1;
}
return ans;
}