【数论】exgcd 扩展欧几里得算法

本文主要是介绍【数论】exgcd 扩展欧几里得算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

参考：exgcd详解 - zzt1208 - 博客园 (cnblogs.com)

exgcd（扩展欧几里得算法），用来求形如 $ax+by=gcd(a,b)$（$a,b$ 为常数）的方程的一组整数解。（如果不确定等号右边是不是gcd，可以先当做gcd，求出来之后验证，是的话就是解，不是的话就不是解）

推导见上面的链接，这篇只放个板子

code

int exgcd(int a, int b, int &x, int &y) // 扩展欧几里得
{if (b == 0){x = 1;y = 0;return a;}int r = exgcd(b, a % b, x, y);int temp = y;y = x - (a / b) * y;x = temp;return r; // 得到a b的最大公因数
}

这篇关于【数论】exgcd 扩展欧几里得算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---