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

문제

6과 9를 곱하면 몇이 될까? 정답은 42이다. 54로 생각했다면, 잠시 쉬었다가 문제를 푸는 것을 권장한다. 그 이유는 42는 13진법으로 계산했을 때 결과이기 때문이다.

2보다 크거나 같은 정수 B에 대해서, B진법의 모든 자리수는 0보다 크거나 같고, B-1보다 작거나 같은 정수이다. B진법 수를 읽으려면 가장 오른쪽 자리에 1을 곱하고, 두 번째 오른쪽 자리에 B를 곱하고, 세 번째 오른쪽 자리에 B2를 곱하고, ... 이와 같은 식으로 계속 곱해야 한다.

일부 등식은 어떤 진법을 사용했냐에 따라서 참과 거짓이 결정된다. 예를 들어, 2+2=4의 경우에 B≥5이면 항상 참이다. 4진법에는 4를 자리로 사용할 수 없기 때문에 B≥5이다. 하지만, 2+2=5와 같은 등식은 어떤 진법을 사용해도 참이 될 수 없다.

등식이 주어졌을 때, 어떤 진법을 사용하면 참이 되는지 구하는 프로그램을 작성하시오. 

입력

입력의 각 줄은 테스트 케이스 하나를 나타내며, 각 테스트 케이스는 "EXPR=EXPR"과 같은 형태이다. EXPR는 17자리를 넘지 않는 수식이다.

모든 수식은 항상 올바르며, '+', '*'와 '0'-'9'까지 숫자로 이루어져 있다. 수식이 '+'기호로 시작하는 경우는 없으며, 수의 앞에 불필요한 0이 붙어있는 경우도 없다.

입력의 마지막 줄에는 '='이 주어진다.

출력

각 테스트 케이스마다 어떤 진법을 사용하면 입력으로 주어진 등식이 참이 되는지 출력한다.

등식을 참으로 만드는 진법이 무한대인 경우에는 "B+"를 출력한다. 여기서 B는 등식을 참으로 만드는 가장 작은 진법이다.

진법의 수가 유한개인 경우에는 진법을 오름차순으로 공백으로 구분하여 출력한다.

어떤 진법을 사용해도 등식이 참이 되지 않는 경우에는 '*'을 출력한다.

예제 입력 1

6*9=42
10000+3*5*334=3*5000+10+0
2+2=3
2+2=4
0*0=0
=

예제 출력 1

