시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB27215011858.128%

문제

양의 정수 nk가 주어진다. nk진수로 변환한 수를 a라고 하자. a의 각 자릿수를 0을 기준으로 나눈 결과를 집합 b라고 하자. 0이 연속으로 나와서 공백이 생기는 경우는 집합 b에 포함되지 않는다. 집합 b에 있는 수의 합을 k진수로 출력하자. 예를 들어, n = 19, k = 2이면 a = 100112, b = {1, 11}, 1 + 11 = 12, 12 = 11002이므로 1100을 출력한다.

입력

첫 번째 줄에 양의 정수 nk가 공백을 사이에 두고 순서대로 주어진다.

출력

첫 번째 줄에 집합 b에 있는 수의 합을 k진수로 출력한다.

제한

  • 1 ≤ n ≤ 1,000,000
  • 2 ≤ k ≤ 10

예제 입력 1

437674 3

예제 출력 1

22101

437674를 3진수 변환하면 a = 2110201010113이다.

2110201010113을 0을 기준으로 나누면 b = {211, 2, 1, 1, 11}이다.

b에 있는 수의 합은 211 + 2 + 1 + 1 + 11 = 226이다.

226을 3진수로 변환하면 221013이다.

예제 입력 2

29 3

예제 출력 2

10

29를 3진수 변환하면 a = 10023이다.

1002를 0을 기준으로 나누면 b = {1, 2}이다.

b에 있는 수의 합은 1 + 2 = 3이다.

3을 3진수로 변환하면 103이다.

예제 입력 3

11 3

예제 출력 3

10

11을 3진수 변환하면 a = 1023이다.

102를 0을 기준으로 나누면 b = {1, 2}이다.

b에 있는 수의 합은 1 + 2 = 3이다.

3을 3진수로 변환하면 103이다.

예제 입력 4

3 3

예제 출력 4

1

3을 3진수로 변환하면 a = 103이다.

10을 0을 기준으로 나누면 b = {1}이다.

b에 있는 수의 합은 1이다.

1을 3진수로 변환하면 13이다.

출처