欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

a^b%p

程序员文章站 2022-04-01 17:21:06
...

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;
}
相关标签: oj