시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 3533 756 524 23.786%

문제

원룡이는 한 컴퓨터 보안 회사에서 일을 하고 있다. 그러던 도중, 원룡이는 YESWOA.COM 으로부터 홈페이지 유저들의 비밀키를 만들라는 지시를 받았다. 원룡이는 비밀 키를 다음과 같은 방법으로 만들었다.

개인마다 어떤 특정한 소수 p와 q를 주어 두 소수의 곱 pq를 비밀 키로 두었다. 이렇게 해 주면 두 소수 p,q를 알지 못하는 이상, 비밀 키를 알 수 없다는 장점을 가지고 있다.

하지만 원룡이는 한 가지 사실을 잊고 말았다. 최근 컴퓨터 기술이 발달함에 따라, 소수가 작은 경우에는 컴퓨터로 모든 경우의 수를 돌려보아 비밀 키를 쉽게 알 수 있다는 것이다.

원룡이는 주성조교님께 비밀 키를 제출하려던 바로 직전에 이 사실을 알아냈다. 그래서 두 소수 p, q 중 하나라도 K보다 작은 암호는 좋지 않은 암호로 간주하여 제출하지 않기로 하였다. 이것을 손으로 직접 구해보는 일은 매우 힘들 것이다. 당신은 원룡이를 도와 두 소수의 곱으로 이루어진 암호와 K가 주어져 있을 때, 그 암호가 좋은 암호인지 좋지 않은 암호인지 구하는 프로그램을 작성하여야 한다.

입력

암호 P(4 ≤ P ≤ 10100)와 K(2 ≤ K ≤ 106) 이 주어진다.

출력

만약에 그 암호가 좋은 암호이면 첫째 줄에 GOOD을 출력하고, 만약에 좋지 않은 암호이면 BAD와 소수 r을 공백으로 구분하여 출력하는데 r은 암호를 이루는 두 소수 중 작은 소수를 의미한다.

예제 입력 1

143 10

예제 출력 1

GOOD

예제 입력 2

77 12

예제 출력 2

