快速幂算法

之前听过快速幂，似懂非懂，不明觉厉……

今天洛谷智能推荐了一道快速幂的模板题，写了半天还是看题解过的……

Part1

对指数进行二进制拆分

当然不用真的拆，只是用位运算即可。

主要是两个位运算：

>>和&

右移和按位与

 

右移就相当于除以二，但是速度更快，是在二进制下将所有位向右移动一些位。

按位与则是对两个操作数的每一位分别与，一个数&1就是它的最低位，可以快速的判断奇偶性。

Part2

公式（套路）

（图片来源自互联网）

如果p为奇数

　　当前答案乘以底数

p除以2

底数自乘

继续判断奇偶，直到p等于0

Attention

如果数据较大，记得取模

最好每算一步，就取一次模

所有数据最好都开long long，以防还没有取模就溢出了

答案最后再取一次模（以防像计算1^0 mod 1这样的式子，因为没有进行快速幂而跳过取模）

Problem

Solution

不就是我嘛……

Code

#include
     
      using namespace std;long long b,p,k,ans;int main(){    cin>>b>>p>>k;    cout<
      <<"^"<
<<" mod "<
        
         <<"=";//先输出,比较方便    ans=1;    while(p>0)    {        if(p&1)            ans*=b;        p>>=1;        b*=b;        b%=k;        ans%=k;    }    cout<
        
     

End