快速幂

二进制中的位运算，左移一位可以看作是将整体乘上2，右移一位可以看作是将整体除以2

对于a ^ b，可以将b的二进制数拆分成多个二进制数和的形式（每一个二进制数只有一个二进制位为1）
例如:
a ^ 10110 可以拆分为 a ^ (10000 + 100 + 10) = a ^ 10000 * a ^ 00100 * a ^ 00010
这样就只需要将b的二进制位为1的各个a的幂相乘就可以了

所以可以将b进行位运算，这一位如果是1就计入答案，当b经过若干次位运算后变为0后，就可以得到最终答案了，至于a的各个幂，可以在每一次位运算后取一次平方得到

时间复杂度

朴素做法是O(b)
快速幂由于是遍历的b的二进制数，所以时间复杂度降为O(log b)

#include <iostream>

using namespace std;

int main()
{
    int a, b, p;
    cin >> a >> b >> p;
    long long res = 1 % p;

    while(b)
    {
        if(b & 1) res = 1ll * (res % p) * (a % p) % p;
        a = 1ll * (a % p) * (a % p) % p;
        b >>= 1;
    }

    cout << res <<endl;
    return 0;
}