算法

快速幂

题型(快速幂):求abab % p
思路解析
首先abab中可以设b=2t1+2t2+…+2tkb=2t1+2t2+…+2tk(二进制) 即将b转换为二进制表示
b&1就是判断b的二进制表示中第0位上的数是否为1,若为1,b&1=true,反之b&1=false 还不理解?进传送门
b&1也可以用来判断奇数和偶数,b&1=true时为奇数,反之b&1=false时为偶数

算法核心代码

求 m^k mod p，时间复杂度 O(logk)。

int qmi(int m, int k, int p)
{
    int res = 1 % p, t = m;
    while (k)
    {
        if (k&1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}

C++ 代码

迭代版(C++)
#include<iostream>
using namespace std;

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        long long  a,b,p,res=1;
        cin>>a>>b>>p;
        while(b)
        {
            if(b&1) res=res*a%p;
            b>>=1;//b右移了一位后,a也需要更新
            a=a*a%p;
        }
        cout<<res<<endl;

    }
}
递归版(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;
    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;
}