acwing 875. 快速幂

题目描述

给定 nn 组 ai,bi,pi，对于每组数据，求出 a^b % p 的值。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含三个整数 ai,bi,pi

输出格式

对于每组数据，输出一个结果，表示 a^b % p 的值。

每个结果占一行。

数据范围

1≤n≤100000
1≤ai,bi,pi≤2×109

输入样例：

2
3 2 5
4 3 9

输出样例：

4
1

快速幂算法求解

分析

a^b %p

判断b二进制的每一位，看是否乘以当前的权重

权重从最低位开始往高位：a, a^2, a^4, a^8, ...

代码

#include
#include
#include
using namespace std;

//const int N = 2000000010;

typedef long long ll;

ll ksm(int a, int b, int p)
{
	ll res = 1;
	ll t = a;
	while(b)
	{
		if(b & 1) res = (res * t) % p; // 判断每一位 
		
		t = (t * t) % p; // 累乘 
		b >>= 1;
	}
	return res;
}

int main()
{
	int n;
	int a, b, p;
	scanf("%d", &n);
	while(n --)
	{
		scanf("%d%d%d", &a, &b, &p);
		printf("%lld\n", ksm(a, b, p));
	}
	return 0;
 } 

时间复杂度

\(O(alog(b))\)

参考文章