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; }