扩展欧几里得

考虑问题求\(\ ax\equiv 1\pmod{b}\)的最小整数解，其中\(2 \leqslant a,b \leqslant 2000000000\)
\(\\\)
数据范围这么大我们肯定不能枚举，考虑别的方法。
\(\\\)
发现问题可以转化为：求\(ax_0+by_0=1\)的最小整数解\(x_0\)（此时\(y\)应该是负的）。
我们另写一个式子：\(bx_1 + (a-\lfloor \frac{a}{b} \rfloor)y_1 = 1\)，整理下这个式子，得到\(ay_1+b\left( x_1- \lfloor \frac{a}{b}y_1\rfloor \right)=1\)
\(\\\)
这两个式子对应相等，我们可以得到关系：\(x_0 = y_1, y_0=x_1 - \lfloor \frac{a}{b}\rfloor y_1\)，得到第二个式子，我们就是运用辗转相除的结果来变成系数，所以在\(log\)复杂度下我们会得到\(a_nx_n + b \times 0 = 1\)，因为由裴属定理，这个不定方程要有解，则\(\gcd(a,b) | 1\)，所以只能\(\gcd(a,b)=1\)，所以最后\(a_n\)必定为1（我们由辗转相除来的），此时我们可以直接取\(x_n=\frac{1}{a_n}=1,y_n=0\)，然后回代即可。
\(\\\)
注意最后我们要得到最小正整数解，我们通过这个方式得到的不一定是正数，可以通过\(x_0=((x_0\mod b)+b)\mod b\)来解决问题。因为当\(x_0<0\)时，\(x_0\mod b\)会结果为\(-\left( -x_0\mod b \right)\)，所以这样就可以得到一个大于\(-b\)的负数，再加\(b\)即可得到最小的正数，如果\(x_0\)为正数，那么\(+b\)再\(\mod b\)没有影响。
\(\\\)

using namespace std;

int x0, yy0;

inline int read() {
	int x = 0, f = 1;
	char c = getchar();
	while (!isdigit(c)) {
		if (c == '-') f = -1;
		c = getchar();
	}
	while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
	return x * f;
}

inline void exgcd(int a, int b) {
	if (b == 0) {
		x0 = 1, yy0 = 0;
		return ;
	}
	exgcd(b, a % b);
	int temp = x0;
	x0 = yy0;
	yy0 = temp - (a / b) * yy0;
	return ;
}

int main() {
	int a, b;
	a = read(), b = read();
	exgcd(a, b);
	x0 = (x0 % b + b) % b;
	printf("%d", x0);
	return 0;
}