背景

Description

Implement pow(A, B) % C.In other words, given A, B and C, find (A^B)%C

Input

The first line of input consists number of the test cases. The following T lines consist of 3 numbers each separated by a space and in the following order:A B C’A’ being the base number, ‘B’ the exponent (power to the base number) and ‘C’ the modular.Constraints:1 ≤ T ≤ 70,1 ≤ A ≤ 10^5,1 ≤ B ≤ 10^5,1 ≤ C ≤ 10^5

Output

In each separate line print the modular exponent of the given numbers in the test case.

Sample Input 1

3
3 2 4
10 9 6
450 768 517

Sample Output 1

1
4
34

大数取余方法

整数求余满足的性质：

(x∗y) mod p = [x(y mod p)]mod p=[(x mod p)(y mod p)]mod p

循环求余

int main(){
    int t; //测试用例数t
    int a,b,c; //基数a，幂b，模数c
    cin>>t;
    while(t--){
        cin>>a>>b>>c;
        int res=1; // 循环求余
        while(b--){
            res = (res*a)%c;
        }
        cout<<res<<endl;
    }
}

快速幂

求大数 a^b 的思路为：

当 b 是偶数时，有 a^b = a^(b/2) * a^(b/2)
当 b 是奇数时，有 a^b = a * a^(b-1)

再利用整数求余性质：

当 b 是偶数时，(a^b)%c = ( a^(b/2) * a^(b/2))%c = [( a^(b/2)%c)*( a^(b/2)%c)]%c
当 b 是奇数时，(a^b)%c = (a * a^(b-1))%c = [a*(a^(b-1)%c)]%c

//快速幂-递归
int qiuyu(int a, int b, int c){ 
    if(b==0) return 1;
    if(b==1) return a%c;
    else if(b%2==0) return (qiuyu(a,b/2,c)*qiuyu(a,b/2,c))%c;
    else return (a*qiuyu(a,b-1,c))%c;
}

//非递归
//快速幂-非递归位运算思想
int qiuyu(int a, int b, int c){
    int ans=1;
    while(b){
        if(b&1) ans=(ans*a)%c;
        a=(a*a)%c;
        b>>=1;
    }
    return ans;
}

参考：大数求余算法