求 a 的 b 次方对 p 取模的值。
输入格式
三个整数 a,b,p ,在同一行用空格隔开。
输出格式
输出一个整数，表示a^b mod p的值。
数据范围
0≤a,b≤1e9
1≤p≤1e9
输入样例：
3 2 7
输出样例：
2
- 代码中用位运算判断 b 当前位是否为0，不是 0 的话就乘进答案中
- 有的代码中把res初始化为 res = 1 % p， 这是为了避免特殊情况，比如 a = 3, b = 0, p = 1, 这里如果把res初始化为 1， 那么最后输出的就是 1 (正确答案是 0 ), 因为 b 等于 0， 在 qmi函数中，根本进不去while循环
- 这里我们初始化为 1 ，最后在输出的时候 %p 就可以等同于把 res 初始化为 1 % p, 同样可以避免上述情况
快速幂的证明省略的，博主数论不好orz
#include <bits/stdc++.h>
using namespace std;
#define int long long
int qmi(int a, int b, int p)
{
int res = 1;
while (b)
{
if (b & 1) res = res * a % p;
b >>= 1;
a = a * a % p;
}
return res;
}
signed main()
{
int a, b, p; cin >> a >> b >> p;
int res = qmi(a, b, p);
cout << res % p << endl;
return 0;
}
觉得写的不错的话，点个赞吧~