客服电话
APP下载
迪恩网络APP
随时随地掌握行业动态
官方微信
扫描二维码
关注迪恩网络微信公众号
|
这一题一眼 $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$ 然后 $\text {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\n"); 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\n"); else printf("%lld %lld %lld\n",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 << "\n"; else cout << "-1\n"; } else cout << "-1\n"; return 0; }
|
2023-10-27
2022-08-15
2022-08-17
2022-09-23
2022-08-13
六六分期app的软件客服如何联系？不知道吗？加qq群【895510560】即可！标题：六六分期
今天小编告诉大家如何处理win10系统火狐flash插件总是崩溃的问题，可能很多用户都不知
今天小编告诉大家如何对win10系统删除桌面回收站图标进行设置，可能很多用户都不知道
今天小编告诉大家如何对win10系统电脑设置节能降温的设置方法，想必大家都遇到过需要
我们在使用xp系统的过程中,经常需要对xp系统无线网络安装向导设置进行设置，可能很多
今天小编告诉大家如何处理win7系统玩cf老是与主机连接不稳定的问题，可能很多用户都不
电脑对日常生活的重要性小编就不多说了，可是一旦碰到win7系统设置cf烟雾头的问题，很
我们在日常使用电脑的时候，有的小伙伴们可能在打开应用的时候会遇见提示应用程序无法
今天小编告诉大家如何对win7系统打开vcf文件进行设置，可能很多用户都不知道怎么对win
今天小编告诉大家如何对win10系统s4开启USB调试模式进行设置，可能很多用户都不知道怎
请发表评论