제출 #1172674

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1172674		karen671	Vepar (COCI21_vepar)	C++20	70 / 70	120 ms	9960 KiB

Main

#include <cmath>
#include <cstdint>
#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

const ll lim = 1e7 + 42;
vector<bool> isComposite;
vector<ll> primes;

void prepare() {
    isComposite.resize(1e7 + 42);

    for (ll i = 2; i < lim; i++) {
        if (!isComposite[i]) {
            primes.push_back(i);
            for (ll j = i * i; j < lim; j += i) {
                isComposite[j] = true;
            }
        }
    }
}

ll count1(ll x, ll a) {
    ll count = 0;
    ll temp = x;

    while (temp <= a) {
        count += a / temp;
        temp *= x;
    }
    return count;
}

ll count2(ll x, ll a, ll b) {
    return count1(x, b) - count1(x, a - 1);
}

void solve(){
    ll a, b, c, d;
    cin >> a >> b >> c >> d;

    for (const auto& x: primes) {
        if (count2(x, c, d) < count2(x, a, b)) {
            cout << "NE\n";
            return;
        }
    }
    cout << "DA\n" << std::endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    prepare();

    int t = 0;
    cin >> t;

    for (int i = 0; i < t; ++i) {
        solve();
    }
    return 0;
}

• 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