线性同余方程求解：为什么需要将 b 除以最大公约数 d？

#include<bits/stdc++.h>\nusing namespace std; \ntypedef long long ll; \nconst ll mn=1e6+10; \nconst ll inf=2e18; \nll exgcd(ll a,ll b,ll &x,ll &y){\n if(b==0){\n x=1; \n y=0; \n return a; \n }\n ll x1,y1,d; \n d=exgcd(b,a%b,x1,y1); \n x=y1,y=x1-a/by1; \n return d; \n}\nvoid solve(){\n ll x=0,y=0; \n ll a,b,c; \n cin>>a>>b>>c; \n if(c%__gcd(a,b)!=0) cout<<-1<<'\n'; \n else{\n ll d=exgcd(a,b,x,y); \n ll ans=inf; \n ll t=b/d; \n a/=d; \n b/=d; \n c/=d; \n x=(xc%b+b)%b; \n //cout<<x<<' '<<y<<'\n'; \n for(int k=-8;k<=8;k++){\n ll xx=x+kt; \n ll yy=(c-axx)/b; \n if(xx>=0&&yy>=0) ans=min(ans,2*(xx+yy)); \n else ans=min(ans,2*abs(xx-yy)-1); \n }\n //cout<<x1<<' '<<y1<<'\n'; \n cout<<ans<<'\n'; \n }\n}\nint main(){\n ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); \n int tt; \n cin>>tt; \n while(tt--){\n solve(); \n }\n} \n在求解线性同余方程 ax + by = c 时，需要先判断 c 是否是 a 和 b 的最大公约数的倍数。如果不是，则无解。 \n \n在判断 c 是否是最大公约数的倍数后，我们可以将方程两边同时除以最大公约数 d，得到新的方程 (a/d)x + (b/d)y = c/d。 \n \n由于 a 和 b 都被 d 整除，所以我们可以将 a 和 b 分别除以 d，得到新的方程 a'x + b'y = c/d。 \n \n这样做的目的是为了简化方程，使得 a 和 b 的最大公约数变为 1，方便后续求解。 \n \n因此，我们需要将 b 除以 d，得到新的方程 a'x + b'y = c/d。