给定不定方程

ax+by=c

若该方程无整数解,输出 −1
若该方程有整数解,且有正整数解,则输出其正整数解的数量,所有正整数解中 x 的最小值,所有正整数解中 y 的最小值,所有正整数解中 x 的最大值,以及所有正整数解中 y 的最大值
若方程有整数解,但没有正整数解,你需要输出所有整数解中 x 的最小正整数值, y 的最小正整数值

正整数解即为 x,y 均为正整数的解, 0 不是正整数
整数解即为 x,y 均为整数的解
x 的最小正整数值即所有 x 为正整数的整数解中 x 的最小值,y 同理

输入格式
第一行一个正整数 T,代表数据组数

接下来 T 行,三个由空格隔开的正整数 a,b,c

输出格式
T 行

若该行对应的询问无整数解,一个数字 −1
若该行对应的询问有整数解但无正整数解,包含 2 个由空格隔开的数字,依次代表整数解中,x 的最小正整数值,y 的最小正整数值
否则包含 5 个由空格隔开的数字,依次代表正整数解的数量,正整数解中,x 的最小值,y 的最小值,x 的最大值,y 的最大值

读入输出量较大,注意使用较快的读入输出方式

输入输出样例
输入 #1 复制
7
2 11 100
3 18 6
192 608 17
19 2 60817
11 45 14
19 19 810
98 76 5432
输出 #1 复制
4 6 2 39 8
2 1
-1
1600 1 18 3199 30399
34 3
-1
2 12 7 50 56
说明/提示
【数据范围】

对于 100%100% 的数据,1≤T≤2×105,1≤a,b,c≤109

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define ll long long
#define llu unsigned ll
using namespace std;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0)
    {
        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;
}

int main(void)
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        ll a,b,c;
        scanf("%lld%lld%lld",&a,&b,&c);
        ll x,y;
        ll d=exgcd(a,b,x,y);
        if(c%d)// 无解
        {
            printf("-1\n");
            continue;
        }

        x=x*c/d,y=y*c/d;
        ll aa=a/d,bb=b/d;
        x=x%bb;
        if(x<=0) x+=bb;
        ll ymax=(c-x*a)/b;

        if(ymax<=0)//无正整数解
        {
            printf("%lld %lld\n",x,(y%aa<=0)?y%aa+aa:y%aa);
            continue;
        }

        y=y%aa;
        if(y<=0) y+=aa;
        ll xmax=(c-y*b)/a;
        printf("%lld %lld %lld %lld %lld\n",(xmax-x)/bb+1,x,y,xmax,ymax);
    }
    return 0;
}