谁发明的啊!!!!!!!!!!!!!!!
2025-08-05 17:12:25
发布于:上海
4阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
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;
}
//向下取整
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,x0,y0;
cin>>a>>b>>c;
ll g=exgcd(a,b,x0,y0);
if(c%g!=0){
cout<<-1<<endl;
return ;
}
//特解
ll x1=x0*c/g;
ll y1=y0*c/g;
//通解参数
ll dx=b/g,dy=a/g;
ll t_l=ceil_div(1-x1,dx);
ll t_r=floor_div(y1-1,dy);
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<<endl;
}
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<<endl;
}
}
int main(){
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}
这里空空如也
有帮助,赞一个