You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
1.0 KiB
1.0 KiB
一、题目描述
求 a
的 b
次方对 p
取模的值。
二、解题方法
一看到这道题,就可以知道是快速幂。 这道题的重点是快速幂,那我就来认真讲讲。
快速幂是使用二进制的思想来在 O(logn)
的时间内解决幂的问题的方法。
举个栗子
7
的10
次方
计算思路:
10 = (1010)_2
从右向左
7^1=7
7^2 = 7^1 * 7^1
7^4 = 7^2 * 7^2
7^8 = 7^4 * 7^4
如上面的办法,我们只需要计算4
次,成倍的翻番,而不用最笨的乘10
次!所得的结果相乘或不断取模就行了。
三、实现代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main() {
LL a, b, p, res = 1;
cin >> a >> b >> p;
while (b) {
if (b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
printf("%lld\n", res % p);
return 0;
}