0830-扩展欧几里得算法+例题 0830-扩展欧几里得算法+例题

phew~终于看懂了，以前一直以为很高深很高深的算法，结果还是很简单嘛
-->参考资料<--
证明什么的大家都写的很好啊，蒟蒻就不再bibi了，在这里解释一下代码吧，我看了好多博客都只讲了思路和证明，像宝宝这种代码能力不强的就只好自己想想想想想

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; }

由于推导出来：

若
文章图片
，
文章图片
那么
文章图片

我们可以找出一组
文章图片
满足
文章图片

文章图片

文章图片

文章图片

文章图片

文章图片

一直这样下去（这是一个递归的过程），直到
文章图片
时，此时
文章图片
就是一组合法的解，再代回去就行了

文章图片
<--重点是这个式子
我们再往下传递的时候就直接把 x，y 交换位置，那么执行完第9行的时候返回回来，x就直接是y‘的值了， y 就是 x’ 的值，然后根据刚刚的式子，y = x' - a/b * y'，相应代换一下就可以得到第10行了

例题
传送门
分析
板子题，唯一需要做的就是转化一下将 ax ≡1( mod b ) 变为 ax - by = 1 的形式，最后由于输出最小的正整数，我们调整一下即可
代码

#include #include #include #define ll long long using namespace std; void exgcd(ll a,ll b,ll &x,ll &y){ if(b==0){x=1; y=0; return; } exgcd(b,a%b,y,x); y-=a/b*x; } int main(){ ll a,b,x,y; cin>>a>>b; exgcd(a,b,x,y); cout<<(x%b+b)%b; return 0; }

最后bibi一句：&是引用的符号，一变全变
【0830-扩展欧几里得算法+例题】2019/08/13更新