시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 456 | 105 | 90 | 30.717% |
믿기 힘들겠지만 상근이는 이번 겨울 방학에 달에 갔다 왔다. 방학이 끝나고 다시 학교로 돌아온 상근이는 친구들에게 달나라 사람(Selenites)을 만났던 이야기를 해주었다.
상근이는 달에서 사용하는 수 체계를 주로 설명해주었다. 달에서는 음의 진법을 사용한다.
음의 진법은 사람들이 이해하기는 어렵다. 따라서, 상근이는 달을 여행하는 동안 0과 \(n\)을 포함하는 사이의 수 중에서 \(k\)진법과 \(-k\)진법에서 표현이 같은 수를 모두 외웠다. 상근이가 외운 숫자의 개수를 구하는 프로그램을 작성하시오.
\(x\)의 \(k\)진법 표현은 0 ≤ \(a_i\) < \(\left| k \right| \), \(\sum_{i = 0} ^ {p} {a_i \times k^i} = x\)를 만족하는 수열 \(a_0\),\(a_1\),...,\(a_p\)이다.
첫째 줄에 \(n\)과 \(k\)가 주어진다. (1 ≤ \(n\) ≤ 1015, 2 ≤ \(k\) ≤ 1,000)
첫째 줄에 상근이가 달에서 생활하면서 외운 숫자의 개수를 출력한다.
21 3
9
21 2
8
첫 번째 예제에서 상근이는 0, 1, 2, 9, 10, 11, 18, 19, 20을 외웠다.
19는 3진법과 -3진법에서 19 = 2013 = 201-3 으로 표현이 같다. 하지만, 7은 7 = 213 = 111-3 으로 같지 않다.
두 번째 예제의 경우에는 0, 1, 4, 5, 16, 17, 20, 21을 외우면 된다.
ICPC > Regionals > Northern Eurasia > Northern Eurasia Finals > NEERC 2012 G번