제출 #1145506

#제출 시각아이디문제언어결과실행 시간메모리
1145506sayaddVepar (COCI21_vepar)C++20
70 / 70
204 ms5976 KiB

#pragma GCC optimize("Ofast")
// #pragma GCC target("popcnt,avx2,fma")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<double> vd;
typedef vector<vector<double>> vvd;
typedef vector<ld> vld;
typedef vector<vector<ld>> vvld;
typedef vector<ull> vull;
typedef vector<vector<ull>> vvull;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef vector<pii> vpii;
typedef vector<vector<pii>> vvp;
typedef vector<pair<ll, ll>> vpll;
typedef vector<vector<pair<ll, ll>>> vvpll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define eb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ff first
#define ss second
#define YES cout << "YES" << endl
#define UwU cout << "Yes" << endl;
#define uWu cout << "No" << endl;
#define NO cout << "NO" << endl;
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define pow(x, y) static_cast<int>(pow(x, y))
#define mt199937_64 mt_rand(chrono::steady_clock::now().time_since_epoch().count())
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
template<typename T> inline T sqr(T x) { return x * x; }
template<typename T> inline T modinv(T a, T mod) { return 0; }
//template<typename T> bool isPrime(T n) { if (n <= 1)return false;if (n <= 3)return true;if (n % 2 == 0 || n % 3 == 0)return false;for (T i = 5;i * i <= n;i += 6)if (n % i == 0 || n % (i + 2) == 0)return false;return true; }
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const long long LINF = 1e18 + 7;
const int MAXN = 1e7+7;
const int LOG = 21;
vi sieve(int n){
    vi primes;
    vb isPrime(n+1,true);
    isPrime[0] = isPrime[1] = false;
    for(int i=2;i<=n;i++){
        if(isPrime[i]){
            primes.pb(i);
            for(ll j=1LL*i*i;j<=n;j+=i){
                isPrime[j] = false;
            }
        }
    }
    return primes;
}
ll lejandr(ll n,int p){
    ll cnt = 0;
    while(n>0){
        n/=p;
        cnt+=n;
    }
    return cnt;
}
signed main(){
    fastio;
    vi primes = sieve(MAXN);
    int t; 
    cin >> t;
    while(t--){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        bool ok = true;
        for(auto p : primes){
            if(p>b){
                break;
            }
            if(lejandr(b,p)-lejandr(a-1,p)>lejandr(d,p)-lejandr(c-1,p)){ 
                    ok = false;
                    break;
            }
        }
        if(ok){
            cout<<"DA"<<endl;
        }
        else{
            cout<<"NE"<<endl;
        }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...