Submission #3024916


Source Code Expand

#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define int long long
using namespace std;

typedef pair<int, int> Pii;

template<typename T>
void readvec(vector<T> &a);
void readindex(vector<int> &a);

int extgcd(int a, int b, int &x, int &y){
    int d = a;
    if(b != 0){
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    }else{
        x = 1;
        y = 0;
    }
    return d;
}

bool ans(int A, int B, int C, int D){
    if(A < B || D < B) return false;
    if(C > B) return true;

    int a = A % B;
    int d = D % B;

    // C < (a + kd) mod B < B とできるならfalse
    if(d == 0){
        if(C < a){
            return false;
        }else{
            return true;
        }
    }
    int x, y;
    int g = extgcd(d, B, x, y);
    int h = (B - 1 - a) / g;
    //(a + kd) mod Bの最大値はa+hg
    if(C < a + h * g){
        return false;
    }else{
        return true;
    }
}

signed main(){

    int T;
    cin >> T;
    int A, B, C, D;
    REP(i, T){
        cin >> A >> B >> C >> D;
        if(ans(A, B, C, D)){
            cout << "Yes" << endl;
        }else{
            cout << "No" << endl;
        }
    }
    
    return 0;
}


template<typename T>
void readvec(vector<T> &a){
    REP(i, a.size()){
        cin >> a[i];
    }
}
void readindex(vector<int> &a){
    REP(i, a.size()){
        cin >> a[i];
        a[i]--;
    }
}

Submission Info

Submission Time
Task B - rng_10s
User sumitacchan
Language C++14 (GCC 5.4.1)
Score 600
Code Size 1560 Byte
Status AC
Exec Time 2 ms
Memory 256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 2
AC × 5
Set Name Test Cases
Sample example_0, example_1
All example_0, example_1, multi_0, multi_1, multi_2
Case Name Status Exec Time Memory
example_0 AC 1 ms 256 KB
example_1 AC 1 ms 256 KB
multi_0 AC 2 ms 256 KB
multi_1 AC 2 ms 256 KB
multi_2 AC 2 ms 256 KB