진법 알아내기
시간 제한1초메모리 제한128 MB
덧셈과 곱셈, 숫자로 이루어진 식이 주어질 때 양변이 같은 값이 되는 모든 진법 B를 구한다.
문제
과 를 곱하면 얼마일까? 정답은 이다. 라고 생각했다면 잠시 쉬었다가 다시 풀어 보길 권한다. 는 진법으로 계산한 결과이기 때문이다.
이상의 정수 에 대하여, 진법의 각 자리 숫자는 이상 이하의 정수이다. 진법 수를 읽을 때는 가장 오른쪽 자리에 을, 오른쪽에서 두 번째 자리에 를, 세 번째 자리에 을 곱하는 식으로 왼쪽으로 갈수록 의 거듭제곱을 곱해 모두 더한다.
어떤 등식은 사용한 진법에 따라 참이 되기도 하고 거짓이 되기도 한다. 예를 들어 는 일 때 항상 참이다. 진법에서는 숫자 를 쓸 수 없으므로 이어야 한다. 반면 처럼 어떤 진법을 써도 참이 될 수 없는 등식도 있다.
등식이 주어졌을 때, 어떤 진법에서 그 등식이 참이 되는지 구하는 프로그램을 작성하시오.
입력
입력의 각 줄은 하나의 테스트 케이스이며 EXPR=EXPR 형태이다. EXPR는 길이가 을 넘지 않는 수식이다.
모든 수식은 항상 올바르며 +, *, 그리고 숫자 0부터 9까지로만 이루어져 있다. 수식이 +로 시작하는 경우는 없고, 수 앞에 불필요한 이 붙는 경우도 없다.
입력의 마지막 줄에는 = 한 글자만 주어진다.
출력
각 테스트 케이스마다 주어진 등식을 참으로 만드는 진법을 출력한다.
등식을 참으로 만드는 진법이 무한히 많은 경우에는 B+를 출력한다. 이때 는 등식을 참으로 만드는 가장 작은 진법이다.
진법이 유한개인 경우에는 그 진법들을 오름차순으로 공백으로 구분하여 출력한다.
어떤 진법에서도 등식이 참이 되지 않으면 *를 출력한다.