【算法】数论---快速幂

什么是快速幂？

快速幂:快速求a^b % p的值,时间复杂度:O(logb)

---

一、暴力写法--- 循环b次求出a^b mod p  (时间复杂度:O(b))

int a,b,p; cin>>a>>b>>p;

long long res=1;

while(b--)res = res * a %p;

cout<<res<<endl;

---

二、快速幂（时间复杂度:O(logb)）

#include<iostream>
using namespace std;

typedef long long LL;

LL qmi(int a, int b, int p)
{
    LL ans = 1 % p;  //这里%p是为了防止在b==0，p==1的情况出错
    while (b)
    {
        if (b & 1) ans = ans * a % p;  //使用b的二进制的最后一位
        b >>= 1;  //使用完b的二进制的最后一位后将最后一位删掉
        a = a * (LL)a % p;  //计算下次要用的a
    }
    return ans;
}

int main()
{
    int n; cin>>n;
    while(n--)
    {
        int a,b,p; cin>>a>>b>>p;
        printf("%d\n",qmi(a,b,p));
    }

    return 0;
}

---