Radio
레이팅 미적용의견: 0
In Croatia there are \(n\) radio stations.
Each station has a concession on one of \(n\)
frequencies denoted by positive integers from 1 to \(n\). The frequencies were not chosen
ideally so sometimes noise appears when multiple stations are broadcasting at the same
time. To be more precise, if two radio stations, with frequencies \(a\) and \(b\) respectively, are
broadcasting at the same time, noise will appear if \(a\) and \(b\) are not relatively prime. The
listeners, of course, do not like the noise, so when they hear it they switch to another
station.
To solve this noise problem, the radio station owners are asking you to write a program which simulates
the actions of the radio stations. Your program needs to support two types of queries:
1. \(S\) \(x\): If not currently broadcasting, the station with frequency \(x\) starts broadcasting, and if it is
already broadcasting, it stops.
2. \(C\) \(l\) \(r\): Check if there exists a pair of broadcasting stations whose frequencies \(a\) and \(b\) are from the
interval [l, r] and such that gcd(a, b)̸ = 1. If such a pair exists, print DA, otherwise print NE.
Initially, no station is broadcasting.
Subtask 1 (10 points): \(1 \le n \le 100\), \(1 \le q \le 200\)
Subtask 2 (30 points): For all queries of the second type it holds that \(l = 1\) i \(r = n\).
Subtask 3 (70 points): No additional constraints.
The first line contains positive integers \(n\) and \(q\) (\(1 \le n \le 1\,000\,000\), \(1 \le q \le 200\,000\)), the number of
radio stations (and frequencies), and the number of queries, respectively.
The \(i-th\) of the next \(q\) lines contains a description of the \(i-th\) query. For queries of the first type it will
hold that \(1 \le x \le n\), and for queries of the second type it will hold that \(1 \le l \le r \le n\).
Print the answers to the queries of the second type in order, in separate lines.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 10점 | \(1 \le n \le 100\), \(1 \le q \le 200\) |
2 | 30점 | For all queries of the second type it holds that \(l = 1\) i \(r = n\). |
3 | 70점 | No additional constraints. |
6 8
S 1
S 2
S 3
C 1 6
S 6
C 1 6
S 2
C 1 6
NE
DA
DA
11 6
S 4
S 10
C 3 11
C 2 7
S 6
C 2 7
DA
NE
DA
20 7
S 10
S 15
S 3
C 10 15
S 10
C 3 15
C 3 10
DA
DA
NE
평가 및 의견
Radio
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Radio