二元一次不定方程 (exgcd)（模板）
ax+by=d ——原式
ax+by=(a,b) ——变式
==> exgcd得变式的特解：x0; ==> 变式的通解：x=x0+b/_gcd;
==> 原式得特解： x0*=d/_gcd;
==> 原式得通解：x=x0+b/_gcd;
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int const mod=100000007;
int const N=1e6+7;
int t,a,b,d;
ll x,y;
int exgcd(int a,int b,ll& x,ll& y){
if(b==0){
x=1;y=0;
return a;
}
int res=exgcd(b,a%b,x,y);
ll t=x;
x=y;
y=t-a/b*y;
return res;
}
int main(){
cin >> t;
while(t--){
cin >> a >> b >> d;
int _gcd=exgcd(a,b,x,y);
if(d%_gcd) {
cout << "-1\n";continue;
}
x*=d/_gcd;y*=d/_gcd;
ll k1=b/_gcd,k2=a/_gcd;
ll tt=abs(x/k1);
if(x<0){
x+=tt*k1;
y-=tt*k2;
if(x<=0) x+=k1,y-=k2;
}
else {
x-=tt*k1;
y+=tt*k2;
if(x<=0) x+=k1,y-=k2;
}
if(y<=0){
y=(y%k2+k2)%k2;
if(y==0) y=k2;
cout << x << " " << y << "\n";
continue;
}
tt=y/k2 - (y%k2==0?1:0);
cout << tt+1 << " " << x << " " << y-tt*k2 << " "<< x+tt*k1 << " "<< y << "\n";
}
return 0;
}
美团成长空间 2792人发布