题意:
一家商店里有A瓶饮料,有一个老逗逼每天白天都会来到商店,磕B瓶饮料,到了晚上,当商店老板发现店里的饮料少于C瓶时,就会购入D瓶。
现在这个老逗逼想知道能不能无限地嗑下去(即每天都能磕B瓶)。
分析:
首先,有几个显而易见的特判:
1、A<BA < BA<B,那么第一天就不够了
2、D<BD < BD<B,那么无论商店老板怎么补,都补不赢这个老逗逼磕的速度。
3、在上述条件都不满足的情况下,如果C+1≥BC+1\geq BC+1≥B,那么这个老逗逼永远不可能磕完。
现在考虑一下一般情况。
其实我们无非就是求
C<A?x×B+y×D<BC<A-x\times B+y\times D<BC<A?x×B+y×D<B中x,yx,yx,y是否有解。
移一下项,变成了
A?B<x×B?y×D<A?CA-B<x\times B-y\times D<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");}
}