【概念】

其实逆元的概念和倒数差不多，即： 方程  的解称为  关于模  的逆，当 （即 ， 互质）时，方程有唯一解，否则无解。 那么逆元可以用来干什么呢，比如说对于 ，并没有 ，但是直接除又会爆精度，这时我们就可以用到逆元，假设用  代表  的逆元，那么   

【三种求法】

方法一：用费马小定律 内容：当  为质数时，有 ，那么易得出  也就是说，此时  就是  关于模  的逆元，用快速幂就可以在 O（）的时间内求出逆元 代码（求 ）： #include #include using namespace std; int Quick_Power(int a,int b,int c) { int ans=1; while(b) { if(b&1) ans=(1ll*ans*a)%c; a=(1ll*a*a)%c; b>>=1; } return ans; } int main() { int a,b,p; scanf("%d%d%d",&a,&b,&p); b=Quick_Power(b,p-2,p); printf("%d",((a%p)*(b%p))%p); return 0; }   方法二：用扩展欧几里得算法 按照逆元的概念，实际上就是求  的一个解，用扩欧就可以轻松解决 时间复杂度O（） 代码： #include #include void exgcd(int a,int b,int &x,int &y) { if(b==0) { x=1; y=0; return; } exgcd(b,a%b,y,x); y-=a/b*x; } int main() { int a,b,p,x,y; scanf("%d%d%d",&a,&b,&p); exgcd(b,p,x,y); x=(x+p)%p; printf("%d",((a%p)*(x%p))%p); return 0; }   方法三：用线性筛 就是通过递推求 1 到 n 之间所有数的逆元 时间复杂度O（） 由于我也不是很懂这个方法我就不多说了，就先给出板子吧 代码： #include #include #define N 1000005 using namespace std; int inv[N]; void get_inverse(int n,int p) { int i; inv[1]=1; for(i=2;i<=n;++i) inv[i]=(p-p/i)*inv[p%i]%p; } int main() { int n,i,p; scanf("%d%d",&n,&p); get_inverse(n,p); return 0; }