定义
含有两个未知数，且未知数项的次数都是 \(1\) 的不定方程就是二元一次不定方程，一般可以化成下面的形式：
\[ax+by=c \]前置知识
裴蜀定理
定理：对于一个二元一次不定方程，当 \(\gcd(a,b)|c\) 存在整数解。
证明：设 \(c = k \times \gcd(a,b)\) ，只需证明 \(ax+by=\gcd(a,b)\) 有整数解，因为把等式两边同时乘 \(k\) 即可得到 \(a(x\times k) + b(x \times k)=c\) 。
设 \(a_0 = \frac{a}{\gcd(a,b)}\) , \(b_0 = \frac{b}{\gcd(a,b)}\) ，则 \(a_0 \perp b_0\)， 则方程可以化为：
\[a_0x+b_0y=1 \]为了证明这个方程有整数解，我们可以构造一组解。设 \(a_0^{-1}\) 是 \(a_0\) 在模 \(b_0\) 意义下的逆元，我们可以得到：
\[a_0a_0^{-1}-b_0\times \lfloor\frac{a_0a_0^{-1}}{b_0}\rfloor=1 \]因为 \(a_0a_0^{-1} \equiv 1 \pmod {b_0}\) ，所以设 \(a_0a_0^{-1}=kb_0+1\)， \(\lfloor\frac{a_0a_0^{-1}}{b_0}\rfloor=k\) ，代入原式得：
\[(kb_0+1)-b_0=1 \]\[1=1 \]\(therefore\) 对于方程 \(a_0x+b_0y=1\) 一定有整数解 \(x=a_0^{-1}, y = -\frac{a_0a_0^{-1}}{b_0}\) ，故方程 \(ax+by=c\) 一定有整数解，证毕。
辗转相除法
辗转相除法又称欧几里得（Euclid）算法，可以在 \(O(\log n)\) 的时间复杂度内求出 \(\gcd(a,b)\) ，设 \(a>b\) ，过程如下：
\[\gcd(a,b) = \begin{cases} b&{a=0} \\ \gcd(b,a \mod b)&{otherwise} \end{cases}\]这就是大多数时候求 \(\gcd\) 的方法。
求解二元一次不定方程
扩展欧几里得算法 （exEuclid）
对于一个二元一次不定方程 \(ax+by=\gcd(a,b)\) 来说，我们可以按照辗转相除法的方法来顺便求出 \(x,y\) 。
举个例子，当 \(a=39,b=15\) 时，执行辗转相除法的过程如下：
\[39,15 \to 15,9 \to 9,6 \to 6,3 \to 3,0 \]我们先考虑最后一个方程，设 \(a_0,b_0\) 为当前的 \(a,b\) ，\(x_0,y_0\) 为当前的 \(x,y\) ，比如上面 \(a_0\) 就等于 \(3\) ，得到方程：
\[a_0x_0+b_0 \times y_0=\gcd(a,b) \]\(\because b_0=0\) ， \(\therefore\) 方程变为
\[a_0x_0=\gcd(a,b) \]所以现在 \(x_0=\gcd(a,b) \div a_0\) ，而 \(a_0\) 就是 \(\gcd(a,b)\) ，所以\(x_0=1\)
。
现在我们往上推，设 \(a_1,b_1\) 为上一次的 \(a\) 和 \(b\) , 所以根据辗转相除法， \(a_0=b_1, b_0=a_1\bmod b = a_1-\lfloor\frac{a_1}{b_1}\rfloor\times b_1\) ，所以方程变为：
\[b_1\times x_0 + (a_1-\lfloor\frac{a_1}{b_1}\rfloor \times b_1)\times y_0=\gcd(a,b) \]把 \(a_1\) 和 \(b_1\) 提出来得：
\[a_1 \times y_0 + b_1 \times (x_0-\lfloor\frac{a_1}{b_1}\rfloor \times y_0) =\gcd(a,b) \]这样新的解就是 \(x1 = y_0,y_1=x_0-\lfloor\frac{a_1}{b_1}\rfloor\times y_0\)
，然后就可以再往上推了。这就是扩展欧几里得算法，时间复杂度和辗转相除法一样，都是 \(O(\log n)\) 。
code
//a>=b,返回gcd(a,b)，并修改x,y，使得ax+by=gcd(a,b)
int exEuc(int a, int b, int &x, int &y) {
if (b == 0) {//结束条件
x = 1, y = 0;
return a;
}
int t = exEuc(b, a % b, x, y);
int x0 = x, y0 = y;//暂记录上次的结果
x = y0, y = x0 - (a / b) * y0;
return t;
}
方程的多个解
对于一个二元一次方程 \(ax+by=c\) ，要么没有整数解，要么有无穷多个整数解和有限个正整数解，对于任意一组整数解 \(x_0.y_0\) 和整数 \(k\) ，\(a_0 = \frac{a}{\gcd(a,b)},b_0 = \frac{b}{\gcd(a,b)},c_0=\frac{c}{\gcd(a,b)}\) ，满足于下面的算式的都是解：
\[\begin{cases} x_k=x_0+k \times b_0\\ y_k=y_0-k\times a_0 \end{cases}\]所有整数解都可以这样算出来，这也很好理解，下面证一下：
\[a_0x_0+b_0y_0=c_0 \]\[a_0x_0+b_0y_0+a_0\times k \times b_0 - a_0 \times k \times b_0 = c_0 \]\[a_0(x_0+k \times b_0) + b_0(y_0-k \times a_0) = c_0 \]\[a_0x_k+b_0y_k=c_0 \]得证。
一些题目
题意：有点多，自己看吧。
思路：
对于 \(c\not|\gcd(a,b)\)，说明无解。
对于有解，先求出 \(x,y\) 的最小正整数值，而 \(x\) 的最小正整数值与 \(y\) 的最大正整数值是一组解，反之亦然，所以判断这样算出的 \(x,y\) 的最大正整数值是否为正整数，不是直接输出最小值，是的话正整数解的个数就是 \(x\) 的最大值与最小值的差除以 \(b_0\) 加一。
code
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
ll exEuc(ll a, ll b, ll &x, ll &y) {
if (b == 0) {
x = 1, y = 0;
return a;
}
ll t = exEuc(b, a % b, x, y);
ll x0 = x, y0 = y;
x = y0, y = x0 - (a / b) * y0;
return t;
}
ll a, b, c;
void solve() {
scanf("%lld%lld%lld", &a, &b, &c);
ll x, y;
ll g = exEuc(a, b, x, y);
if (c % g != 0)
printf("-1\n");
else {
x = x * (c / g), y = y * (c / g);
ll a0 = a / g, b0 = b / g;
ll x0 = (x > 0 ? -1ll * floor(1.0 * x / b0) : 1ll * ceil(1.0 * (0 - x) / b0));
ll y0 = (y > 0 ? -1ll * floor(1.0 * y / a0) : 1ll * ceil(1.0 * (0 - y) / a0));
x0 += (x + x0 * b0 == 0), y0 += (y + y0 * a0 == 0);
if (y - a0 * x0 <= 0 && x - b0 * y0 <= 0)
printf("%lld %lld\n", x + x0 * b0, y + y0 * a0);
else {
ll x1 = x - b0 * y0, y1 = y - a0 * x0;
x0 = x + x0 * b0, y0 = y + y0 * a0;
printf("%lld %lld %lld %lld %lld\n", (x1 - x0) / b0 + 1, x0, y0, x1, y1);
}
}
}
int main() {
int T;
scanf("%d", &T);
while (T--)
solve();
return 0;
}