首页 > 代码库 > 快速幂（讲解）
快速幂（讲解）
对于快速幂有人会问：要快速幂干什么，cmath库里的pow就很好用啊！
但是你有没有想过他的时间复杂度！假设我们要求a^b,按照朴素算法就是把a连乘b次，这样一来时间复杂度是O(b)也即是O(n)级别，况且有些大佬说：用stl比用循环还慢。但是我们在这里所说的快速幂的目的就是做到快速求幂，快速幂能做到O(logn)，快了好多好多。
快速幂的原理是用二分及二进制优化的。
假设我们要求a^b,那么我们在这里如果我们要用快速幂来做这道题，我们可以把b拆成二进制，该二进制的第i位的权为2^(i-1),例如：
当b==11时，a^11=a^(2^0+2^1+2^3)
11的二进制是1011，11 = 2³×1 + 2²×0 + 2¹×1 + 2º×1，因此，我们将a¹¹转化为算 a^(2^0)*a^(2^1)*a^(2^3) ，有没有发现现在就快多了？
(⊙o⊙)…貌似这两项也不是很好求的样子。。。。
没事，我们在下面还会讲到的。
由于是二进制，很自然地想到用位运算这个强大的工具： & 和 >>
各种模板
one。快速幂普通版（未取模）
int kpow(int n,int k){ long long int res=1; while(k) { if(k&1) res*=n; n*=n; k=k>>1;//每次都将k/2，为使用的二进制，使改代码更快。 } return res;}
two。快速幂取余版
int kpow(long long n,long long k,long long mod){ long long int res=1; while(k) { if(k&1) res=(res*n)%mod; n=(n*n)%mod; k=k>>1;//每次都将k/2，为使用的二进制，使改代码更快。 } return res;}
three。由于若题目数据太大，会使快速幂时由于是先乘后取余，乘后会导致越界，故可采用模拟乘法，在模拟乘法过程中取余数
即模拟乘法+快速幂
int qpow(long long n,long long k,long long mod){ long long int res=1; while(k) { if(k&1) res=(res*n)%mod; n=(n*n)%mod; k=k>>1; } return res;}/******************华丽的分割线*****************************/ /****模拟乘法****/ int Analog multiplication(long long n,long long k,long long mod){ long long res=0; while(k) { if(k&1)res=(res+n)%mod; n=(2*n)%mod; k=k>>1; } return res;} /****快速幂****/ int qpow(long long n,long long k,long long mod){ long long res=1; while(k) { if(k&1) res=Analog multiplication(n,k,mod); n=Analog multiplication(n,n,mod); k=k>>1; } return res;}
代码很短，死记也可行，但最好还是理解一下吧，其实也很好理解，以b==11为例，b=>1011,二进制从右向左算，但乘出来的顺序是 a^(2^0)*a^(2^1)*a^(2^3)，是从左向右的。我们不断的让n*=n目的即是累乘，以便随时对ans做出贡献。
其中要理解n*=n这一步，看：：：n*n==n^2,下一步再乘，就是n^2*n^2==n^4,然后同理 n^4*n4=n^8,,,,,see?是不是做到了n-->n^2-->n^4-->n^8-->n^16-->n^32.......指数正是 2^i 啊，再看上 面的例子，a¹¹= a^(2^0)*a^(2^1)*a^(2^3)，这三项是不是完美解决了，，嗯，快速幂就是这样。
顺便啰嗦一句，由于指数函数是爆炸增长的函数，所以很有可能会爆掉int的范围，根据题意决定是用 long long啊还是unsigned int啊还是mod某个数啊自己看着办。
快速幂（讲解）