这是一道模板题（bushi）
首先，说实话，我感觉做这道题比较吃力，毕竟我是刚刚背过(exgcd)代码，并且只是小小的对找正整数解有所了解，所以写了半天才做出来。做这种数论题确实是对计算能力和逻辑思维的考验，而且从难度上看，我这个蒟蒻能做出绿题，也有点小小的成就感。
今天开始停课备战(CSP)，下午在机房打板子，打到(exgcd)，突然发现我板子题还没(A)，其他的拓展题倒是做了不少，遂开始切板子题。
思路
其实思路非常简单，就是代码实现细节真的比较多（而且我貌似写的很麻烦，写了足足有130多行）。首先用真板子来求出一组特解，然后判断是否有解。在找最小整数解的时候，要特判一波：如果有一组解能满足(x)和(y)都是正整数，那么就要输出5个数。反之，则只需要输出(x)和(y)的最小整数解。
那么首先最好写的就是求出的特解都是正整数的情况，只需要用一波取模的常规操作求出一个最小正整数解，那么同时另一个解就是最大正整数解。即(x)最小时，(y)最大。就这样求出四个最值。个数可以通过最大解和最小解中间差了几个(a/d)或(b/d)即可（原理就是求最小正整数解的操作，详情可见【青蛙的约会】）。然后中间稍微手玩一下，就能找到个数与最值之间的关系。
ll x1=(x1%(b/d)+(b/d))%(b/d);
ll y1=(y1%(a/d)+(a/d))%(a/d);//求出最小值
if(x1==0){//特判，必须是正整数
x1=b/d;
}
if(y1==0){
y1=a/d;
}
ll x2=(c-y1*b)/a;
ll y2=(c-x1*a)/b;//根据最小值推出最大值
ll sum;
if(x2%(b/d)==0){//手玩即可找到规律，推导为小学数学水平
sum=x2/(b/d);
x1=a/d;
}
else{
sum=x2/(b/d)+1;
x1=x2%(b/d);
}
那么接下来就是(x)和(y)这一组特解中有一个为非正整数的情况了，虽然这种情况相对复杂，但是原理是一样的。假设(x)是负的，那么(y)必然是正的，否则不可能得到正数结果。那么我们就让(x)不断地加上(b/d)，为保持等式成立，也要让(y)同时减去(a/d)。这样将(x)变为正数。如果(x)变为正数后(y)变为了负数，那么就说明不可能有正整数解，这时候只要进行一步常规取模操作，输出最小正整数解即可。但是如果(x)变为正数后(y)依然是正数，就相当于变回了第一种情况，再操作即可。
思路就是这么简单，但是代码实现的确有难度。首先我们思考(x)需要几个(b/d)才能变成正数，首先可以将(x)变为相反数，便于我们进行除法。由于除法是向下取整，所以我们用(x)除以(b/d)还要再加一个(b/d)才行（即使整除也要加，因为0并不是正整数）。所以我们就可以用(x/(b/d)+1)来求得加的(b/d)的个数，同时(y)也要减。然后再按照上述思路判断即可。
if(x<=0){
x=-x;
int k=x/(b/d)+1;
x-=k*(b/d);
x=-x;
y-=k*(a/d);
if(y>0){//有正整数解
ll x1=x,y2=y,sum,y1;
if(y2%(a/d)==0){
sum=y2/(a/d);
y1=a/d;
}
else{
sum=y2/(a/d)+1;
y1=y2%(a/d);
}
ll x2=(c-y1*b)/a;
printf("%lld %lld %lld %lld %lld
",sum,x1,y1,x2,y2);
continue;
}
else{//无正整数解
ll x1=(xx%(b/d)+(b/d))%(b/d);
ll y1=(yy%(a/d)+(a/d))%(a/d);
if(x1==0){
x1=b/d;
}
if(y1==0){
y1=a/d;
}
printf("%lld %lld
",x1,y1);
continue;
}
}
做完了
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
int T;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
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()
{
scanf("%d",&T);
while(T--){
ll a,b,c,x,y;
a=read();b=read();c=read();
ll d=exgcd(a,b,x,y);
if(c%d!=0){
printf("-1
");
continue;
}
else{
x*=c/d,y*=c/d;
ll xx=x,yy=y;
if(x<=0){
x=-x;
int k=x/(b/d)+1;
x-=k*(b/d);
x=-x;
y-=k*(a/d);
if(y>0){//有正整数解
ll x1=x,y2=y,sum,y1;
if(y2%(a/d)==0){
sum=y2/(a/d);
y1=a/d;
}
else{
sum=y2/(a/d)+1;
y1=y2%(a/d);
}
ll x2=(c-y1*b)/a;
printf("%lld %lld %lld %lld %lld
",sum,x1,y1,x2,y2);
continue;
}
else{//无正整数解
ll x1=(xx%(b/d)+(b/d))%(b/d);
ll y1=(yy%(a/d)+(a/d))%(a/d);
if(x1==0){
x1=b/d;
}
if(y1==0){
y1=a/d;
}
printf("%lld %lld
",x1,y1);
continue;
}
}
if(y<=0){
y=-y;
int k=y/(a/d)+1;
y-=k*(a/d);
y=-y;
x-=k*(b/d);
if(x>0){//有正整数解 (y为最小整数解
ll y1=y,x2=x,x1,sum;
if(x2%(b/d)==0){
sum=x2/(b/d);
x1=b/d;
}
else{
sum=x2/(b/d)+1;
x1=x2%(b/d);
}
ll y2=(c-x1*a)/b;
printf("%lld %lld %lld %lld %lld
",sum,x1,y1,x2,y2);
continue;
}
else{
ll x1=(xx%(b/d)+(b/d))%(b/d);
ll y1=(yy%(a/d)+(a/d))%(a/d);
if(x1==0){
x1=b/d;
}
if(y1==0){
y1=a/d;
}
printf("%lld %lld
",x1,y1);
continue;
}
}
ll x1=(x1%(b/d)+(b/d))%(b/d);
ll y1=(y1%(a/d)+(a/d))%(a/d);
if(x1==0){
x1=b/d;
}
if(y1==0){
y1=a/d;
}
ll x2=(c-y1*b)/a;
ll y2=(c-x1*a)/b;
ll sum;
if(x2%(b/d)==0){
sum=x2/(b/d);
x1=a/d;
}
else{
sum=x2/(b/d)+1;
x1=x2%(b/d);
}
}
}
return 0;
}
中间出了两个小锅，耗费了我大量时间：一个是我忘记判x>0&&y>0的情况了，可能是因为这种情况相比于其它的情况太水了，所以忘记了。第二个，由于y<0和x<0的代码绝大部分都是一样的，只不过需要该两个变量名，所以我直接复制粘贴之后一个个改变量名。结果漏改了一个，导致出锅。