当前位置: 代码迷 >> 综合 >> 【数学】AtCoder Grand Contest 026 rng_10s
  详细解决方案

【数学】AtCoder Grand Contest 026 rng_10s

热度:43   发布时间:2023-09-27 07:18:33.0

题意:

一家商店里有A瓶饮料,有一个老逗逼每天白天都会来到商店,磕B瓶饮料,到了晚上,当商店老板发现店里的饮料少于C瓶时,就会购入D瓶。
现在这个老逗逼想知道能不能无限地嗑下去(即每天都能磕B瓶)。


分析:

首先,有几个显而易见的特判:
1、A&lt;BA &lt; BA<B,那么第一天就不够了
2、D&lt;BD &lt; BD<B,那么无论商店老板怎么补,都补不赢这个老逗逼磕的速度。
3、在上述条件都不满足的情况下,如果C+1≥BC+1\geq BC+1B,那么这个老逗逼永远不可能磕完。

现在考虑一下一般情况。
其实我们无非就是求
C&lt;A?x×B+y×D&lt;BC&lt;A-x\times B+y\times D&lt;BC<A?x×B+y×D<Bx,yx,yx,y是否有解。

移一下项,变成了
A?B&lt;x×B?y×D&lt;A?CA-B&lt;x\times B-y\times D&lt;A-CA?B<x×B?y×D<A?C是否有解。

这时就很简单了,x×B?y×Dx\times B-y\times Dx×B?y×D能够凑出的数必然是gcd(B,D)gcd(B,D)gcd(B,D)的倍数。(学过拓欧的应该都知道)

无非就是求(A?B,A?C)(A-B,A-C)(A?B,A?C)中是否有gcd(B,D)gcd(B,D)gcd(B,D)的倍数。

就是判断?A?C?1gcd(B,D)???A?Bgcd(B,D)?≥0\lfloor \frac {A-C-1} {gcd(B,D)}\rfloor - \lfloor \frac {A-B} {gcd(B,D)}\rfloor \geq 0?gcd(B,D)A?C?1????gcd(B,D)A?B??0而已,满足即可能喝完,不满足则不可能。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define SF scanf
#define PF printf
#define MAXN 100010
using namespace std;
typedef long long ll;
int n;
ll a,b,c,d;
ll gcd(ll x,ll y){if(y==0)return x;return gcd(y,x%y);
}
int main(){SF("%d",&n);while(n--){SF("%lld%lld%lld%lld",&a,&b,&c,&d);if(a<b){PF("No\n");continue;}if(b>d){PF("No\n");continue;}if(c+1>=b){PF("Yes\n");continue;}ll g=gcd(b,d);if((a-c-1ll)/g-(a-b)/g>0)PF("No\n");elsePF("Yes\n");}
} 
  相关解决方案