C 代码

//此题可看作Acwing27的升级版，比那道题多考虑了一个取模
//如何处理取模操作:
//显然直接算出结果再取模复杂度过高，数据也太大，选择拆分后每个部分都先取模
//将指数按照二进制拆分成很多位，预处理出每一位对应的乘积取模后的值
//将预处理的值分步（每次两个相乘）乘在一起并取模，最终就得到结果

#include <stdio.h>
#include <math.h>

typedef long long LL;

int main()
{
    int n;
    scanf("%d",&n);
    while (n--){
        LL base,k,p;
        scanf("%lld%lld%lld",&base,&k,&p);
        LL res = 1;
        base = base % p;
        int k1 = abs(k);
        for (;k1;k1 /= 2){
            if (k1 % 2) res = res * base % p;
            base = (base * base) % p; 
        }
        printf("%lld\n",(res % p + p) % p);
    }
}