同样地，对于每个b，我们可以表示为（整数b的二进制形式有k位）。
\(b = c_02^0+c_12^1+c_22^2+....c_{k-2}2^{k-2}+c_{k-1}2^{k-1}\)

即
\( b = \sum_{i=0}^{k-1}c_i2^i \)

那么对于

\(a^b =a^{\sum_{i=0}^{k-1}c_i2^i} =a^{c_02^0+c_12^1+c_22^2+....c_{k-2}2^{k-2}+c_{k-1}2^{k-1}}= a^{c_k-1*2{k-1}}*a^{c_k-2*2{k-2}}*a^{c_k-3*2{k-3}}......a^{c_0+2^0}\)

因为 \(k\) = \(\lceil log_2(b+1)\rceil\)（向上取整，即对于整数b的二进制位数）

所以上述乘积项的项数不多于\(\lceil log_2(b+1)\rceil\)个，复杂度为\(O(log_2 b)\)。

而我们本质上要求的就是若干个\(a^{2^i}\)相乘的结果。

又因为

\(a^{2^i} = (a^{2^{i-1}})^2\)

那么我们只需要k次递推求出每次的乘积项，当\(c_i\) = 1时，即二进制位为1的时候将乘积累积到答案中。我们可以用b & 1运算表示b的二进制下的最低位，并用b >> 1来舍去最低位。

int ans = 1;
    for (;b;b >>= 1){
        if (b & 1){
            ans = 1ll * ans * a;//通过乘上1ll进行类型转换
        }
        a = 1ll * a * a;
    }

而根据取模的性质

(a + b) % p = (a % p + b % p) % p （1）

(a - b) % p = (a % p - b % p) % p （2）

(a * b) % p = (a % p * b % p) % p （3）

a ^ b % p = ((a % p)^b) % p （4）

即(a * b)% p = (a % p * b % p ) % p

我们可以让 ans,a分别%p

#include <iostream>
using namespace std;

int main(){
    int a,b,p;
    cin >> a >> b >> p;
    int ans = 1 % p;
    for (;b;b >>= 1){
        if (b & 1){
            ans = 1ll * ans * a % p;
        }
        a = 1ll * a * a %p;
        cout << ans << " ";
    }
    cout << ans;
}