Submission #1166810

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166810		sunflower	Vepar (COCI21_vepar)	C++17	70 / 70	93 ms	14436 KiB

Main

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

#define ll long long
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define SZ(x) ((int) (x).size())
#define ALL(a) (a).begin(), (a).end()
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(x) cerr << "[" << #x << " = " << (x) << "]" << endl

#define left    __left
#define right   __right
#define prev    __prev
#define fi      first
#define se      second

template <class X, class Y>
    bool maximize(X &x, Y y) {
        if (x < y) return x = y, true;
        else return false;
    }

template <class X, class Y>
    bool minimize(X &x, Y y) {
        if (x > y) return x = y, true;
        else return false;
    }

int t;

#define MAX_N 10'000'100
bool isPrime[MAX_N + 2];

vector <int> primes;

void sieve() {
    memset(isPrime, true, sizeof(isPrime));
    isPrime[0] = isPrime[1] = false;
    FOR(i, 2, trunc(sqrt(MAX_N)))
        if (isPrime[i])
            FOR(j, i, MAX_N / i)
                isPrime[i * j] = false;

    FOR(i, 2, MAX_N) if (isPrime[i]) primes.push_back(i);
}

// legendary formula;
int get(int n, int value) {
    int ans = 0;
    for (ll i = value; i <= n; i *= value) {
        ans += n / i;
    }

    return ans;
}

int cal(int l, int r, int value) {
    return get(r, value) - get(l - 1, value);
}

int main() {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    // freopen("test.inp","r",stdin);
    // freopen("test.out","w",stdout);

    sieve();

    cin >> t;
    while (t--) {
        int L, R, X, Y;
        cin >> L >> R >> X >> Y;

        bool ok = true;
        for (int i : primes) {
            if (i > max(R, Y)) break;
            ok &= (cal(L, R, i) <= cal(X, Y, i));
            if (!ok) break;
        }

        cout << (ok ? "DA\n" : "NE\n");
    }

    return 0;
}

/* Discipline - Calm */

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10