对于 $a^b$可以将b按照二进制拆分例如$3=11_b$

这样对于$2^3$相当于$2^{{10_b}+1_b}=2^{10_b}*2^{1_b}$

那么此时就相当于$2^1*2^2$

对于5来说 $5=101_b$

$2^5 = 2^{100_b+1_b} = 2^{100_b}*2^{1_b} = 2^3*2^1$

那么我们可以定义$var \ x =\ 1\ :\ long\ int$

对于$2^5来说:

对于指数从低向高乘 x *= 2^0; 2 *= 2; 因为2最开始是最低次幂
此时指数为0 x不用乘, 2^2 *= 2^2
此时指数为1 x*= 2^4 2^4 *= 2^4

代码如下:

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    // ..................................lzx.....................
    ll a, b, p;
    a = read();
    b = read();
    p = read();
    printf("%d^%d mod %d=", a, b, p);
    ll k = 1;
    while(b > 0){
        if(b & 1) k = (k * a) % p;
        b >>= 1;
        a = (a * a) % p;
    }
    printf("%d", k % p);

    //...........................................................
    return 0;
}