方程\(ax+by=c\)被称为二元线性丢番图方程，其中\(a,b,c\)为确定值，\(x,y\)为变量。这个方程有无解和无穷多个解两种可能。
定理
- \(ax+by=c\)有解的充分必要条件是\(d=gcd(a,b)\)能整除\(c\)
- 若\(x_0\)和\(y_0\)是\(ax+by=gcd(a,b)\)的一组特解，那么\(ax+by=c\)的一组特解为\(x_0'=x_0c/d\)和\(y_0'=y_0c/d\)
- 如果有解，所有解的通解形式为\(x=x_0'+(b/d)n\)，\(y=y_0'-(a/d)n\)，其中\(x_0'\)和\(y_0'\)是其中一个特解
- \(x=(x\%t+t)\%t\)是\(x\)的一个最小非负整数解，其中\(t=b/d\)
- \(y=(y\%t+t)\%t\)是\(y\)的一个最小非负整数解，其中\(t=a/d\)
代码实现
int exgcd(int a, int b, int &x, int &y) { //用扩展欧几里得求出ax+by=gcd(a,b)的一组特解
if(b == 0) {
x = 1;
y = 0;
return a;
} else {
int d = exgcd(b, a % b, y, x);
y -= (a / b) * x;
return d;
}
}
bool func(int a, int b, int c, int &x, int &y) { //求出ax+by=c的一组特解
int d = exgcd(a, b, x, y);
if(c % d != 0) return false;
x *= c / d;
y *= c / d;
return true;
}
bool minx(int a, int b, int c, int &x, int &y) { //求出x的最小非负整数解
int d = exgcd(a, b, x, y);
if(c % d != 0) return false;
x *= c / d;
y *= c / d;
x = (x % (b / d) + b / d) % (b / d);
return true;
}
bool miny(int a, int b, int c, int &x, int &y) { //求出y的最小非负整数解
int d = exgcd(a, b, x, y);
if(c % d != 0) return false;
x *= c / d;
y *= c / d;
y = (y % (a / d) + a / d) % (a / d);
return true;
}