快速幂模板（luogu P1226 【模板】快速幂||取余运算）

题目描述
输入b，p，k的值，求b^p mod k的值。其中b，p，k*k为长整型数。

输入输出格式
输入格式：
三个整数b,p,k.

输出格式：
输出“b^p mod k=s”

s为运算结果

k*k为长整型，所以要想直接for循环你就凉飕飕，高进度写的脑阔又疼，下面就介绍一个神奇的算法，快速幂！！

如2^{10,可以将10分成二进制下的1010,即2}10=(2(2^1))(2(2³⁾⁾⁼²22⁸⁼²10;

所以任意一个十进制数都可以转化成二进制数，对于a^b，可以将b拆分为二进制的数并逐步运算，可以在log n 下完成，非常快！！
话不多说，直接上代码。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int a,b,m;
int quickPow(int a,int b,int m){
    int sum=1;
    while(b){
        if(b&1) sum=sum*a%m;
        b>>=1;
        a=a*a%m;
    }
    return sum;
}
int main(){
    scanf("%d%d%d",&a,&b,&m);
    printf("%d\n",quickPow(a,b,m));
    return 0;
}

不理解的地方动手模拟一下代码，应该非常好理解

点个赞啦谢谢！！