시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB306269359224.605%

문제

백준 온라인 저지의 신년대회 Hello, BOJ 2022!의 개최일은 2022년 1월 15일이다. 준겸이는 대회가 개최된다는 사실이 기뻐 제목을 뚫어져라 보다가 2022가 무언가 특별하다는 사실을 깨달았다.

그렇다. $2022$를 $5$진법으로 표현하면 ${31042}_{(5)}$로, $5$진법의 각 숫자인 $0$, $1$, $2$, $3$, $4$가 모두 한 번씩 나타난다. 다음에 이런 년도가 오려면 2054년이 되어야 한다.

수 $N$과 진법 $d$가 주어진다. 당신은 수 $N$보다 크면서, $d$진법으로 표현했을 때 $d$진법의 숫자가 모두 정확히 한 번씩 등장하는 가장 작은 수를 찾아야 한다. 단, 수를 표기할 때는 앞에 불필요한 0이 존재해서는 안 된다.

입력

첫 번째 줄에 수 $N$과 진법 $d$가 공백을 사이에 두고 $10$진법으로 주어진다.

출력

첫 번째 줄에 $N$보다 크면서 $d$진법으로 표현했을 때 $d$진법의 숫자가 모두 정확히 한 번씩 등장하는 수 중 가장 작은 것을 $10$진법으로 출력한다.

만약 그런 수가 존재하지 않는다면, 첫 번째 줄에 $-1$을 대신 출력한다.

제한

  • $1 \le N \le 10^9$
  • $2 \le d \le 9$
  • 입력으로 주어지는 모든 수는 정수이고, $10$진법으로 표현되어 있다.

예제 입력 1

2021 5

예제 출력 1

2022

예제 입력 2

2022 5

예제 출력 2

2054

예제 입력 3

13857 6

예제 출력 3

14055

노트

  • 양의 정수 $A$를 $d$진법으로 표현한 결과가 ${a_n a_{n-1} \cdots a_1 a_0}_{(d)}$ 라는 의미는, $A = a_n \times d^n + a_{n-1} \times d^{n-1} + \cdots + a_1 d^1 + a_0 d^0$ 이라는 의미이다. 단, $a_n \neq 0$이다.
    • 예를 들어, $2022 = 3 \times 5^4 + 1 \times 5^3 + 0 \times 5^2 + 4 \times 5^1 + 2 \times 5^0 = 31042_{(5)}$이다.
  • $d$진법의 숫자는 $0$ 이상 $d$ 미만의 숫자를 의미한다.
  • $A$를 $d$진법으로 표현했을 때 $d$진법의 숫자가 모두 정확히 한 번씩 등장한다는 의미는, $A = {a_n a_{n-1} \cdots a_1 a_0}_{(d)}$이라고 썼을 때, $a_n, a_{n-1}, \cdots, a_0$ 에서 $0, 1, \cdots, d-1$이 각각 정확히 한 번씩 등장한다는 의미이다.

출처

Contest > BOJ User Contest > Good Bye, BOJ > Hello, BOJ 2022! A번