题目
给定 $n$ 组 $a_i,b_i,p_i$,对于每组数据,求出 ${a_i}^{b_i}mod{p_i}$ 的值。
输入格式 第一行包含整数 $n$。
接下来 $n$ 行,每行包含三个整数 $a_i,b_i,p_i$。
输出格式 对于每组数据,输出一个结果,表示 ${a_i}^{b_i}mod{p_i}$ 的值。
每个结果占一行。
数据范围 $1≤n≤100000,1≤a_i,b_i,p_i≤2×10^9$ 输入样例:
2
3 2 5
4 3 9
输出样例:
4
1
思路
主要思路是将 $b$ 转换成二进制,将二进制中位为 $1$ 的初始化,最终结果由预处理的数值拼凑而成。
代码
#include <iostream>
using namespace std;
typedef long long LL;
// 快速幂代码
int fast_power(int a, int b, int p)
{
LL res = 1;
while (b)
{
if (b & 1) res = res * a % p;
b >>= 1;
a = (LL)a * a % p;
}
return res;
}
int main()
{
int n;
scanf("%d", &n);
while (n -- )
{
int a, b, p;
scanf("%d%d%d", &a, &b, &p);
printf("%lld\n", fast_power(a, b, p));
}
return 0;
}
标签:d%,int,res,LL,875,long,fast,快速,AcWing
From: https://blog.51cto.com/u_16170343/7254007