题型(快速幂):求$a^b$ % p

思路解析

首先$a^b$中可以设$\color{red}{b=2^{t1}+2^{t2}+ \ldots +2^{tk}}$(二进制) 即将b转换为二进制表示
b&1就是判断b的二进制表示中第0位上的数是否为1,若为1,b&1=true,反之b&1=false 还不理解?进传送门
b&1也可以用来判断奇数和偶数,b&1=true时为奇数,反之b&1=false时为偶数

代码(C++)

迭代版(C++)

#include<iostream>
using namespace std;

int main()
{
    long long  a,b,p,res=1;
    scanf("%ld%ld%ld",&a,&b,&p);
    while(b)
    {
        if(b&1) res=res*a%p;
        b>>=1;//b右移了一位后,a也需要更新
        a=a*a%p;
    }
    printf("%ld\n",res%p);
}

递归版(C++)

#include<iostream>
using namespace std;
#define ull unsigned long long
ull quick_pow(ull a,ull b,ull p)
{
    if(b==0) return 1%p;
    a%=p;
    ull res=quick_pow(a,b>>1,p);
    if(b&1) return res*res%p*a%p;
    return res*res%p;
}
int main()
{
    int a,b,p;
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin>>a>>b>>p;
    cout<<quick_pow(a,b,p)<<endl;
    return 0;
}