扩展欧几里得算法求逆元

扩展欧几里得算法应该是最优的求逆元算法之一 ，他和费马小定理具有同样的时间复杂度$O(log(n))$，但是费马小定理需要模数为质数，扩展欧几里得算法则不需要。

逆元定义

若$a$与$p$互素，则满足$(a\times x)modp=1$的$x$为$a$的逆元。

显然，有$(k\times p+1)modp=1$（$k$为任意常数），又因为$(a\times x)modp=1$，所以有$k\times p+1=a\times x$，也就是$$a\times x+k\times p=1$$

只要求得任意一组满足等式的$x、k$，其中的$x$就是$a$的逆元！

这不就是扩展欧几里得算法解决的问题吗？

扩展欧几里得算法求逆元代码：

void exgcd(ll a, ll b, ll &x, ll &y, ll &d) { if (!b) { d = a; x = 1; y = 0; return; } exgcd(b, a % b, x, y, d); ll temp = x; x = y; y = temp - (a / b) * y; } int main() { ll a, b, x, y, d; cin >> a >> b; exgcd(a, b, x, y, d); x = (x % b + b) % b; //防止出现负数 cout << "a关于模b的逆元为: " << x << endl; return 0; }