【模板】二元一次不定方程(exgcd)

(p1=frac{b}{d} p2=frac{a}{d})（思考一下如何证明）

(x=x0+k*p1 \y=y0-k*p2\)

这里的k是同一个数 （思考一下如何证明）

需要注意的是把 (ax+by=d) 转化为 (ax+by=c) 时 p1和p2保持不变而不是翻倍 （思考一下如何证明）

处理正整数解问题时

x取最小正整数时，y会取到最大正整数

y取最小正整数时，x会取到最大正整数

x增大则y必然减小

y增大则x必然减小

统计解的个数时只需要根据这个原理看一下最多能放下多少组x或y即可

#include<bits/stdc++.h>
#define N 110000
#define eps 1e-7
#define inf 1e9+7
#define db double
#define ll long long
#define ldb long double
#define ull unsigned long long
using namespace std;
inline ll read()
{
    char ch=0;
    ll x=0,flag=1;
    while(!isdigit(ch)){ch=getchar();if(ch=='-')flag=-1;}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0',ch=getchar();}
    return x*flag;
}
ll X,Y;
ll exgcd(ll a,ll b)
{
    if(!b){X=1;Y=0;return a;}
    ll d=exgcd(b,a%b);
    ll t=X;X=Y;Y=t-(a/b)*Y;
    return d;
}
void work()
{
    ll a=read(),b=read(),c=read();
    ll d=exgcd(a,b),p1=b/d,p2=a/d,k=c/d;
    if(c%d){printf("-1n");return;}
    X*=k;Y*=k;X=(X%p1+p1)%p1;if(!X)X+=p1;Y=(c-a*X)/b;
    if(X>0&&Y>0)
    {
        ll num,xmin,ymin,xmax,ymax;
        num=(Y-1)/p2+1;
        X=(X%p1+p1)%p1;if(!X)X+=p1;Y=(c-a*X)/b;xmin=X;ymax=Y;
        Y=(Y%p2+p2)%p2;if(!Y)Y+=p2;X=(c-b*Y)/a;ymin=Y;xmax=X;
        printf("%lld %lld %lld %lld %lldn",num,xmin,ymin,xmax,ymax);
    }
    else
    {
        ll xmin,ymin;
        X=(X%p1+p1)%p1;if(!X)X+=p1;Y=(c-a*X)/b;xmin=X;
        Y=(Y%p2+p2)%p2;if(!Y)Y+=p2;X=(c-b*Y)/a;ymin=Y;
        printf("%lld %lldn",xmin,ymin);
    }
}
int main()
{
    ll t=read();
    for(ll i=1;i<=t;i++)work();
    return 0;
}