#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define clean(a,s) memset((a),0,sizeof((a)[0])*(s))
#define all(x) (x).begin() , (x).end()
#define fi first
#define se second
#define int int
using pii = pair<int,int>;
using ll = long long;
const int maxn = 1e7+5;
const int inf = 2e9;
const int mod = 1e9+7;
int t,a,b,c,d;
int cnt[maxn];
bitset<maxn> composite;
int32_t main () {
//freopen("in","r",stdin); freopen("out","w",stdout);
ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
for(int i=2;i<maxn-2;i++) {
if(composite[i]) continue;
for(ll j=1ll*i*i;j<1ll*maxn-2;j+=i)
composite[j] = true;
}
cin >> t;
while(t--) {
cin >> a >> b >> c >> d;
for(int i=a;i<=b;i++) {
if(!composite[i]) {
cnt[i]++;
continue;
}
int tmp = i;
for(int j=2;1ll*j*j<=tmp;j++)
while(tmp > 1 && tmp % j == 0) {
tmp /= j;
cnt[j]++;
}
if(tmp > 1) cnt[tmp]++;
}
for(int i=c;i<=d;i++) {
if(!composite[i]) {
cnt[i]--;
continue;
}
int tmp = i;
for(int j=2;1ll*j*j<=tmp;j++) {
while(tmp > 1 && tmp % j == 0) {
tmp /= j;
cnt[j]--;
}
}
if(tmp > 1) cnt[tmp]--;
}
int z = max(c,d);
bool f = true;
for(int i=2;i<=z;i++)
if(cnt[i] > 0) {
f = false;
break;
}
cout << (f ? "DA" : "NE") << endl;
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
57 ms |
1644 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
52 ms |
1516 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
52 ms |
1516 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1577 ms |
7472 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1568 ms |
6944 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1587 ms |
7064 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1583 ms |
7276 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |