题解 | #快速幂#

#include <stdio.h>
//两个关键点， (a*b)mod q = (a mod q)*(b mod q) mod q;
//              a^n (n>=2) = a^n/2 * a^n/2 (单数情况见代码）
unsigned long long quick(unsigned long long a, unsigned long long b, unsigned long long q)
{
    if (b == 0)
    {
        return 1;
    }
    if (b == 1)
    {
        return a % q;
    }
    unsigned long long k = quick(a, b / 2, q) % q;
    if (b % 2)
    {
        // 单数

        return ((k * k) % q * (a % q)) % q;
    }
    else
    {
        // 双数
        return k * k % q;
    }
}
int main()
{
    int times;
    scanf("%d",×);
    while(times--){
unsigned long long a, b, q;
    scanf("%lld%lld%lld", &a, &b, &q);

    printf("%lld\n", quick(a, b, q));
    }
    
    return 0;
}