定义

又名扩展欧几里得算法（辗转相除法）

是用来求 \(ax+by=gcd(a,b)\) 中未知数的算法

算法证明

拿到一组 \(a,b\) ，设 \(G=gcd(a,b)\)

目标：求出满足 \(ax+by=G（1）\) 的 \(x\) 与 \(y\)

如果 已知一组 \(x2,y2\) ，满足 \(bx2+\) \((a\) \(mod\) \(b)y2=G（2）\)

此时结合 \((1)(2)\) 得
\(ax+by=\) \(bx2+\) \((a\) \(mod\) \(b)y2（3）\)

那么当 如果 满足时，目标就成了求满足 \((3)\) 的 \(x,y\)，其中 \(a,b,x2,y2\) 均已知

根据取模运算是 \(a\) \(mod\) \(b=a-b*(a/b)\)
所以方程 \((3)\) 实则是

\(ax+by=\) \(bx2+\) \((a-b*(a/b))y2\)

\(->\) \(ax+by=bx2+ay2-b*(a/b)y2\)

\(->\) \(ax+by=ay2+b(x2-(a/b)y2)\)

那么在根据方程 \(ax+by=G（1）\) 得出一组必然的解：

\(x=y2,y=x2-(a/b)y2（4）\)

可见只需求出 \(x2,y2\) ，就能求出正确的 \(x,y\)，问题就转化成了求 \(x2,y2\)

将方程 \((1)\) 与 \((2)\) 对比一下：

\(ax+by=G（1）\)

\(bx2+\) \((a\) \(mod\) \(b)y2=G（2）\)

发现原方程的 \(a\) 变成了 \(b\)，原方程的 \(b\) 变成了 \(a\) 而已

所以新的方程也可以看做 \(ax+by=G\) 的形式，然后按照上面的程序进行下来，发现问题又变为求 \(x3,y3\) 再求 \(x4,y4\) \(......\) 即一个递归的过程

递归过程中 \(a,b\) 不断被替换为 \(b,a\) \(mod\) \(b\)，这个过程和普通的欧几里得是一样的，所以最后会出现 \(a(n)=G,b(n)=0\)

那么这特就是最后一层，此时就要直接返回了，需要一组 \(x(n),y(n)\) 满足 \(a(n)x(n)+b(n)y(n)=G（5）\)，然而 \(a(n)=G,b(n)=0\)，所以只要 \((5)\) 的 \(x(n)\) 取 \(1\) 就必定满足了，\(y(n)\) 就随便取个 \(0\) 就行了

最后一层结束后，就开始返回，知道最上一层，每一层都可以通过下一层的 \(x(k+1),y(k+1)\) 求出当前层的 \(x(k),y(k)\)

整个过程就是：以辗转相除的方式向下递进，不断缩小系数，保证会出现有确定解的最后一层

例题

题目链接 同余方程

问题处理

题目问的是满足 \(ax\) \(mod\) \(b=1\) 的最小正整数（a,b均为正整数）

问题可以转化成求 \(ax+by=1\) 中 \(x\) 的值，其中 \(y\) 是个引入的辅助数（y一定是一个负数，但是写成 \(+\) 的形式以便 \(exgcd\) 算法）

问题仍需转化，\(exgcd\) 求得是 \(ax+by=gcd(a,b)\)，所以求方程 \(ax+by=m\) 必须满足的条件就是 \(m\) \(mod\) \(gcd(a,b)=0\)

简单证明一下：

由最大公因数的定义，\(a,b\) 均是 \(gcd(a,b)\) 的倍数，因为 \(m=ax+by\)，所以 \(m\) 一定是 \(gcd(a,b)\) 的倍数，即 \(m\) \(mod\) \(gcd(a,b)=0\)

可得这道题中，必须满足 \(1\) \(mod\) \(gcd(a,b)=0\)，那么 \(gcd(a,b)\) 就必须等于 \(1\) 了，即 \(a,b\) 互质（数据一定是满足的）

之后通过上述的 \(exgcd\) 算法即可，但是题目要求 \(x\) 的最小值，仅仅 \(exgcd\) 无法满足，所以需要答案处理

答案处理

求出来的 \(x,y\) 仅仅满足 \(ax+by=1\)，而 \(x\) 不一定是最小正整数解。有可能太大，也可能是负数

解决方案是：\(x\) 批量地减去或加上 \(b\)，能保证 \(ax+by=1\)，因为：

\(ax+by=1\)

\(->\) \(ax+by+k*ba-k*ba=1\)

\(->\) \(a(x+kb)+(y-ka)b=1\)

1.显然这并不会把方程中的任何整数变为非整数

2.加上或减去 \(b\) 不会使 \(x\) 错过任何解，可以这么理解：

已经求出一组 \(x,y\) 使得 \(ax+by=1\)，也就是 \((1-ax)/b=y\)，\(y\) 是整数，可见目前 \(1-ax\) 是 \(b\) 的倍数

现在给 \(x\) 加上 \(kb\)（k为整数），则变为：

\((1-a(x+kb))/b\)

\(=(1-ax)/b+ak\)

仍满足其为 \(b\) 的倍数，由此当 \(x\) 的变化量为 \(b\) 的倍数时，等式仍满足

因此到最后，如果 \(x\) 太小就不断 \(+b\) 直到 \(>=0\)，反之则一直减直到最小正整数值，就是这么写

x=(x%b+b)%b;

总代码如下

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
template<typename Tp> inline void read(Tp&x)
{
    x=0;register bool z=1;
    register char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
    for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    x=(z?x:~x+1);
}
int a,b,x,y;
int exgcd(int a,int b,int &x,int &y)
{
    if(b==0) {x=1;y=0;return a;}
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
signed main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    read(a),read(b);
    exgcd(a,b,x,y);
    x=(x%b+b)%b;
    cout<<x;
}