快速幂

思想：把$ a ^ b $看成 b 个 a 相乘，利用二进制拼成b ，时间复杂度O(logb)

#include <iostream>

using namespace std;

typedef long long LL;

LL qmi(LL a,LL b,LL p)
{
    LL res=1 % p;  // 边界数据：a,0,1,因为b=0,所以不会进入while循环，
                    // 若直接定义res=1,然而任何数%1=0,所以要先模
    while(b)
    {
        if(b & 1) res = res *a % p;  // 直接定义为LL，防止溢出
        a = a * a % p; // a倍增
        b >>= 1;
    }
    return res;
}

int main()
{
    LL a,b,p;
    cin >> a>> b >> p;

    cout << qmi(a,b,p);

    return 0;
}