没有整数解当且仅当 \(\gcd(a,b)\nmid c\),直接输出 -1
。
用 exgcd 解方程 \(ax+by=\gcd(a,b)\) 得到一组特解 \(x_0,y_0\)。对原方程变形得到 \(a\cdot\dfrac{xc}{\gcd(a,b)}+b\cdot\dfrac{yc}{\gcd(a,b)}=c\),于是有 \(ax+by=c\) 的一组特解 \(x_1=\dfrac{xc}{\gcd(a,b)},y_1=\dfrac{yc}{\gcd(a,b)}\)。
接下来,由「同余方程」一题中的技巧,用 x=(x%b+b)%b, y=(y%a+a)%a;
求出 \(x,y\) 的最小取值 \(x_{\min},y_{\min}\),因为 \(x\) 增大 \(y\) 减小,可以直接分别带入原方程,求出 \(y_{\max},x_{\max}\)。如果 \(x_{\max},y_{\max}<0\),则没有正整数解,直接输出两个最小值即可;否则有正整数解,分别输出最大值、最小值和解的个数。