a的b次方

a^b%p

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

输入格式

三个整数 $a,b,p$

输出格式

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

数据范围

$0\leqslant a,b\leqslant 10^9 $

$1\leqslant p\leqslant 10^9$

输入样例:

1
3 2 7

输出样例:

1
2

解析

(默认懂位运算,不懂的查)

要求 $a^b \mod p$ 就要先解决 $a^b$ ,因为根据模的运算定理 $(a*b)\mod p = (a\mod p \times b\mod p)\mod p$ 而 $a^b = a\times a\times a …\times a$

若 $a = b = 10^9$ 那么 $a^b$ 就会超时

考虑简化 $b$,由数学常识可得一个正整数可以唯一表示为若干指数不重复的2的次幂的和,即$b = c_{k - 1}\times{2^{k - 1}} + c_{k - 2}\times{2^{k - 2}} + …+c_{0}\times{2^0}$ ,$c$ 的值为 $b$ 的二进制在 $k$ 位置上的值

那么这样就易得 $a^b = a^{c_{k - 1}\times{2^{k - 1}}} \times a^{c_{k - 2}\times{2^{k - 2}}} \times … \times a^{c_{0}\times {2^{0}}}$ 而 $c_k\times{2^k}$ 的最大值不会超过 $log_2^{1e9 + 1}$ 即不会超过 $30$ ,这样就将时间复杂度从 $O(b)$ 变为了 $O(log_2^b)$

计算的时候还需要观察一下规律,假设我们最后得到的是这样一个式子 $a^{1\times1} \times a^{0\times2} \times a^{1\times4} \times a^{1 \times 8}$ 我们发现, 无论 $c$ 的值为何值,从第二项开始后面的值 $2^k$ 都是上一次的值 $(2^{k-1})^2$,而且之前的值我们是不会再次调用的,于是就可以用 $a$ 的值继承就好。

综上,可得计算代码

1
2
3
4
5
int ans = 1 % p //一定要 %p 因为可能 b = 0, p = 1
for (; b; b >>= 1) {
if(b & 1) ans = (long long)ans * a % p;
a = (long long)a * a % p;
}

最后放过题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <cstdio>
#include <iostream>

int main() {
int a, b, p;
scanf("%d %d %d", &a, &b, &p);
int ans = 1 % p;
for (; b; b >>= 1) {
if(b & 1) ans = (long long)ans * a % p;
a = (long long)a * a % p;
} printf("%d", ans);
return 0;
}