AtCoder AGC #026 : B - rng_10s

AtCoderのうちARC/AGCの記事、３か月位書いてなかったらしい。
https://beta.atcoder.jp/contests/agc026/tasks/agc026_b

問題

初期状態で店にA個のジュースがある。
毎日B個のジュースが買われていく。
毎晩店に残ったジュースがC個以下ならD個補充される。

永遠にジュースをB個買えるか判定せよ。

解法

まず明らかなケースを処理する。

• A＜Bだったり、D＜Bのケースは明らかに永遠に買うことはできない。
• そうでない場合、かつC≧B-1なら、常に補充が間に合うので永遠に買うことができる。

残りは、A≧B、D≧B、C＜B-1の場合である。
ジュースの残数が[C+1,B-1]の範囲になってしまうと、その日B個ジュースを変えないことになる。
これは言い換えると、
(A + D*x)%Bが[C+1, B-1]の範囲に入ることがあるかを判定すればよい。
式変形するとD*x が(mod Bにおいて) [(C+1)-A, (B-1)-A]の範囲に入るか判定することになる。
D*xの取る範囲は、結局gcd(D,B)の倍数なので、[(C+1)-A, (B-1)-A]の範囲にgcd(D,B)の倍数が含まれるかを調べるとよい。

int T;
ll A,B,C,D;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>A>>B>>C>>D;
		
		if(D<B || A<B) {
			cout<<"No"<<endl;
			continue;
		}
		if(C>=B-1) {
			cout<<"Yes"<<endl;
			continue;
		}
		
		D=__gcd(D,B);
		ll L=(((C+1)-A)%B+B)%B;
		ll R=(((B-1)-A)%B+B)%B;
		if(R>=L) {
			if(L/D == R/D && L%D) {
				cout<<"Yes"<<endl;
			}
			else {
				cout<<"No"<<endl;
			}
		}
		else {
			cout<<"No"<<endl;
		}
		
		
	}
}

まとめ

10sはジュースなんだろうなと気が付いたけど、英語版見てる人はタイトルの意味わからなさそう。