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.
47 lines
1.0 KiB
47 lines
1.0 KiB
[题目传送门](https://www.acwing.com/problem/content/description/91/)
|
|
|
|
### 一、题目描述
|
|
求 $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$次！所得的结果相乘或不断取模就行了。
|
|
|
|
|
|
### 三、实现代码
|
|
```c++
|
|
#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;
|
|
}
|
|
```
|
|
|
|
|