Acwing.875 快速幂

题目

给定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;}

思路

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