C++ 代码详解：求解线性方程 ax + by = c 的最小步数

#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mn=1e6+10; const ll inf=2e18; ll exgcd(ll a,ll b,ll &x,ll &y){ if(b==0){ x=1; y=0; return a; } ll x1,y1,d; d=exgcd(b,a%b,x1,y1); x=y1,y=x1-a/by1; return d; } void solve(){ ll x=0,y=0; ll a,b,c; cin>>a>>b>>c; if(c%__gcd(a,b)!=0) cout<<-1<<'\n'; else{ ll d=exgcd(a,b,x,y); ll ans=inf; ll t=b/d; a/=d; b/=d; c/=d; x=(xc%b+b)%b; //cout<<x<<" "<<y<<'\n'; for(int k=-8;k<=8;k++){ ll xx=x+kt; ll yy=(c-axx)/b; if(xx>=0&&yy>=0) ans=min(ans,2*(xx+yy)); else ans=min(ans,2*abs(xx-yy)-1); } //cout<<x1<<" "<<y1<<'\n'; cout<<ans<<'\n'; } } int main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); int tt; cin>>tt; while(tt--){ solve(); } }