Nowcoder practice 60 D.斩杀线计算大师(扩展欧几里得）


思路：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
#define mst(a) memset(a,0,sizeof a)
void egcd(ll a,ll b,ll &x,ll &y){
	if(b==0){
		x=1,y=0;
		return;
	}
	egcd(b,a%b,x,y);
	ll tmp=x;
	x=y;
	y=tmp-a/b*y;
}
int main(){
	ll a,b,c,k,t;
    cin>>a>>b>>c>>k;
    ll g=__gcd(a,b);
	for(int i=0;i<=k/c;i++)
	{
		if((k-i*c)%g==0)
		{
			ll x,y;
			egcd(a,b,x,y);
			t=(k-i*c)/g;	// ax=gcd(modb) ax%b=(a*x%b)%b ax%b=(ax+b)%b 
			ll x1=x*t,y1=y*t,b1=b/g;  //ax与b同余 b1最小的对x1操作的。 
			x1=(x1%b1+b1)%b1;//保证x1>=0 x1+b1*t 找到最小整数解 x1%b1找到在0-b1范围内 若小于0则加上b1 
			y1=(k-i*c-x1*a)/b;
			if(x1>=0&&y1>=0)
			{
				 printf("%lld %lld %lld\n",x1,y1,i);
				 break;
			}
		}	
	} 
	return 0;
}