快速幂:快速求$a^b$ % p的问题,时间复杂度:$O(logb)$,若对于n组数据,那么时间复杂度为$O(n \ast logb)$

一.暴力解法 $\quad O(n \ast b) \quad 会\color{red}{TLE}$

基本思路:对于n组数据,分别循环b次求出$a^b \quad mod \quad p$

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int a,b,p;
        long long res=1;
        cin>>a>>b>>p;
        while(b--)
            res = res * a %p;
        cout<<res<<endl;
    }
}

二.快速幂解法 $\quad O(n \ast logb)$

基本思路:

1. 预处理出$a^{2^0},a^{2^1},a^{2^2},\ldots,a^{2^{logb}}.这b个数$
2. 将$a^b用a^{2^0},a^{2^1},a^{2^2},\ldots,a^{2^{logb}}这b种数来组合,即组合成a^b=a^{2^{x_1}}\times a^{2^{x_2}}\times \ldots \times a^{2^{x_t}}=a^{2^{x_1}+2^{x_2}+\ldots+2^{x_t}}$即用二进制表示
   为什么b可用$a^{2^0},a^{2^1},a^{2^2},\ldots,a^{2^{logb}}这b个数来表示?$∵$\color{brown}{二进制可以表示所有数,且用单一用二进制表示时,b单一表示最大可表示为二进制形式的2^{logb} }$

注意:

• b&1就是判断b的二进制表示中第0位上的数是否为1,若为1,b&1=true,反之b&1=false 还不理解?进传送门
  b&1也可以用来判断奇数和偶数,b&1=true时为奇数,反之b&1=false时为偶数

快速幂之迭代版 $\quad O(n \ast logb)$

#include<iostream>
using namespace std;
long long qmi(long long a,int b,int p)
{
    long long res=1;
    while(b)//对b进行二进制化,从低位到高位
    {
        //如果b的二进制表示的第0位为1,则乘上当前的a
        if(b&1) res = res *a %p;
        //b右移一位
        b>>=1;
        //更新a,a依次为a^{2^0},a^{2^1},a^{2^2},....,a^{2^logb}
        a=a*a%p;
    }
    return res;
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        cin.tie(0);
        ios::sync_with_stdio(false);
        int a,b,p;
        long long res=1;
        cin>>a>>b>>p;
        res = qmi(a,b,p);
        cout<<res<<endl;
    }
    return 0;
}

快速幂之递归版 $\quad O(n \ast logb)$

#include<iostream>
using namespace std;
#define ull unsigned long long
ull quick_pow(ull a,ull b,ull p)
{
    if(b==0) return 1;
    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 n;
    cin>>n;
    while(n--)
    {
        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;
}

$\color{brown}{喜欢题解的话,欢迎点赞、收藏、关注(三连)喔,如有什么疑问,欢迎评论下方指出}$