题目

给定n组ai , bi, pi，对于每组数据，求出a^kimod pi的值。

输入格式

第一行包含整数n。
接下来n行，每行包含三个整数ai , bi,pi。输出格式
对于每组数据，输出一个结果，表示ai^bimod pi的值。
每个结果占一行。

数据范围

1≤n ≤100000,
1 ≤as, bi, pi≤ 2* 10⁹

##C++代码

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
// a^k % p
int qmi(int a, int k， int p)
{
	int res = 1;
	while (k)
	{
		if (k & 1) res - (LL)res * a % p;
		k >>= 1;
		a = (LL)a * a % p;
	}	
	return res;
}
int main()
{
	int n;
	scanf("%d"，&n);
	while (n -- )
	{
		int a, k, p;
		scanf("%d%d%d",&a,&k,&p);
		printf("%d\n", qmi(a,k, p));
	}
	return 0;
}

java代码（非本题代码，但同样为快速幂代码，为博主系统学习之前自己查阅资料自学时用的代码）

public static long fastPower(long a,int n){
        int ans=1;
        while (n != 0) {
            if((n&1)!=0){
                ans*=a;
            }
            a*=a;
            n>>=1;

        }
        return ans;
    }

思路

快速幂的代码很短很简单，大家可以选择背诵，当然也可以理解，理解记得更久嘛。以下图片为快速幂的推导