13
6 10
*
5+
2+
W3sicHJvYmxlbV9pZCI6IjU3MjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM5YzRcdWJjOTUgXHVjNTRjXHVjNTQ0XHViMGI0XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD42XHVhY2ZjIDlcdWI5N2MgXHVhY2YxXHVkNTU4XHViYTc0IFx1YmE4N1x1Yzc3NCBcdWI0MjBcdWFlNGM/IFx1YzgxNVx1YjJmNVx1Yzc0MCA0Mlx1Yzc3NFx1YjJlNC4gNTRcdWI4NWMgXHVjMGRkXHVhYzAxXHVkNTg4XHViMmU0XHViYTc0LCBcdWM3YTBcdWMyZGMgXHVjMjZjXHVjNWM4XHViMmU0XHVhYzAwIFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWQ0NzhcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YWQ4Y1x1YzdhNVx1ZDU1Y1x1YjJlNC4gXHVhZGY4IFx1Yzc3NFx1YzcyMFx1YjI5NCA0Mlx1YjI5NCAxM1x1YzljNFx1YmM5NVx1YzczY1x1Yjg1YyBcdWFjYzRcdWMwYjBcdWQ1ODhcdWM3NDQgXHViNTRjIFx1YWNiMFx1YWNmY1x1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjJcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM4MTVcdWMyMTggQlx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIEJcdWM5YzRcdWJjOTVcdWM3NTggXHViYWE4XHViNGUwIFx1Yzc5MFx1YjlhY1x1YzIxOFx1YjI5NCAwXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIEItMVx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC4gQlx1YzljNFx1YmM5NSBcdWMyMThcdWI5N2MgXHVjNzdkXHVjNzNjXHViODI0XHViYTc0IFx1YWMwMFx1YzdhNSBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjNzkwXHViOWFjXHVjNWQwIDFcdWM3NDQgXHVhY2YxXHVkNTU4XHVhY2UwLCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWM3OTBcdWI5YWNcdWM1ZDAgQlx1Yjk3YyBcdWFjZjFcdWQ1NThcdWFjZTAsIFx1YzEzOCBcdWJjODhcdWM5ZjggXHVjNjI0XHViOTc4XHVjYWJkIFx1Yzc5MFx1YjlhY1x1YzVkMCBCPHN1cD4yPFwvc3VwPlx1Yjk3YyBcdWFjZjFcdWQ1NThcdWFjZTAsIC4uLiBcdWM3NzRcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YzJkZFx1YzczY1x1Yjg1YyBcdWFjYzRcdWMxOGQgXHVhY2YxXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzdjXHViZDgwIFx1YjRmMVx1YzJkZFx1Yzc0MCBcdWM1YjRcdWI1YTQgXHVjOWM0XHViYzk1XHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU4OFx1YjBkMFx1YzVkMCBcdWI1MzBcdWI3N2NcdWMxMWMgXHVjYzM4XHVhY2ZjIFx1YWM3MFx1YzlkM1x1Yzc3NCZuYnNwO1x1YWNiMFx1YzgxNVx1YjQxY1x1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgMisyPTRcdWM3NTggXHVhY2JkXHVjNmIwXHVjNWQwIEImZ2U7NVx1Yzc3NFx1YmE3NCBcdWQ1NmRcdWMwYzEgXHVjYzM4XHVjNzc0XHViMmU0LiA0XHVjOWM0XHViYzk1XHVjNWQwXHViMjk0IDRcdWI5N2MgXHVjNzkwXHViOWFjXHViODVjIFx1YzBhY1x1YzZhOVx1ZDU2MCBcdWMyMTggXHVjNWM2XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBCJmdlOzVcdWM3NzRcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgMisyPTVcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YjRmMVx1YzJkZFx1Yzc0MCBcdWM1YjRcdWI1YTQgXHVjOWM0XHViYzk1XHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU3NFx1YjNjNCBcdWNjMzhcdWM3NzQgXHViNDIwIFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjRmMVx1YzJkZFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM1YjRcdWI1YTQgXHVjOWM0XHViYzk1XHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU1OFx1YmE3NCBcdWNjMzhcdWM3NzQgXHViNDE4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1YWMwMSBcdWM5MDRcdWM3NDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWQ1NThcdWIwOThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViYTcwLCBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCAmcXVvdDtFWFBSPUVYUFImcXVvdDtcdWFjZmMgXHVhYzE5XHVjNzQwIFx1ZDYxNVx1ZDBkY1x1Yzc3NFx1YjJlNC4gRVhQUlx1YjI5NCAxN1x1Yzc5MFx1YjlhY1x1Yjk3YyBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YzIxOFx1YzJkZFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1YzIxOFx1YzJkZFx1Yzc0MCBcdWQ1NmRcdWMwYzEgXHVjNjJjXHViYzE0XHViOTc0XHViYTcwLCAmIzM5OysmIzM5OywgJiMzOTsqJiMzOTtcdWM2NDAgJiMzOTswJiMzOTstJiMzOTs5JiMzOTtcdWFlNGNcdWM5YzAgXHVjMjJiXHVjNzkwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YzIxOFx1YzJkZFx1Yzc3NCAmIzM5OysmIzM5O1x1YWUzMFx1ZDYzOFx1Yjg1YyBcdWMyZGNcdWM3OTFcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YzczY1x1YmE3MCwgXHVjMjE4XHVjNzU4IFx1YzU1ZVx1YzVkMCBcdWJkODhcdWQ1NDRcdWM2OTRcdWQ1NWMgMFx1Yzc3NCBcdWJkOTlcdWM1YjRcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHViM2M0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgJiMzOTs9JiMzOTtcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1YzViNFx1YjVhNCBcdWM5YzRcdWJjOTVcdWM3NDQgXHVjMGFjXHVjNmE5XHVkNTU4XHViYTc0IFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHViNGYxXHVjMmRkXHVjNzc0IFx1Y2MzOFx1Yzc3NCBcdWI0MThcdWIyOTRcdWM5YzAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0ZjFcdWMyZGRcdWM3NDQgXHVjYzM4XHVjNzNjXHViODVjIFx1YjljY1x1YjRkY1x1YjI5NCBcdWM5YzRcdWJjOTVcdWM3NzQgXHViYjM0XHVkNTVjXHViMzAwXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAmcXVvdDtCKyZxdW90O1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzVlY1x1YWUzMFx1YzExYyBCXHViMjk0IFx1YjRmMVx1YzJkZFx1Yzc0NCBcdWNjMzhcdWM3M2NcdWI4NWMgXHViOWNjXHViNGRjXHViMjk0IFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVjOWM0XHViYzk1XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM5YzRcdWJjOTVcdWM3NTggXHVjMjE4XHVhYzAwIFx1YzcyMFx1ZDU1Y1x1YWMxY1x1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjOWM0XHViYzk1XHVjNzQ0IFx1YzYyNFx1Yjk4NFx1Y2MyOFx1YzIxY1x1YzczY1x1Yjg1YyBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHVkNTU4XHVjNWVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWI0XHViNWE0IFx1YzljNFx1YmM5NVx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NzRcdWIzYzQgXHViNGYxXHVjMmRkXHVjNzc0IFx1Y2MzOFx1Yzc3NCBcdWI0MThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAmIzM5OyomIzM5O1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiNTcyMCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJhc2VzIiwiZGVzY3JpcHRpb24iOiI8cD5XaGF0IGRvIHlvdSBnZXQgaWYgeW91IG11bHRpcGx5IDYgYnkgOT8gVGhlIGFuc3dlciwgb2YgY291cnNlLCBpcyA0MiwgYnV0IG9ubHkgaWYgeW91IGRvIHRoZSBjYWxjdWxhdGlvbnMgaW4gYmFzZSAxMy48XC9wPlxyXG5cclxuPHA+R2l2ZW4gYW4gaW50ZWdlciBCICZnZTsgMiwgdGhlIGJhc2UgQiBudW1iZXJpbmcgc3lzdGVtIGlzIGEgbWFubmVyIG9mIHdyaXRpbmcgaW50ZWdlcnMgdXNpbmcgb25seSBkaWdpdHMgYmV0d2VlbiAwIGFuZCBCICZtaW51czsgMSwgaW5jbHVzaXZlLiBJbiBhIG51bWJlciB3cml0dGVuIGluIGJhc2UgQiwgdGhlIHJpZ2h0bW9zdCBkaWdpdCBoYXMgaXRzIHZhbHVlIG11bHRpcGxpZWQgYnkgMSwgdGhlIHNlY29uZCByaWdodG1vc3QgZGlnaXQgaGFzIGl0cyB2YWx1ZSBtdWx0aXBsaWVkIGJ5IEIsIHRoZSB0aGlyZCByaWdodG1vc3QgZGlnaXQgaGFzIGl0cyB2YWx1ZSBtdWx0aXBsaWVkIGJ5IEI8c3VwPjI8XC9zdXA+LCBhbmQgc28gb24uPFwvcD5cclxuXHJcbjxwPlNvbWUgZXF1YXRpb25zIGFyZSB0cnVlIG9yIGZhbHNlIGRlcGVuZGluZyBvbiB0aGUgYmFzZSB0aGV5IGFyZSBjb25zaWRlcmVkIGluLiBUaGUgZXF1YXRpb24gMiArIDIgPSA0LCBmb3IgaW5zdGFuY2UsIGlzIHRydWUgZm9yIGFueSBCICZnZTsgNSAmbWRhc2g7IGl0IGRvZXMgbm90IGhvbGQgaW4gYmFzZSA0LCBmb3IgaW5zdGFuY2UsIHNpbmNldGhlcmUgaXMgbm8gZGlnaXQgJmxzcXVvOzQmcnNxdW87IGluIGJhc2UgNC4gT24gdGhlIG90aGVyIGhhbmQsIGFuIGVxdWF0aW9uIGxpa2UgMiArIDIgPSA1IGlzIG5ldmVyIHRydWUuPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IGdpdmVuIGFuIGVxdWF0aW9uIGRldGVybWluZXMgZm9yIHdoaWNoIGJhc2VzIGl0IGhvbGRzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+RWFjaCBsaW5lIG9mIHRoZSBpbnB1dCBjb250YWlucyBhIHRlc3QgY2FzZTsgZWFjaCB0ZXN0IGNhc2UgaXMgYW4gZXF1YXRpb24gb2YgdGhlIGZvcm0gJmxkcXVvO0VYUFI9RVhQUiZyZHF1bzssIHdoZXJlIGJvdGggJmxkcXVvO0VYUFImcmRxdW87IGFyZSBhcml0aG1ldGljIGV4cHJlc3Npb25zIHdpdGggYXQgbW9zdCAxNyBjaGFyYWN0ZXJzLjxcL3A+XHJcblxyXG48cD5BbGwgZXhwcmVzc2lvbnMgYXJlIHZhbGlkLCBhbmQgY29udGFpbiBvbmx5IHRoZSBjaGFyYWN0ZXJzICZsc3F1bzsrJnJzcXVvOywgJmxzcXVvOyomcnNxdW87IGFuZCB0aGUgZGlnaXRzIGZyb20gJmxzcXVvOzAmcnNxdW87IHRvICZsc3F1bzs5JnJzcXVvOy4gTm8gZXhwcmVzc2lvbnMgY29udGFpbiBsZWFkaW5nIHBsdXMgc2lnbnMsIGFuZCBubyBudW1iZXJzIGluIGl0IGhhdmUgbGVhZGluZyB6ZXJvcy48XC9wPlxyXG5cclxuPHA+VGhlIGVuZCBvZiBpbnB1dCBpcyBpbmRpY2F0ZWQgYnkgYSBsaW5lIGNvbnRhaW5pbmcgb25seSAmbGRxdW87PSZyZHF1bzsuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlIGluIHRoZSBpbnB1dCB5b3VyIHByb2dyYW0gc2hvdWxkIHByb2R1Y2UgYSBzaW5nbGUgbGluZSBpbiB0aGUgb3V0cHV0LCBpbmRpY2F0aW5nIGZvciB3aGljaCBiYXNlcyB0aGUgZ2l2ZW4gZXF1YXRpb24gaG9sZHMuPFwvcD5cclxuXHJcbjxwPklmIHRoZSBleHByZXNzaW9uIGlzIHRydWUgZm9yIGluXHVmYjAxbml0ZWx5IG1hbnkgYmFzZXMsIHByaW50ICZsZHF1bztCKyZyZHF1bzssIHdoZXJlIEIgaXMgdGhlIFx1ZmIwMXJzdCBiYXNlIGZvciB3aGljaCB0aGUgZXF1YXRpb24gaG9sZHMuPFwvcD5cclxuXHJcbjxwPklmIHRoZSBleHByZXNzaW9uIGlzIHZhbGlkIG9ubHkgZm9yIGEgXHVmYjAxbml0ZSBzZXQgb2YgYmFzZXMsIHByaW50IHRoZW0gaW4gYXNjZW5kaW5nIG9yZGVyLCBzZXBhcmF0ZWQgYnkgc2luZ2xlIHNwYWNlcy48XC9wPlxyXG5cclxuPHA+SWYgdGhlIGV4cHJlc3Npb24gaXMgbm90IHRydWUgaW4gYW55IGJhc2UsIHByaW50IHRoZSBjaGFyYWN0ZXIgJmxzcXVvOyomcnNxdW87LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > Latin America > South America Regional Contests 2008 B번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: lsh0426