a^b

求 a 的 b 次方对 p 取模的值。

输入格式
三个整数 a,b,p ,在同一行用空格隔开。

输出格式
输出一个整数,表示a^b mod p的值。

数据范围
1≤a,b,p≤1e9
输入样例:
3 2 7
输出样例:
2

时/空限制: 1s / 32MB

这道题刚看会发现诶,直接循环就完了嘛,但是一看下面的数据范围就会发现,如果直接循环,一定会超时。

那怎么做呢?

这里就是一个典型快速幂的题目,我们可以吧a^b分解,利用二进制的特性,从低位乘到高位,如果那一位是0就代表不需要乘,1则反之。

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,p;
	cin>>a>>b>>p;
	int res=1%p;//防止p是0的情况出现 
	while(b)
	{
		if(b&1)	res*=1ll*a%p;//1ll是把res和a强转为long long 
		a*=1ll*a%p;
		b>>=1;//b右移 
	}
	cout<<res<<endl;
	return 0;
}