题解 | #快速幂#

• 若采用循环直接实现幂指数计算时间复杂度为O(n)
• 使用快速幂的方式，即计算的幂指数的指数部分每次减半，底数变为平方。通过对折的方式，减少指数部分，从而减少循环的次数。

1. （对指数奇偶性进行判断）当指数大于零的时候，对2取余数，余数为1的时候，此时计算的结果res乘一次底数，并将结果对p取余。
2. 指数对2取整（变为原来的一半），底数取平方并对p取余数。
3. 当指数<=0，跳出循环。

tips:计算中对p取余数，防止数值过大，造成内存溢出。

# @param q 询问次数
# @param a 底数
# @param b 指数
# @param p 除数
# @return res 幂指数对p取余数 

def fast_power(base, power, p):
    res = 1
    while power > 0:
        if power % 2 == 1:
            res = res * base % p
        power = power // 2
        base = base * base % p
    return res % p
q = int(input())

for i in range(q):
    s = input()
    splt = s.split()
    a = int(splt[0])
    b = int(splt[1])
    p = int(splt[2])
    ans = fast_power(a, b, p)
    print(ans)