题解 [AGC026B] rng_10s
cjh20090318
·
·
题解
多校联考考这个题，然后因为大样例给的太水了很多人因此挂分。
题意
当 A \ge B 时，A \gets A - B，如果此时 A \le C，A \gets A + D。
请问能否无限循环执行下去。
分析
首先分析几个比较容易判断的条件。
$D < B$ 时即使进入了循环也没有用，因为即使能加也不能使 $A$ 回到原来的水平。
对于剩下的情况，此时已经保证了 $A \ge B$，$D \ge B$。
一种显然会无限循环的情况是 $C \ge B-1$，因为当 $A < B$ 时必然满足 $A \le C$ 的情况，且 $D \ge B$，所以一定又会将 $A$ 加回 $A \ge B$ 的状态。
剩下的情况是绝对无解或有解的吗？并不是。
如果我们可以找到一个非负整数 $k$ 使得 $( a + k(d-b) ) \bmod b > c$，也就是说经过一定的操作后 $C < A < B$，那么就不能继续循环了。
将上面那个式子转化为同余方程 $kd \equiv x - a \pmod{b}$，需要找到一个 $x \in (c,b)$ 使得该同余方程有解。
根据裴蜀定理，同余方程有解的条件是 $\gcd(b,d) \mid (x-a)$，于是我们直接求最大的 $x$ 即可。
单次时间复杂度 $O(\log n)$。
## 代码
```cpp
//the code is from chenjh
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
LL a,b,c,d;
void solve(){
scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
if(d<b||a<b) puts("No");
else{
if(c>=b-1) puts("Yes");
else{
LL g=__gcd(d,b);
a%=b;
LL x=(b-1-a)/g*g;
puts((a+x)%b>c?"No":"Yes");
}
}
}
int main(){
int T;scanf("%d",&T);
while(T--) solve();
return 0;
}
```