扩展欧几里得
本题要点：
1、这里需要解方程 ax + by = c 的所有正整数解。
不过，有个前提，a, b, c 都是正整数， 后面方便处理很多。
2、记 d = gcd(a, b), 如果 c % d != 0, 说明方程无整数解。
3、 用 扩展欧几里得 exgcd 算出 ax + by = gcd(a, b) 的 解 x0, y0;
那么原方程 ax + by = c 的所有 整数解可以表示为
x = (c/d)x0 + k(b/d)
y = (c/d)y0 - k(a/d), 其中，k取遍所有整数。
4、 记 m1 = b/d, m2 = a/d,
x 的最小正整数为： min_x = (x % m1 + m1) % m1,
y 的最小正整数为： min_y = (y % m2 + m2) % m2;
这里算出来的 min_x， min_y 可能为0， 只需加上 m1, m2 即可。
5、当 x 取得最小的正整数， 对应的 y 最大的正整数（如果存在的话）
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
int T;
ll a, b, c;ll exgcd(ll a, ll b, ll& x, ll& y)
{
if(0 == b){
x = 1, y = 0;return a;}ll d = exgcd(b, a % b, x, y);ll z = x; x = y; y = z - y * (a / b);return d;
}void solve()
{
ll x0, y0;ll d = exgcd(a, b, x0, y0);if(c % d) // 无解{
printf("-1\n");return;}// 注意到 a, b, c都是正整数ll m1 = b / d, m2 = a / d; ll x = c / d * x0, y = c / d * y0;ll min_x = (x % m1 + m1) % m1, min_y = (y % m2 + m2) % m2; if(!min_x) min_x += m1;if(!min_y) min_y += m2;ll max_y = (c - a * min_x) / b, max_x = (c - b * min_y) / a;if(max_y <= 0){
printf("%lld %lld\n", min_x, min_y);return;}int cnt = (max_x - min_x) / m1 + 1; // 正整数解printf("%d %lld %lld %lld %lld\n", cnt, min_x, min_y, max_x, max_y);}int main()
{
scanf("%d", &T);while(T--){
scanf("%lld%lld%lld", &a, &b, &c); solve();}return 0;
}/* 7 2 11 100 3 18 6 192 608 17 19 2 60817 11 45 14 19 19 810 98 76 5432 *//* 4 6 2 39 8 2 1 -1 1600 1 18 3199 30399 34 3 -1 2 12 7 50 56 */