H1N1's Problem(快速幂）

描述

H1N1 like to solve acm problems.But they are very busy, one day they meet a problem. Given three intergers a,b,c, the task is to compute a^(b^c))17000011. 1412, ziyuan and qu317058542 don't have time to solve it, so the turn to you for help.

输入

The first line contains an integer T which stands for the number of test cases. Each case consists of three integer a, b, c seperated by a space in a single line. 1 <= a,b,c <= 100000

输出

For each case, print a^(b^c)17000011 in a single line.

样例输入

2
1 1 1
2 2 2

样例输出

1
16

 快速幂的递归，好久没学数学，完全要没感觉了

#include<stdio.h>
long long f(long long a,long long b,long long m)
{
    long long z=1;
    while(b)
    {
        if(b%2) z=(z*a)%m;
        b/=2;
        a=(a*a)%m;
    }
    return z;
}
int main()
{
    long long n,a,b,c;
    scanf("%I64d",&n);
    while(n--)
    {
        scanf("%I64d%I64d%I64d",&a,&b,&c);
        printf("%I64d
",f(a,f(b,c,317000010),317000011));
    }
}

a^(b^c) % p = a^( (b^c)%(p-1) )%p