题目描述
给定n组ai,bi,pi,对于每组数据,求出aibi mod pi的值。
样例
输入样例:
2
3 2 5
4 3 9
输出样例:
4
1
算法
(快速幂)
- 如果b是0,指数是0,直接返回1。ans直接递归到f(a, b / 2, p)那里。最后ans的平方,再对p取余。
- 如果b是1,再用ans和a的乘积对p取余。最后return ans
时间复杂度
$O(n)$
C++ 代码
#include<iostream>
using namespace std;
typedef long long LL;
int f(int a, int b, int p)
{
if(!b) return 1;
int ans = f(a, b >> 1, p);
ans = (LL) ans * ans % p;
if(b & 1) ans = (LL) ans * a % p;
return ans;
}
int main()
{
int n;
cin >> n;
while(n--)
{
int a, b, p;
cin >> a>> b >> p;
cout << f(a, b, p) << endl;
}
}