快速幂原理介绍
快速幂模板
int qmi(int a, int k, int p) {
int res = 1;
while (k) {
//后面的a其实是底数与其指数的运算结果了,是不断迭代的
//第一个a其实就是a的2的0次方
if (k & 1) res = (res * a) % p;
a = (a * a) % p;
//注意,a是一个不断变化的过程
//下一个a就等于上一个a的平方,
k >>= 1;
}
return res;
}
快速幂求逆元
首先要知道什么是逆元。
在模运算下,如果存在一个数 b,使得 (a * b) mod p = 1,a不是p的倍数,那么我们称 b 是 a 在模 p 下的逆元。
费马小定理:假设我们需要计算 a 在模 p 下的逆元,即要找到一个数 b,使得 (a * b) mod p = 1。根据费马小定理,当 a 不是 p 的倍数时,有 a^(p-1) mod p = 1。将其变形为 a^(p-2) mod p = a^(-1) (mod p),即 a 的逆元(a^(-1))等于 a^(p-2) 在模 p 下的余数。因此,我们只需使用快速幂算法计算 a^(p-2) mod p 即可得到 a 在模 p 下的逆元。
例题:
分析:
1.先看逆元存不存在,不存在就输出impossible。如果a不是p的倍数(a%p!=0),逆元才存在。
2.如果逆元存在,用快速幂算 a^(p-2) mod p 即可
int qmi(int a, int k, int p) {
int res = 1;
while (k) {
//后面的a其实是底数与其指数的运算结果了,是不断迭代的
//第一个a其实就是a的2的0次方
if (k & 1) res = (res * a) % p;
a = (a * a) % p;
//注意,a是一个不断变化的过程
//下一个a就等于上一个a的平方,
k >>= 1;
}
return res;
}
bool check(int a, int p) {
if (a % p == 0) return true;
return false;
}
signed main() {
int t; cin >> t;
while (t--) {
int a, p; cin >> a >> p;
if (check(a, p)) {
cout << "impossible" << endl;
continue;
}
cout << qmi(a, p - 2, p) << endl;
}
retu