题解 注释看不懂那就别看了

数论真是阴得没边了

有点小长版

#include<iostream>
using namespace std;
typedef long long ll;
//ax+by=gcd(a,b)
//x=y1 y=x1-a/b*y1
ll exgcd(ll a,ll b,ll &x,ll &y){//返回gcd(a,b)
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    ll x1,y1;
    ll g=exgcd(b,a%b,x1,y1);
    x=y1;
    y=x1-a/b*y1;
    return g;
}
//向上取整 p/q
ll ceil_div(ll p,ll q){
    if(p==0)return 0;
    if(p>0)return (p+q-1)/q;
    else return p/q;//小于0的情况就是向零取整
}
//向下取整 p/q
ll floor_div(ll p,ll q){
    if(p%q==0)return p/q;
    else if(p<0)return p/q-1;
    else return p/q;
}
void solve(){
    ll a,b,c;
    cin>>a>>b>>c;
    ll x0,y0;
    ll g=exgcd(a,b,x0,y0);
    //无解情况
    if(c%g!=0){
        cout<<"-1\n";
        return ;
    }
    //特解
    ll x1=x0*c/g;
    ll y1=y0*c/g;
    //通解参数
    //x=x1+dx*t  y=y1-dy*t
    ll dx=b/g,dy=a/g;
    ll t_l=ceil_div(1-x1,dx);//t的下界
    ll t_r=floor_div(y1-1,dy);//t的上界
    if(t_l<=t_r){
        ll cnt=t_r-t_l+1;
        ll xmin=x1+dx*t_l;
        ll xmax=x1+dx*t_r;
        ll ymin=y1-dy*t_r;
        ll ymax=y1-dy*t_l;
        cout<<cnt<<" "<<xmin<<" "<<ymin<<" "<<xmax<<" "<<ymax<<"\n";
    }else{//无正整数解
        ll xmin=(x1%dx+dx)%dx;
        if(xmin==0)xmin=dx;
        ll ymin=(y1%dy+dy)%dy;
        if(ymin==0)ymin=dy;
        cout<<xmin<<" "<<ymin<<"\n";
    }
}
int main(){
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

优化简单版

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll a,b,d,x,y;
bool exgcd(ll a,ll b,ll &x,ll &y,ll d){//返回gcd(a,b)
    if(b==0){
        if(d%a==0){
            x=d/a;
            y=0;
            return true;
        }
        return false;
    }
    ll x1,y1;
    if(exgcd(b,a%b,x1,y1,d)){
        x=y1;
        y=x1-a/b*y1;
        return true;
    }
    return false;
}
void solve(){
    cin>>a>>b>>d;
    bool res=exgcd(a,b,x,y,d);
    if(!res){
        cout<<"-1\n";
        return ;
    }
    //相当于x和y的变化量
    ll dx=b/__gcd(a,b);
    ll dy=a/__gcd(a,b);
    //x=x+k*dx  y=y-k*dy
    ll k=x%dx<=0?x/dx-1:x/dx;
    ll x0=x-k*dx;//x最小的整数解
    ll y0=y+k*dy;//y最大的正整数
    k=y%dy<=0?y/dy-1:y/dy;
    ll x1=x+k*dx;//x最大整数解
    ll y1=y-k*dy;//y最小整数解
    if(y0<=0){
        cout<<x0<<" "<<y1<<endl;
        return ;
    }
    ll cnt=(x1-x0)/dx+1;//正整数解的数量
    cout<<cnt<<" "<<x0<<" "<<y1<<" "<<x1<<" "<<y0<<endl;
}
int main(){
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}