原题链接

求乘法逆元

定义:即已知 $b$ 与 $m$ 互质 且 $b|a$ 则求一个$x$ 使得 $a/b\equiv a*x\mod m$
[注] 简单定义 即 $b*x \equiv 1 \mod m$ 且 $ b$ 与 $m$ 互质 则 $x$ 为 $b$ 的逆元

1. 当$m$为质数时

求解过程如下 ：

由费马小定理可知

$$ b^{m-1} \equiv 1 \mod m$$

而

$$a/b\equiv a*x \mod m$$

联立以上两式，得:
$$a/b*b^{m-1}\equiv a*x \mod m $$

即为
$$a*b^{m-2} \equiv a*x \mod m$$

而$b|a$,且$b$与m互质,因此对于$b$来说,一定存在一个$a$也与$m$互质,故而$a$可以在两边同时约去(感谢yxc大佬)

因此
$$x\equiv b^{m-2} \mod m$$

无解条件 即 $b$与$m$不互质时无解,而$m$为质数,所以$b$只能为$m$的倍数，此时无解,也就是$b\%m==0$

2.当m不是质数时,则需要用扩展欧几里得求逆元

3.逆元的作用

当 $a,b$ 很大时 求 $a/b \mod p$ 的值

而 $a/b \mod p \not= ((a \mod p)/(b \mod p) )\mod p$

因此可以借助逆元转化为乘法,再算,设b的逆元为$b^{-1}$

则 $a/b \mod p=a*b^{-1}\mod p = ((a \mod p)*(b^{-1} \mod p) )\mod p$

当m为质数时，求解逆元的C++代码如下

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int qmi(int a, int b, int p){//快速幂
    int res = 1%p;
    while(b){
        if(b&1) res = (LL)res*a%p;
        a = (LL)a*a%p;
        b>>=1;
    }
    return res;
}
int main(){
    int n,a,p;
    cin>>n;
    while(n--){
        cin>>a>>p;//p是质数 求 a的逆元(mod p意义下)
        if(a%p) cout<<qmi(a,p-2,p)<<endl;
        else cout<<"impossible"<<endl;
    }
    return 0;
}