BAD 7
W3sicHJvYmxlbV9pZCI6IjE4MzciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1NTRcdWQ2MzhcdWM4MWNcdWM3OTEiLCJkZXNjcmlwdGlvbiI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDEwMDZcL1NjcmVlbiBzaG90IDIwMTAtMDYtMTEgYXQgNF80OF80MiBQTS5wbmdcIiBzdHlsZT1cImZsb2F0OnJpZ2h0OyBoZWlnaHQ6MjQ0cHg7IHdpZHRoOjI5MXB4XCIgXC8+XHVjNmQwXHViOGUxXHVjNzc0XHViMjk0IFx1ZDU1YyBcdWNlZjRcdWQ0ZThcdWQxMzAgXHViY2Y0XHVjNTQ4IFx1ZDY4Y1x1YzBhY1x1YzVkMFx1YzExYyBcdWM3N2NcdWM3NDQgXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViN2VjXHViMzU4IFx1YjNjNFx1YzkxMSwgXHVjNmQwXHViOGUxXHVjNzc0XHViMjk0IFlFU1dPQS5DT00gXHVjNzNjXHViODVjXHViZDgwXHVkMTMwIFx1ZDY0OFx1ZDM5OFx1Yzc3NFx1YzljMCBcdWM3MjBcdWM4MDBcdWI0ZTRcdWM3NTggXHViZTQ0XHViYzAwXHVkMGE0XHViOTdjIFx1YjljY1x1YjRlNFx1Yjc3Y1x1YjI5NCBcdWM5YzBcdWMyZGNcdWI5N2MgXHViYzFiXHVjNTU4XHViMmU0LiBcdWM2ZDBcdWI4ZTFcdWM3NzRcdWIyOTQgXHViZTQ0XHViYzAwIFx1ZDBhNFx1Yjk3YyBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YmMyOVx1YmM5NVx1YzczY1x1Yjg1YyBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMxY1x1Yzc3OFx1YjljOFx1YjJlNCBcdWM1YjRcdWI1YTQgXHVkMmI5XHVjODE1XHVkNTVjIFx1YzE4Y1x1YzIxOCBwXHVjNjQwIHFcdWI5N2MgXHVjOGZjXHVjNWI0IFx1YjQ1MCBcdWMxOGNcdWMyMThcdWM3NTggXHVhY2YxIHBxXHViOTdjIFx1YmU0NFx1YmMwMCBcdWQwYTRcdWI4NWMgXHViNDUwXHVjNWM4XHViMmU0LiBcdWM3NzRcdWI4MDdcdWFjOGMgXHVkNTc0IFx1YzhmY1x1YmE3NCBcdWI0NTAgXHVjMThjXHVjMjE4IHAscVx1Yjk3YyBcdWM1NGNcdWM5YzAgXHViYWJiXHVkNTU4XHViMjk0IFx1Yzc3NFx1YzBjMSwgXHViZTQ0XHViYzAwIFx1ZDBhNFx1Yjk3YyBcdWM1NGMgXHVjMjE4IFx1YzVjNlx1YjJlNFx1YjI5NCBcdWM3YTVcdWM4MTBcdWM3NDQgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTU4XHVjOWMwXHViOWNjIFx1YzZkMFx1YjhlMVx1Yzc3NFx1YjI5NCBcdWQ1NWMgXHVhYzAwXHVjOWMwIFx1YzBhY1x1YzJlNFx1Yzc0NCBcdWM3OGFcdWFjZTAgXHViOWQwXHVjNTU4XHViMmU0LiBcdWNkNWNcdWFkZmMgXHVjZWY0XHVkNGU4XHVkMTMwIFx1YWUzMFx1YzIyMFx1Yzc3NCBcdWJjMWNcdWIyZWNcdWQ1NjhcdWM1ZDAgXHViNTMwXHViNzdjLCBcdWMxOGNcdWMyMThcdWFjMDAgXHVjNzkxXHVjNzQwIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWNlZjRcdWQ0ZThcdWQxMzBcdWI4NWMgXHViYWE4XHViNGUwIFx1YWNiZFx1YzZiMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHViM2NjXHViODI0XHViY2Y0XHVjNTQ0IFx1YmU0NFx1YmMwMCBcdWQwYTRcdWI5N2MgXHVjMjdkXHVhYzhjIFx1YzU0YyBcdWMyMTggXHVjNzg4XHViMmU0XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNmQwXHViOGUxXHVjNzc0XHViMjk0IFx1YzhmY1x1YzEzMVx1Yzg3MFx1YWQ1MFx1YjJkOFx1YWVkOCBcdWJlNDRcdWJjMDAgXHVkMGE0XHViOTdjIFx1YzgxY1x1Y2Q5Y1x1ZDU1OFx1YjgyNFx1YjM1OCBcdWJjMTRcdWI4NWMgXHVjOWMxXHVjODA0XHVjNWQwIFx1Yzc3NCBcdWMwYWNcdWMyZTRcdWM3NDQgXHVjNTRjXHVjNTQ0XHViMGM4XHViMmU0LiBcdWFkZjhcdWI3OThcdWMxMWMgXHViNDUwIFx1YzE4Y1x1YzIxOCBwLCBxIFx1YzkxMSBcdWQ1NThcdWIwOThcdWI3N2NcdWIzYzQgS1x1YmNmNFx1YjJlNCBcdWM3OTFcdWM3NDAgXHVjNTU0XHVkNjM4XHViMjk0IFx1Yzg4Ylx1YzljMCBcdWM1NGFcdWM3NDAgXHVjNTU0XHVkNjM4XHViODVjIFx1YWMwNFx1YzhmY1x1ZDU1OFx1YzVlYyBcdWM4MWNcdWNkOWNcdWQ1NThcdWM5YzAgXHVjNTRhXHVhZTMwXHViODVjIFx1ZDU1OFx1YzYwMFx1YjJlNC4gXHVjNzc0XHVhYzgzXHVjNzQ0IFx1YzE5MFx1YzczY1x1Yjg1YyBcdWM5YzFcdWM4MTEgXHVhZDZjXHVkNTc0XHViY2Y0XHViMjk0IFx1Yzc3Y1x1Yzc0MCBcdWI5ZTRcdWM2YjAgXHVkNzk4XHViNGU0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHViMmY5XHVjMmUwXHVjNzQwIFx1YzZkMFx1YjhlMVx1Yzc3NFx1Yjk3YyBcdWIzYzRcdWM2NDAgXHViNDUwIFx1YzE4Y1x1YzIxOFx1Yzc1OCBcdWFjZjFcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YzU1NFx1ZDYzOFx1YzY0MCBLXHVhYzAwIFx1YzhmY1x1YzViNFx1YzgzOCBcdWM3ODhcdWM3NDQgXHViNTRjLCBcdWFkZjggXHVjNTU0XHVkNjM4XHVhYzAwIFx1Yzg4Ylx1Yzc0MCBcdWM1NTRcdWQ2MzhcdWM3NzhcdWM5YzAgXHVjODhiXHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWM1NTRcdWQ2MzhcdWM3NzhcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWM1ZWNcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNTU0XHVkNjM4IFAoNCAmbGU7IFAgJmxlOyAxMDxzdXA+MTAwPFwvc3VwPilcdWM2NDAgSygyICZsZTsgSyAmbGU7IDEwPHN1cD42PFwvc3VwPikgXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWI5Y2NcdWM1N2RcdWM1ZDAgXHVhZGY4IFx1YzU1NFx1ZDYzOFx1YWMwMCBcdWM4OGJcdWM3NDAgXHVjNTU0XHVkNjM4XHVjNzc0XHViYTc0IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgR09PRFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWFjZTAsIFx1YjljY1x1YzU3ZFx1YzVkMCBcdWM4OGJcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YzU1NFx1ZDYzOFx1Yzc3NFx1YmE3NCBCQURcdWM2NDAgXHVjMThjXHVjMjE4IHJcdWM3NDQmbmJzcDtcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHVkNTU4XHVjNWVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NFx1YjM3MCByXHVjNzQwJm5ic3A7XHVjNTU0XHVkNjM4XHViOTdjIFx1Yzc3NFx1YjhlOFx1YjI5NCBcdWI0NTAgXHVjMThjXHVjMjE4Jm5ic3A7XHVjOTExIFx1Yzc5MVx1Yzc0MCBcdWMxOGNcdWMyMThcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE4MzciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUaGUgRW1iYXJyYXNzZWQgQ3J5cHRvZ3JhcGhlciIsImRlc2NyaXB0aW9uIjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL0p1ZGdlT25saW5lXC91cGxvYWRcLzIwMTAwNlwvU2NyZWVuIHNob3QgMjAxMC0wNi0xMSBhdCA0XzQ4XzQyIFBNLnBuZ1wiIHN0eWxlPVwiZmxvYXQ6cmlnaHQ7IGhlaWdodDoyNDRweDsgd2lkdGg6MjkxcHhcIiBcLz5UaGUgeW91bmcgYW5kIHZlcnkgcHJvbWlzaW5nIGNyeXB0b2dyYXBoZXIgT2RkIEV2ZW4gaGFzIGltcGxlbWVudGVkIHRoZSBzZWN1cml0eSBtb2R1bGUgb2YgYSBsYXJnZSBzeXN0ZW0gd2l0aCB0aG91c2FuZHMgb2YgdXNlcnMsIHdoaWNoIGlzIG5vdyBpbiB1c2UgaW4gaGlzIGNvbXBhbnkuIFRoZSBjcnlwdG9ncmFwaGljIGtleXMgYXJlIGNyZWF0ZWQgZnJvbSB0aGUgcHJvZHVjdCBvZiB0d28gcHJpbWVzLCBhbmQgYXJlIGJlbGlldmVkIHRvIGJlIHNlY3VyZSBiZWNhdXNlIHRoZXJlIGlzIG5vIGtub3duIG1ldGhvZCBmb3IgZmFjdG9yaW5nIHN1Y2ggYSBwcm9kdWN0IGVmZmVjdGl2ZWx5LjxcL3A+XHJcblxyXG48cD5XaGF0IE9kZCBFdmVuIGRpZCBub3QgdGhpbmsgb2YsIHdhcyB0aGF0IGJvdGggZmFjdG9ycyBpbiBhIGtleSBzaG91bGQgYmUgbGFyZ2UsIG5vdCBqdXN0IHRoZWlyIHByb2R1Y3QuIEl0IGlzIG5vdyBwb3NzaWJsZSB0aGF0IHNvbWUgb2YgdGhlIHVzZXJzIG9mIHRoZSBzeXN0ZW0gaGF2ZSB3ZWFrIGtleXMuIEluIGEgZGVzcGVyYXRlIGF0dGVtcHQgbm90IHRvIGJlIFx1ZmIwMXJlZCwgT2RkIEV2ZW4gc2VjcmV0bHkgZ29lcyB0aHJvdWdoIGFsbCB0aGUgdXNlcnMga2V5cywgdG8gY2hlY2sgaWYgdGhleSBhcmUgc3Ryb25nIGVub3VnaC4gSGUgdXNlcyBoaXMgdmVyeSBwb3dlZnVsIEF0YXJpLCBhbmQgaXMgZXNwZWNpYWxseSBjYXJlZnVsIHdoZW4gY2hlY2tpbmcgaGlzIGJvc3MmcnNxdW87IGtleS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiBubyBtb3JlIHRoYW4gMjAgdGVzdCBjYXNlcy4gRWFjaCB0ZXN0IGNhc2UgaXMgYSBsaW5lIHdpdGggdGhlIGludGVnZXJzIDQgJmxlOyBLICZsZTsgMTA8c3VwPjEwMDxcL3N1cD4gYW5kIDIgJmxlOyBMICZsZTsgMTA8c3VwPjY8XC9zdXA+IC4gSyBpcyB0aGUga2V5IGl0c2VsZiwgYSBwcm9kdWN0IG9mIHR3byBwcmltZXMuIEwgaXMgdGhlIHdhbnRlZCBtaW5pbXVtIHNpemUgb2YgdGhlIGZhY3RvcnMgaW4gdGhlIGtleS4gVGhlIGlucHV0IHNldCBpcyB0ZXJtaW5hdGVkIGJ5IGEgY2FzZSB3aGVyZSBLID0gMCBhbmQgTCA9IDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggbnVtYmVyIEssIGlmIG9uZSBvZiBpdHMgZmFjdG9ycyBhcmUgc3RyaWN0bHkgbGVzcyB0aGFuIHRoZSByZXF1aXJlZCBMLCB5b3VyIHByb2dyYW0gc2hvdWxkIG91dHB1dCAmbGRxdW87QkFEIHAmcmRxdW87LCB3aGVyZSBwIGlzIHRoZSBzbWFsbGVzdCBmYWN0b3IgaW4gSy4gT3RoZXJ3aXNlLCBpdCBzaG91bGQgb3V0cHV0ICZsZHF1bztHT09EJnJkcXVvOy4gQ2FzZXMgc2hvdWxkIGJlIHNlcGFyYXRlZCBieSBhIGxpbmUtYnJlYWsuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > Nordic Collegiate Programming Contest > NCPC 2005 D번