求关于 \(x\) 的同余方程 \(ax\equiv 1 (\bmod b)\) 的最小正整数解。
根据取模的性质，这个方程相当于 \(ax+by=1\)，其中 \(y\) 为负数，形式类似于扩展欧几里得的经典形式 \(ax+by=\gcd(a,b)\)。
方程 \(ax+by=m\) 有整数解的必要条件是 \(\gcd(a,b)|m\)，此处 \(m=1\)，所以有 \(\gcd(a,b)=1=m\)。也就是说方程 \(ax+by=1 \iff ax+by=\gcd(a,b)\)，我们可以直接使用扩展欧几里得求解。
假设我们已知一组整数 \(x_1,y_1\) 使得 \(bx_1+(a\bmod b)y_1=\gcd(a,b)\) 成立，则有 \(ax+by=bx_1+(a\bmod b)y_1\) 成立。由取模的性质得，\(ax+by=bx_1+(a-b\cdot\lfloor\dfrac{a}{b}\rfloor)y_1=ay_1+b(x_1+\lfloor\dfrac{a}{b}\rfloor y_1)\)，得到一组解 \(x=y_1,y=x_1+\lfloor\dfrac{a}{b}\rfloor y_1\)。这样，只要知道了一组 \(x_1,y_1\)，就能够得到一组 \(x,y\)。
那么怎么求 \(x_1,y_1\) 呢？我们发现，定义 \(x_1,y_1\) 的方程 \(bx_1+(a\bmod b)y_1=\gcd(a,b)\) 和 \(ax+by=\gcd(a,b)\) 形式相同，可以用同样的方法，令 \(ax+by=\gcd(a,b)\) 中的 \(a=b,b=a\bmod b\)，再去找一组 \(x_2,y_2\) 满足 \(bx_2+(a\bmod b)y_2=\gcd(a,b)\)。知道了 \(x_2,y_2\)，就知道了 \(x_1,y_1\)……依此类推。
类似欧几里得算法，递归边界是 \(a=\gcd(a,b),b=0\)，又 \(ax_n+by_n=\gcd(a,b)\)，所以 \(x_n=1,y_n\) 取任意值（为避免溢出，一般取 \(0\)），递归回去求出一开始的 \(x,y\) 即可。
此时的答案尚不符合题目“最小”的要求，需要进一步处理。设 \(a=m+bn\)，\(n\) 极大，于是原方程为 \((m+bn)x+by=1 \iff mx+b(nx+y)=1\) 使得 \(x\) 最小，所以直接 \(x\bmod b\)即可，注意调整范围避免出现负数。
下面是 AC 代码：
void exgcd(int a, int b, int &x, int &y) {
if (!b) return x = 1, y = 0, void();
exgcd(b, a % b, y, x);
y = y - (a / b) * x;
}
//main
exgcd(a, b, x, y);
x = (x % b + b) % b;