Submission #1185374

#TimeUsernameProblemLanguageResultExecution timeMemory
1185374Haciyev12Vepar (COCI21_vepar)C++20
0 / 70
1596 ms28744 KiB
#include "bits/stdc++.h" #define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define ll long long #define pb push_back #define in insert #define F first #define S second #define vll vector<ll> #define all(v) v.begin(),v.end() #define rep(a, b, c) for (int(a) = (b); (a) < (c); (a)++)//i, 0, n #define endl '\n' #define pii pair<ll,ll> #define yes cout << "Yes" << endl; #define no cout << "No" << endl; using namespace std; const ll INF = 1e18, mod = 1e9 + 7, N = 1e7 + 1; ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); } ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; } ll modpow(ll a, ll b){ ll ans = 1; while(b > 0){ if(b % 2 == 1){ ans *= a; ans = ans%mod; } a *= a; a %= mod; b = b >> 1; } return ans % mod; } ll inv(ll a){ return (modpow(a,mod-2)) % mod; } vector<bool>p(N, false); vll prime; void sieve(){ p[2] = true; for(int i = 3; i < N; i+= 2){ p[i] = true; } for(int i = 3; (i * i) < N ; i+= 2){ if(p[i]){ for(int j = (i * i); j < N; j += (2 * i)){ p[j] = false; } } } prime.pb(2); for(int i = 3; i < N; i += 2){ if(p[i]){ prime.pb(i); } } } vector<long long> divis(long long n) { vector<long long> factorization; for (long long d : prime) { if (d * d > n) break; while (n % d == 0) { factorization.push_back(d); n /= d; } } if (n > 1) factorization.push_back(n); return factorization; } void solve(){ // cout << prime.size() << endl; ll a,b,c,d; cin >> a >> b >> c >> d; map<ll,ll>mp; map<ll,ll>mp1; //2+, 3+ , 2++ , 5+ //7+ 2+++, 3++ for(int i = a; i <= b; i++){ for(auto j :divis(i) ){ mp[j]++; } } for(int i = c; i <= d; i++){ for(auto j :divis(i) ){ mp1[j]++; } } vector<pii>v; vector<pii>v1; for(auto i : mp){ v.pb({i.F, i.S}); } for(auto i : mp1){ v1.pb({i.F, i.S}); } bool t = false; ll cnt = 0; for(int i = 0; i < min(v.size(), v1.size()); i++){ if(v[i].F == v1[i].F && v1[i].S < v[i].S){ cout << "NE" << endl; return; } else if (v[i].F == v1[i].F && v1[i].S >= v[i].S){ t = true; } else if(v[i].F != v1[i].F){ cout << "NE" << endl; return; } } // cout << v.size() << " " << v1.size() << endl; // cout << cnt << endl; if(max(v.size(), v1.size()) == v.size()){ for(int i = min(v.size(), v1.size()); i < max(v.size(), v1.size()); i++){ cnt++; } } // cout << cnt << endl; if(t && cnt == 0){ cout << "DA" << endl; return; } cout << "NE" << endl; } int main() { fast; sieve(); ll t = 1; cin >> t; while (t--) { solve(); } }
#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...