시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 3681 | 1887 | 1438 | 51.578% |
여러분은 Q개의 쿼리를 수행해야 합니다. 수행해야 하는 쿼리는 다음과 같습니다.
어떤 수 a를 2의 거듭제곱 꼴로 나타낼 수 있는가?
첫 줄에 Q가 주어집니다. (1 ≤ Q ≤ 106)
두 번째 줄부터 Q+1번째 줄까지 a가 주어집니다. a는 1이상 231-1이하 자연수입니다.
각 쿼리마다, 답이 Yes이면 1을, 그렇지 않으면 0을 출력합니다.
10 1 2 7 4 14 32 33 34 35 36
1 1 0 1 0 1 0 0 0 0
어떤 수 a가 2의 거듭제곱꼴로 나타내어진다고 해 봅시다. 그렇다면, a = 2n (단 n ≥ 0인 정수) 를 만족할 겁니다. 보통, 각 비트별로 검사를 하면서, 켜져 있는 비트의 개수를 알아내는 것도 좋은 방법입니다. 이때에는, 많아봤자 32번 정도 연산을 수행하고, 전체 쿼리가 Q개 있다면, 총 시간 복잡도는 O(32Q)가 됩니다.
그런데, 더 좋은 방법이 없을까요? x (x ≥ 0)를 2진법으로 표현해 볼건데요. x가 홀수인 경우와 짝수인 경우로 나눠 봅시다.
...01
이때 -x는 어떻게 표현이 될까요?
...11
따라서, x&(-x)를 하면 1이 나옵니다. x가 짝수라면 어떨까요?
...10…0
으로 표현이 될 겁니다. 이때 -x는 어떻게 표현이 될까요? 일단 bit 반전 먼저 시켜봅시다.
...01...1
이 되고, 여기에 1을 더한 것이 2의 보수 표현법입니다. 따라서 -x는
...10...0
으로 표현됩니다. 따라서 x&(-x)는 1이 있는 x의 최하위 bit와 관련이 있음을 알 수 있습니다. 예제를 하나 들어봅시다. x=6인 경우 x&(-x)의 값은 어떻게 나올까요?
6 = ...0110
-6 = ...1010
이므로 6&(-6) = 2가 나옵니다.
그러면, a가 2i꼴로 나타내어진다면, 어떤 성질이 있는지를 관찰해 봅시다.
a = 0...010...0
-a = 1...110...0
따라서 (a&(-a)) == a라면 2의 거듭제곱이고, 그렇지 않으면 2의 거듭제곱이 아닙니다.
High School > 선린인터넷고등학교 > 제2회 천하제일 코딩대회 B번