AcWing 89. a^b

题目链接:https://www.acwing.com/activity/content/problem/content/323/1/

 

89. a^b

 

求 aa 的 bb 次方对 pp 取模的值。

输入格式

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

输出格式

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

数据范围

0≤a,b,p≤1090≤a,b,p≤109

输入样例:

3 2 7

输出样例:

2

解题思路:
首先暴力的写法是乘一个a然后就对p取一次余,但是这样会超时。
基于二进制的思想,我们可以将b写成一个二进制数,这样我们每对b右移以为就让a乘以自己,并且当b是奇数的时候就将答案乘上一个a同时对p取余数。这样时间复杂度就是logn。这样就不会超时了。
AC代码:
#include <iostream>
#include <cstdio>

using namespace std;

typedef long long LL;

inline int qm(int a, int b, int p) {
	LL res = 1;
	LL tmp = a;
	while(b) {
		if(b & 1) res = (res * tmp) % p;
		tmp = (LL)tmp * tmp % p;
		b >>= 1;
	}
	
	return res;
}

int main(void) {
//	freopen("in.txt", "r", stdin);
	int a, b, p;
	scanf("%d%d%d", &a, &b, &p);
	if(b == 0) printf("%d\n", 1 % p);
	else printf("%d\n", qm(a, b, p));
	return 0;
}

  

 
上一篇:csp-s模拟测试89


下一篇:89. 格雷编码