[数论] AtCoder Grand Contest 026 B - rng_10s

貌似学到了新姿势。

对于这题,改特判的先特判掉,剩下 \(D>B\) 的情况。

应该是求是否存在 $ (A+Dx)\text{ % }B >C$ ,怎么算呢..... \[ \Leftrightarrow B>A+Dx-Py>C \\ \Leftrightarrow B-A>Dx-Py>C-A \] \(Dx-Py\) 的取值应该是所有 \(gcd(D,P)\) 的倍数,是裴蜀定理。

所以只需判下这个范围内是否有倍数就行了。

意味收获是发现现在我能求 \((r+kx)\text{ % }B\) 这种东西的最大最小值了。

比如 \((r+kx)\text{ % }B \le C\) ,然后 \(kx - By \le C -r\) ,算一下就好了。

裴蜀定理真是一切的基础啊.....

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
int _test;
LL A,B,C,D;
LL gcd(LL a,LL b){ return b?gcd(b,a%b):a; }
int main(){
freopen("agc026B.in","r",stdin);
freopen("agc026B.out","w",stdout);
scanf("%d",&_test);
while(_test--){
scanf("%lld%lld%lld%lld",&A,&B,&C,&D);
if(A>C) A=(A-C-1)%B+C+1;
if(A<B||D<B) puts("No"); else{
A%=B; D%=B; LL d=gcd(B,D);
if((C-A)/d<(B-A-1)/d) puts("No"); else puts("Yes");
}
}
return 0;
}