一.逆元是什么？为什么引入逆元 （1）逆元，又称为数论倒数。这里和普通的倒数是不一样的，普通倒数可能为小数，而数论倒数一定是个整数。 数论概念：对于正整数 aa 和 pp，如果有 ax≡1(modp)，那么把这个同余方程中 x 的最小正整数解叫做 a模 p的逆元。 即 ax % p = 1中 x 的最小正整数解就是a关于模数p的逆元。 （2）为什么引入逆元？（只适用于除法取模运算） 这里引入取模的概念： a +  b) % p = (a%p +  b%p) %p  （对） (a  -  b) % p = (a%p  -  b%p) %p  （对） (a  *  b) % p = (a%p *  b%p) %p  （对） (a  /  b) % p = (a%p  /  b%p) %p  （错） 我们都知道取模运算对于除法是不成立的，那么如果模运算中出现了除法是不是就无法计算了呢？伟大的数学家于是给出了逆元这个东西。 ax % p = 1，这里x不一定等于 1 / a ， 因为加入了取模。比如 3 * 2%5 = 1 ， 这里的2不就相当于 1 / 3的作用吗？于是我们就说 2 是3关于模数5的逆元。这就是逆元产生的意义。于是，我们在计算除法取模时，可以把除数变为他的逆元，把除法取模运算变为乘法取模运算，在二式等价背景下，变除为乘，间接实现取模运算，这就是逆元的魅力！（我们下面用inv（a）代表a的逆元）   由上可知： （a/b）%p  = （a * inv（b））%p = （a%p * inv（b）%p）%p    （即除以一个数取模等于乘以这个数的逆元取模）   二、如何求逆元 （1）费马小定理（要求：模数p为素数，且a 与 p互质即gcd（a,p） == 1） 由费马小定理知： a^(p-1) ≡ 1（mod p）即 a^（p-1）%p = 1 已知：a*inv（a）%p = 1 所以：a*inv（a）%p = a^（p-1）%p 则：inv（a）%p = a^（p-2）%p 于是这里用到快速幂 + 费马小定理来求逆元。 代码：  LL power(LL a,LL b)//快速幂 { a%=p; LL ans = 1; while(b){ if(b&1)ans = (ans*a)%p; b>>=1; a = (a*a)%p; } return ans; } int main() { while(scanf("%lld%lld",&n,&p)!=EOF&&n){ printf("%lld ",power(n,p-2));//求n关于p的逆元 } return 0; } 时间复杂度 O（log（p）) （2）拓展欧几里得算法求逆元（不要求模数p为素数，要求a， p互质即gcd（a,p）==1 ）   我们知道 拓展欧几里得 求解 ： ax + py = 1（a与p互质即gcd（a,p） = 1） 则： ax%p + py%p = 1%p 即：ax % p = 1%p 即： ax ≡ 1（mod p） 所以x的最小整数解就是a关于p的逆元，所以我们只要求解 ax + py = 1的最小正整数解 x 即可 代码： LL ex_gcd(LL a,LL b,LL &x,LL &y){ if(b==0){x = 1;y = 0;return a;} int ans = ex_gcd(b,a%b,x,y); int temp = x; x = y; y = temp - (a/b)*y; return ans; } LL inv(LL a,LL b){ LL x,y; int ans = ex_gcd(a,b,x,y); if(x<0)x = (x%b + b)%b;//有可能<0，我们让他>0 if(ans==1)return x;//ab互斥有解 else return -1;//否则返回-1 } int main() { while(scanf("%lld%lld",&n,&p)!=EOF&&n){ printf("%lld ",inv(n,p)); } return 0; } 时间复杂度 O（log（p）)