本文主要是介绍逆元相关知识点、求法(快速幂，拓展欧几里得，线性算法，阶乘的逆元)及拓展欧几里得算法的应用，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
概念：
若xy≡1 (mod p),且gcd(x,p)=1（gcd函数是求x,y的最大公约数），则称x关于模p的乘法逆元为y。
那么除以y相当于乘以x（模p情况下）。值得注意的是x(y+k*p)≡1(mod p),逆元不止一个，求最小的就可以；
几个定理or算法：
1.费马小定理：x^(p-1) ≡1 (mod p),p为素数,x不为p的倍数，若x为p的倍数则x^p ≡p (mod p)。那么当gcd(x,p)=1时，x * x^(p-2) ≡ 1(mod p),即x关于模p的逆元为x^(p-2)。则快速幂可求得逆元。
2.欧拉定理：a^φ(n)≡1(mod n) ，gcd(a,n)=1,函数φ(n)求数1到n与n互质的数的个数，当n为素数p的时候则为费马小定理。
3.欧几里得算法：即辗转相除法。
4.扩展欧几里得算法：已知整数a, b一定可以求解一组x，y（整数），使它们满足贝祖等式： ax+by = gcd(a, b) =d。
5 贝祖定理，方程ax+by=c有整数解的条件是gcd(a,b) | c。
用法：
1）这个算法可以用来求已知a，b的二元一次方程ax+by =z的整数解。但是前提是gcd(a,b) | z，否则没有整数解。(增加一个判断，例题POJ1061青蛙的约会）
2） 还可以用来求乘法的逆元a∗x≡1(mod p)—>a∗x+y∗p=1—>a∗x+b∗y=1(把p换成b),那么x是a关于b( p )的乘法逆元，y是b( p )的关于a的乘法逆元。(gcd(a*x,b)=1,b=p)
然而无论是用来求整数解还是求逆元都要对贝祖方程求解。
具体求法，代码及例题
拓展欧几里得算法：
1 求法
首先要对贝祖方程进行求解：
1）当b=0时，gcd(a,b)=a , ax+by=a–>x=1,y=0
2) 当b！=0时，
设方程1：ax+by=gcd(a,b),
方程2：bx1+(a%b)x1=gcd(b,a%b)
由欧几里得算法可得gcd(a,b)=gcd(b,a%b)=…=gcd(c,0) （///欧几里得算法的递推过程，c为a，b的最大公约数）
那么ax+by=bx1+(a-a/b*b)y1—>ax+by=ay1+b(x1-a/by1)—>x=y1 , y=x1-a/by1，由此我们可以知道x，y的解可由下一个x1，y1的解的得到，而递归到最后时，b=0，gcd(a,b)=a , ax+by=a–>x=1,y=0，这个时候x，y的值根据x=y1 , y=x1-a/by1一层一层的往回带，最后可以得到初始的x，y值。
2 代码：
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y)
{if(a==0&&b==0) return -1;///注意这种极端情况if(b==0){x=1,y=0;return a;}int r=exgcd(b这篇关于逆元相关知识点、求法(快速幂，拓展欧几里得，线性算法，阶乘的逆元)及拓展欧几里得算法的应用的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
