두 진법의 자릿수 합

시간 제한2초메모리 제한512 MB

요약

n, a, b가 주어질 때, a진법과 b진법에서 자릿수의 합이 같은 n보다 큰 최소 정수 m을 구한다.

문제

세 정수 $n$ , $a$ , $b$ 가 주어진다. $m$ 을 $a$ 진법으로 적었을 때 각 자리 숫자의 합과 $b$ 진법으로 적었을 때 각 자리 숫자의 합이 같아지는, $n$ 보다 큰 가장 작은 정수 $m$ 을 구한다.

입력은 테스트 케이스 하나로 이루어진다. 첫 줄에 정수 $n$ , $a$ , $b$ 가 공백으로 구분되어 주어진다. $0 \le n \le 10^{16}$ 이고 $2 \le a < b \le 36$ 이다. 세 수 모두 10진법으로 주어진다.

$n$ 보다 큰 정수 중에서 $a$ 진법 자리 합과 $b$ 진법 자리 합이 같은 가장 작은 정수 $m$ 을 10진법으로 한 줄에 출력한다. $m$ 은 $10^{16}$ 보다 클 수 있다.