시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 145 | 64 | 52 | 52.525% |
양의 정수 $A$에 대해 $A$보다 큰 $2$의 제곱수 중 가장 작은 값을 $P$라고 할 때, $B = A \oplus (P-1)$라고 하자.
이 때, 양의 정수 $K$에 대해 $A \geq B \times (2^K-1)$일 경우 $A$를 압도적 XOR 수라고 한다.
$N$과 $K$가 주어지면 $1$부터 $N$까지의 정수 중 압도적 XOR 수의 개수를 구해보자.
첫 번째 줄에 $N, K$가 공백으로 구분되어 주어진다. $(1 \leq N \leq 10^{15}, 1 \leq K \leq 50)$
$1$부터 $N$까지의 압도적 XOR 수의 개수를 출력한다.
243 4
22
243 7
7
1000000000000000 2
437050046578689
$a$와 $b$의 bitwise XOR인 $a \oplus b$는 2진법으로 표현했을 때 $a$와 $b$의 $i$번째 자리가 같으면 $a \oplus b$의 $i$번째 자리가 $0$이고, 서로 다르면 $1$이 되도록 계산한다.
두 번째 입력에서 압도적 XOR 수는 $1, 3, 7, 15, 31, 63, 127$로 총 $7$개이다.