Submission #3045994

---

Source Code Expand

#include <algorithm>
#include <array>
#include <bitset>
#include <iostream>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

#include <cassert>
using namespace std;

long long GetGcd(long long a, long long b)
{
    while (a > 0 && b > 0) {
        if (a >= b) {
            a %= b;
        } else {
            b %= a;
        }
    }
    return a + b;
}

long long Ceil(long long num, long long den)
{
    return (num + den - 1) / den;
}

long long Floor(long long num, long long den)
{
    return num / den;
}

struct TSolver
{
    long long A;
    long long B;
    long long C;
    long long D;

    void Setup()
    {
        cin >> A >> B >> C >> D;
    }

    void Solve()
    {
        if (A < B) {
            Show(false);
            return;
        }

        if (D < B) {
            Show(false);
            return;
        }

        if (B > C + 1) {
            auto x = A % B;
            auto d = D % B;

            bool existsK = false;

            if (C >= x) {
                existsK |= ExistsK(d, B, C - x + 1, B - x - 1);
            } else {
                existsK |= ExistsK(d, B, 0, B - x - 1);
                existsK |= ExistsK(d, B, (C - x + B) % B, B - 1);
            }

            if (existsK) {
                Show(false);
            } else {
                Show(true);
            }
        } else {
            Show(true);
        }
    }

    static bool ExistsK(long long d, long long b, long long l, long long r)
    {
        // Returns |true| if and only if exists k >= 0: k * d \in [l, r] (mod b).
        assert(0 <= l && l <= r);
        assert(r < b);
        assert(0 <= d && d < b);
        auto g = GetGcd(d, b);
        d /= g;
        b /= g;
        l = Ceil(l, g);
        r = Floor(r, g);
        return l <= r;
    }

    void Show(bool indefinite)
    {
        if (indefinite) {
            cout << "Yes" << '\n';
        } else {
            cout << "No" << '\n';
        }
    }

    void TearDown()
    {
        cout.flush();
    }
};

int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    TSolver solver;
    int testCount;
    cin >> testCount;
    for (int i = 0; i < testCount; ++i) {
        solver.Setup();
        solver.Solve();
        solver.TearDown();
    }

    return 0;
}

Submission Info

Judge Result