#include using namespace std; typedef long long LL; //扩展欧几里得 LL exgcd(LL a, LL b, LL &x, LL &y) { if (!b) { x = 1, y = 0; return a; } LL d = exgcd(b, a % b, y, x); y -= a / b * x; return d; } /* 测试用例: 1 2 3 5 答案: 1 1 1 1 1 */ int main() { int t; scanf("%d", &t); while (t--) { LL a, b, c; scanf("%lld %lld %lld", &a, &b, &c); LL x, y; LL d = __gcd(a, b); //使用库函数__gcd计算最大公约数d if (c % d) //裴蜀定理,当gcd(a,b)不能整除c时,方程无解,输出-1 puts("-1"); else { //这步很值得总结:一个方程拿到手,第一步是化简,就是把a,b,c中都除以gcd(a,b),实现化简 //举个栗子:2x+4y=8 -> x+2y=4 很直白吧,套路吧~ 此方程与原方程的角系一样吧~ //当然,也可能化简不了,比如: 2x+3y=5,因为gcd(2,3)=1,化不化简都一样 //但这里有一个事实,因为 a'=a/gcd(a,b),b'=b/gcd(a,b)后,a',b'肯定是互质。 //令d'=gcd(a',b') 现在d'=1 a /= d, b /= d, c /= d; //扩展欧几里得,一通用形式返回d,在有的题解中,不采用exgcd返回d,而是用__gcd计算d. //把扩展欧几里得算法定位为取特解x,y专用,也是比较直观简便的。 //性能上嘛,由于辗转相除法不断的变更除数,速度上很快,两次也没有问题。 //扩欧的形式:ax+by=gcd(a,b),求方程的一组解 x,y。现在的情况下,gcd(a,b)=1了,可以 exgcd(a, b, x, y); x *= c, y *= c; //结果(x,y)需要乘以c才能还原为ax+by=c的方程解。 /* 通解公式: x=x0+b/d*t y=y0-a/d*t 此时d=1,则通解公式: x=x0+b*t y=y0-a*t 想要xmin => x0固定值,b固定值,只能变化的是t,每变化一次就增加、减少一个b */ // printf("x=%lld y=%lld a=%lld b=%lld\n", x, y, a, b); LL xmin = (x % b + b) % b; //利用最小正整数解的公式(需要特判0) if (xmin == 0) xmin = b; // xmin如果是0,需要特判,加一个b搞定~ LL ymin = (y % a + a) % a; //利用最小正整数解的公式(需要特判0) if (ymin == 0) ymin = a; // ymin如果是0,需要特判,加一个a搞定~ // printf("xmin=%lld ymin=%lld\n", xmin, ymin); // x最大值怎么求呢?简单利用原始方程变形求 // ax+by=c => ax=c-by => x = (c-by)/a // x要想最大,则y必须取最小值 LL xmax = (c - b * ymin) / a; // y要想最大,则x必须取最小值 LL ymax = (c - a * xmin) / b; if (xmax <= 0 || ymax <= 0) //若最大值还不是正整数,则无正整数解 printf("%lld %lld\n", xmin, ymin); //输出最小值 else { //解的个数是最大 x 最小 x 的差除以模数 b 再加上1。 LL sum = (xmax - xmin) / b + 1; //不足b时,也有1个解,+b就增加一个解 printf("%lld %lld %lld %lld %lld\n", sum, xmin, ymin, xmax, ymax); } } } return 0; }