快速幂求逆元
费马小定理的定义
费马小定理:
如果p是一个质数,并且整数a不是p的倍数,则有 $ a^{p-1} = 1 (mod ~ p)$
逆元的定义
若整数b, m互质,并且对于任意的整数a,如果满足b|a, 则存在一个整数x,使得$a/b = a * (mod ~ m)$,
则称x为b的乘法逆元,记为$ b^{-1} (mod ~ m) $
b存在乘法逆元的条件是b与模数m互质。当模数m为质数时,$ b^{m-2} $即为b的乘法逆元
推导
a/b = a * x (mod m)
a/b = a * b^{-1} (mod m)
1 = b^{-1} * b (mod m)
由费马小定理 b^{m-1} = 1 (mod m)
所以b^{m-1} = b^{-1} * b (mod m)
即b^{-1} = b^{m-2}
结论
当b与m互质时,b的乘法逆元为$ b^{m-2} $;
当b为m的倍数时,b的乘法逆元不存在
#include <iostream>
using namespace std;
typedef long long LL;
// return a^k MOD p
LL quick_power(int a, int k, int p) {
int res = 1;
while (k != 0) {
if ((k & 1) != 0) res = (LL) res * a % p;
a = (LL) a * a % p;
k >>= 1;
}
return res;
}
/**
* acwing 876-快速幂求逆元
* @return
*/
int main() {
int n;
scanf("%d", &n);
while (n--) {
int b, m;
scanf("%d%d", &b, &m);
if (b % m == 0) {
puts("impossible");
} else {
printf("%lld", quick_power(b, m - 2, m));
}
}
return 0;
}