AGC026 B - rng_10s

問題リンク
B - rng_10s

問題概要

初期値がAのとき次の操作が無限に続けられるか判定せよ。

• 値がB以上ならB減らし、その後、値がC以下ならばD増やす。値がB未満ならば終了する。

入力はT個のクエリからなる。

制約

• 1 <= T <= 300
• 1 <= A,B,C,D <= 10¹⁸
• 入力は整数

解法

単純にシミュレートすると各クエリO(10¹⁸)くらいの計算量になってしまうので間に合わない。
まず自明なケースを考えると、

• B > D のとき

毎回D増やしてもBの減少量が大きいので単調減少する。No

• A < B のとき

一回目の操作で終了するので No

• B <= D, B <= C のとき

必ず値がC以上に保たれるので Yes

以上のケースは除けるので B > C, B <= D を仮定する。
操作を無限に続けられるということは現れる値がループしているということである。しかし、途中の値に C < X < B のような X が現れると次の操作が行えない。

一方で、操作後の値の変化量に注目すると -B または D-B なので gcd(B,D) で法をとった値は操作前後で変化しない。つまり何回操作を行っても途中の値Xは A≡X mod gcd(B,D) を満たし、このようなXしか値としてとりえない。

以上より、(C, B)の範囲に A%gcd(B,D) と合同になるような値があればNo、なければYesである。(0以上D以下のA%gcd(B,D)と合同になるような値はすべて取りうるので) これは十分高速に判定できる。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll gcd(ll p, ll q){
    if(p%q == 0)return q;
    else return gcd(q, p%q);
}

int main() {
    int T;
    cin >> T;
    for(int i=0; i<T; i++){
        ll a,b,c,d;
        cin >> a >> b >> c >> d;
        if(b > d || a < b){
            cout << "No" << endl;
            continue;
        }
        if (b <= c){
            cout << "Yes" << endl;
            continue;
        }
        ll g = gcd(b,d);
        if(c%g < a%g || (b-c-1) >= g){
            cout << "No" << endl;
        }
        else{
            cout << "Yes" << endl;
        }
    }
    return 0;
}