给定不定方程
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;
}