牛客练习赛60d斩杀线计算大师，exgcd
斩杀线计算大师
http://www.nowcoder.com/questionTerminal/87e4a81191134d45a9374a275d990ff1
把x遍历一遍，然后把转化为关于y，z的yb+zc=（k-xa）的二元一次方程（exgcd模板题），exgcd求解
用exgcd求出的是y0，然后转成y（放大（k-xa）/gcd倍），这里的t是y的最小增幅
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,c,x,y,z,d,s,k,ym;
int exgcd(ll a,ll b,ll &x,ll &y){
if(!b){
x=1, y=0;
return a;
}
int d;
d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
int main(){
cin>>a>>b>>c>>k;
for(int i=0;i*a<=k;i++){
s=k-i*a;
d=__gcd(b,c);
if(s%d) continue;
d=exgcd(b,c,y,z);
y=y*s/d;//y0转y
ll t=c/d;
y=(y%t+t)%t;//y的最小正整数解
if(s%d==0&&k-i*a-b*y>=0){
cout<<i<<" "<<y<<" "<<(k-i*a-b*y)/c<<endl;;
return 0;
}
}
return 0;
} 其实比赛暴力莽就完事了，就看你比赛敢不敢交
当然也要缩小下暴力范围
额，😓这题比赛时的数据有点弱，遍历y（1~k）,z然后用if（k-y*b-z*c）%a==0可以莽过去，但是遍历x,y求z或者遍历x,z求y就会tel
当然我也是莽过去的
创作不易，
（你懂的）
（你懂的） 
投递蔚来等公司10个岗位 >
