• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

Codeforces1244C.TheFootballSeason

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

传送门

这一题一眼 $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;
}
exgcd做法

 

事实上因为 $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;
}
暴力

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
C#WINFORM运行简单JS带返回值给c#发布时间:2022-07-13
下一篇:
c语言中不同进制数的表示发布时间:2022-07-13
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap