Codeforces 1244 C. The Football Season —— 扩展欧几里得

本文主要是介绍Codeforces 1244 C. The Football Season —— 扩展欧几里得，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

This way

题意：

让你求dx+wy+0z=p,[0<=x,y,z&&x+y+z=n]

题解：

首先很明显可以暴力，因为d和w都是<=1e5的，所以枚举1e5次必然能出答案。
但是我们在学习新知识，所以必然不能这样子去简单地暴力，要搞一点数学的东西进去。
那么很明显是扩展欧几里得，但是裸的板子会有负数的情况，所以我们需要先贪心地放赢得局，因为这样子前两种局数会达到最小，然后剩下的再贪心地放平局，此时会有放不完的情况，那么这个剩余值我们就拿来做扩欧即可。
此时还是会有负数的情况，那么我们将赢的和平局看看哪个是负数，然后做一下gcd的调整即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
ll g;
void ex_gcd(ll a,ll b,ll& x,ll& y){if(!b){g=a;x=1,y=0;}else {ex_gcd(b,a%b,y,x);y=y-a/b*x;}
}
int main()
{ll n,p,w,d;scanf("%lld%lld%lld%lld",&n,&p,&w,&d);ll x,y;ex_gcd(w,d,x,y);ll v1=p/w;ll res=p%w;ll v2=res/d;res=res%d;if(res%g!=0)return 0*printf("-1\n");while(v1+x*(res/g)<0)v1+=d/g,v2-=w/g;while(v2+y*(res/g)<0)v1-=d/g,v2+=w/g;if(v1+x*(res/g)<0||v2+y*(res/g)<0||n-v1-x*(res/g)-v2-y*(res/g)<0)return 0*printf("-1\n");return 0*printf("%lld %lld %lld\n",v1+x*(res/g),v2+y*(res/g),n-v1-x*(res/g)-v2-y*(res/g));
}

这篇关于Codeforces 1244 C. The Football Season —— 扩展欧几里得的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---