역사 속의 수학

Numeristan의 역사는 상당히 흥미롭다. 잘 알려져 있듯이 Numeristan의 마하라자들은 미신을 많이 믿었다. 해마다 그들은 수석 마법사에게 행운의 숫자를 물었고, 그해의 모든 계산은 이 행운의 숫자를 밑으로 하는 위치 기수법1로 해야 했다. 당연히 세월이 흐르면서 혼란이 많았다. 반대로, 이 덕분에 역사가들은 고문서의 연도를 아주 쉽게 알아낼 수 있게 되었다.

최근 두 수의 단순한 곱셈만 적힌 오래된 필사본이 발견되었다. 연도에 대한 다른 단서가 없어, 몇몇 역사가가 계산이 이루어진 기수법의 밑을 알아내는 데 도움을 청했다.

1밑이 b인 위치 기수법에는 숫자 0, 1, ..., b - 1만 들어 있다. 정수 n은 하나 이상의 숫자 di로 이루어진다. 각 숫자는 위치 i와 자신의 값에 따라 n = Σdi · bi (i = 0부터 ∞까지)라는 공식으로 n의 전체 값에 기여한다. 값이 0인 앞쪽 숫자는 보통 생략한다. 예를 들어 밑이 13일 때 정수 512의 전체 값은 5 · 132 + 1 · 131 + 2 · 130이다. 잘 알려져 쓰이는 위치 기수법으로는 이진법(유효한 밑이 가장 작은 위치 기수법이기도 하다), 십진법, 십육진법이 있다.

입력은 세 줄로 이루어지고, 각 줄은 앞에 0이 없는 양의 정수 하나를 나타낸다. 각 줄은 다음과 같다.

• 정수 n (1 ≤ n ≤ 1 000): 현재 설명하는 정수의 자릿수.
• n개의 정수 dn−1, ..., d0 (각 i에 대해 0 ≤ di ≤ 230, dn−1 ≠ 0): 정수의 숫자. 가장 큰 자릿수는 dn−1이고 가장 작은 자릿수는 d0이다.

처음 두 줄은 곱하는 두 수이고, 세 번째 줄은 곱셈의 결과이다.

곱셈이 이루어진 가능한 밑을 하나 출력한다. 가능한 밑이 여러 개라면 아무거나 출력해도 된다. 가능한 밑이 없으면 impossible을 출력한다.