시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 84 | 35 | 22 | 32.353% |
$2$ 이상의 양의 정수 $m$에 대해서, 음이 아닌 정수 집합을 정의역으로 갖는 함수 $f_{m}$을 다음과 같이 정의한다.
$$f_{m}(x) = \begin{cases} 0 & (x = 0) \\ f_{m}{\left(\dfrac{x}{m}\right)} & (x \equiv 0 \pmod {m}) \\ f_{m}{\left(\left\lfloor\dfrac{x}{m}\right\rfloor\right)} + 1 & (x \not\equiv 0 \pmod {m}) \end{cases}$$
양의 정수 $a$, $b$, $m$, $n$이 주어질 때, $a \le k \le b$에서 $f_{m}(k) = n$인 정수 $k$의 개수를 구하여라.
첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다. $(1 \le T \le 50\,000)$
다음 $T$개의 줄에 양의 정수 $a$, $b$, $m$, $n$이 공백으로 구분되어 주어진다. $(1 \le a \le b \le 10^{18};$ $2 \le m \le 10;$ $1 \le n \le 100)$
$T$개의 줄에 걸쳐, 각각의 $a$, $b$, $m$, $n$에 대해 $a \le k \le b$에서 $f_{m}(k) = n$인 정수 $k$의 개수를 출력한다.
3 1 7 2 2 8 12 3 1 7 17 4 2
3 1 8
$f_{2}(1)$부터 $f_{2}(7)$까지의 값은 차례대로 각각 $1$, $1$, $2$, $1$, $2$, $2$, $3$이고, 이 중 값이 $2$인 것은 $f_{2}(3)$, $f_{2}(5)$, $f_{2}(6)$으로 총 3개다.
$f_{3}(8)$부터 $f_{3}(12)$까지의 값은 차례대로 각각 $2$, $1$, $2$, $2$, $2$이고, 이 중 값이 $1$인 것은 $f_{3}(9)$ 1개다.
$f_{4}(7)$부터 $f_{4}(17)$까지의 함숫값 중 값이 $2$인 것은 $f_{4}(7)$, $f_{4}(9)$, $f_{4}(10)$, $f_{4}(11)$, $f_{4}(13)$, $f_{4}(14)$, $f_{4}(15)$, $f_{4}(17)$로 총 8개다.