这一题一眼 $exgcd$
怎么看都是 $exgcd$
考虑一下 $exgcd$ 怎么做这一题
考虑求出 $wx+dy=p$ 的解，并且要尽量满足 $x+y+z=n$
那么就是要求出一组解 $x,y$ 使得 $x+y$ 尽量小
因为 $d<w$ ，所以对于 $wx+dy=p$
当 $y$ 取最小正整数解的时候的 $x+y$ 一定是最小的
然后就可以用 $exgcd$ 求出最小的 $y$ ，然后再通过 $y$ 得到 $x$
然后 $ ext {Wrong answer on test 5}$ ....
比赛结束以后发现爆 $lnog long$ 了
所以需要比较优美的写法，当求出一组 $x,y$ 满足 $wx+dy=gcd(w,d)$ 以后
我们不能直接 $y=y*(p/gcd(w,d))$ 然后再 $mod=w/gcd(w,d),y=(y \% mod + mod) \% mod$
而是应该直接 $mod=w/gcd(w,d) ,y= ( (y \% mod * (p/gcd(w,d)) \%mod ) \%mod + mod ) \% mod$
然后因为 $w,d<=10^5$ ，就不会爆了
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef long long ll; inline ll read() { ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } ll n,p,w,d; ll exgcd(ll a,ll b,ll &x,ll &y) { if(!b) { x=1,y=0; return a; } ll g=exgcd(b,a%b,x,y); ll t=x; x=y; y=t-a/b*y; return g; } int main() { n=read(),p=read(),w=read(),d=read(); ll x,y,g=exgcd(w,d,x,y); if(p%g) { printf("-1 "); return 0; } ll mo=w/g; y=((y%mo)*((p/g)%mo)%mo+mo)%mo; x=(p-y*d)/w; if((x+y>n) || (x<0)) printf("-1 "); else printf("%lld %lld %lld ",x,y,n-x-y); return 0; }
事实上因为 $w,d<=10^5$ ，我们完全可以暴力从小到大枚举 $y in [0,w)$ 并判断是否存在合法的 $x$
一旦存在即找到最小的 $y$
注意到判断的式子为 $p-dy = 0 mod w$ ，注意到 $p-dy mod w$ 的循环节长度也在 $w$ 以内
所以如果枚举完 $y in [0,w)$ 以后还是无解那么就一定无解了
由于 $w<=10^5$，所以暴力即可，代码来自 ：jiangly
#include <bits/stdc++.h> using namespace std; using LL = long long; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); LL n, p, d, w; cin >> n >> p >> d >> w; LL y = 0; while (y < d && (p - w * y) % d != 0) ++y; if (y < d) { LL x = (p - w * y) / d; LL z = n - x - y; if (x >= 0 && z >= 0) cout << x << " " << y << " " << z << " "; else cout << "-1 "; } else cout << "-1 "; return 0; }