a ^ b
求 a 的 b 次方对 p 取模的值。
输入格式
三个整数 a,b,p ,在同一行用空格隔开。
输出格式
输出一个整数,表示a^b mod p的值。
数据范围
0≤a,b,p≤109
数据保证 p≠0
输入样例:
3 2 7
输出样例:
2
思路说明:
若采用a个b一个个相乘取模的方式来做,它的算法复杂度为O(n)
而因为
- 一位一位的二进制组合可以表示所有的数,即所有数都可以表示为\(2^0\)+\(2^1\)+...+\(2^n\)
- a * b mod p == (a mod p) * (b mod p) mod p (咕咕咕,可能之后会在后面补上这数学证明)
所以我们可以把b用一位一位二进制来表示即可把时间复杂度降为O(\(log_2b\))
代码展示:
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll; typedef unsigned long long ull;
ll a, b, p;
inline int qpm(ll a, ll b, ll p) {
ll ans = 1 % p, t = a % p; // 若没有一开始ans % p 若遇到 0 0 1
while(b) {
if(b & 1) ans = ans * t % p;
t = t * t % p;
b >>= 1;
}
return ans;
}
int main(){
scanf("%lld%lld%lld", &a, &b, &p);
printf("%lld\n", qpm(a, b, p));
return 0;
}