快速幂模板题。

令 $k$ 为 $b$ 在二进制下的位数，$t_i$ 为 $b$ 在二进制下的第 $i$ 位。

则 $b = t_{k - 1} {2^{k - 1}} + t_{k - 2} 2 ^ {k - 2} + … + t_02_0$

于是 $a ^ b = a^{t_{k - 1}{2^{k - 1}}} * a^{t_{k - 2}{2^{k - 2}}} * … * a^{t_02_0}$

所以我们只要将 $b$ 二进制中所有为 $1$ 的位 $i$，取出，答案即为所有 $a^{t_{i}2_i}$ 的乘积。

#include <iostream>
using namespace std;
typedef long long LL;
LL a, b, p;
int main() {
    scanf("%lld%lld%lld", &a, &b, &p);
    LL res = 1 % p;
    while (b) {
        if (b & 1) res = res * a % p;
        b >>= 1;
        a = a * a % p;
    }
    printf("%lld\n", res);
    return 0;
}