시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 1741 334 259 26.402%

문제

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

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

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

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

입력

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

출력

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

예제 입력 1

143 10

예제 출력 1

GOOD
W3sicHJvYmxlbV9pZCI6IjE4MzciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1NTRcdWQ2MzhcdWM4MWNcdWM3OTEiLCJkZXNjcmlwdGlvbiI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDEwMDZcL1NjcmVlbiBzaG90IDIwMTAtMDYtMTEgYXQgNF80OF80MiBQTS5wbmdcIiBzdHlsZT1cImZsb2F0OnJpZ2h0OyBoZWlnaHQ6MjQ0cHg7IHdpZHRoOjI5MXB4XCIgXC8+XHVjNmQwXHViOGUxXHVjNzc0XHViMjk0IFx1ZDU1YyBcdWNlZjRcdWQ0ZThcdWQxMzAgXHViY2Y0XHVjNTQ4IFx1ZDY4Y1x1YzBhY1x1YzVkMFx1YzExYyBcdWM3N2NcdWM3NDQgXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViN2VjXHViMzU4IFx1YjNjNFx1YzkxMSwgXHVjNmQwXHViOGUxXHVjNzc0XHViMjk0IFlFU1dPQS5DT00gXHVjNzNjXHViODVjXHViZDgwXHVkMTMwIFx1ZDY0OFx1ZDM5OFx1Yzc3NFx1YzljMCBcdWM3MjBcdWM4MDBcdWI0ZTRcdWM3NTggXHViZTQ0XHViYzAwXHVkMGE0XHViOTdjIFx1YjljY1x1YjRlNFx1Yjc3Y1x1YjI5NCBcdWM5YzBcdWMyZGNcdWI5N2MgXHViYzFiXHVjNTU4XHViMmU0LiBcdWM2ZDBcdWI4ZTFcdWM3NzRcdWIyOTQgXHViZTQ0XHViYzAwIFx1ZDBhNFx1Yjk3YyBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YmMyOVx1YmM5NVx1YzczY1x1Yjg1YyBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMxY1x1Yzc3OFx1YjljOFx1YjJlNCBcdWM1YjRcdWI1YTQgXHVkMmI5XHVjODE1XHVkNTVjIFx1YzE4Y1x1YzIxOCBwXHVjNjQwIHFcdWI5N2MgXHVjOGZjXHVjNWI0IFx1YjQ1MCBcdWMxOGNcdWMyMThcdWM3NTggXHVhY2YxIHBxXHViOTdjIFx1YmU0NFx1YmMwMCBcdWQwYTRcdWI4NWMgXHViNDUwXHVjNWM4XHViMmU0LiBcdWM3NzRcdWI4MDdcdWFjOGMgXHVkNTc0IFx1YzhmY1x1YmE3NCBcdWI0NTAgXHVjMThjXHVjMjE4IHAscVx1Yjk3YyBcdWM1NGNcdWM5YzAgXHViYWJiXHVkNTU4XHViMjk0IFx1Yzc3NFx1YzBjMSwgXHViZTQ0XHViYzAwIFx1ZDBhNFx1Yjk3YyBcdWM1NGMgXHVjMjE4IFx1YzVjNlx1YjJlNFx1YjI5NCBcdWM3YTVcdWM4MTBcdWM3NDQgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTU4XHVjOWMwXHViOWNjIFx1YzZkMFx1YjhlMVx1Yzc3NFx1YjI5NCBcdWQ1NWMgXHVhYzAwXHVjOWMwIFx1YzBhY1x1YzJlNFx1Yzc0NCBcdWM3OGFcdWFjZTAgXHViOWQwXHVjNTU4XHViMmU0LiBcdWNkNWNcdWFkZmMgXHVjZWY0XHVkNGU4XHVkMTMwIFx1YWUzMFx1YzIyMFx1Yzc3NCBcdWJjMWNcdWIyZWNcdWQ1NjhcdWM1ZDAgXHViNTMwXHViNzdjLCBcdWMxOGNcdWMyMThcdWFjMDAgXHVjNzkxXHVjNzQwIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWNlZjRcdWQ0ZThcdWQxMzBcdWI4NWMgXHViYWE4XHViNGUwIFx1YWNiZFx1YzZiMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHViM2NjXHViODI0XHViY2Y0XHVjNTQ0IFx1YmU0NFx1YmMwMCBcdWQwYTRcdWI5N2MgXHVjMjdkXHVhYzhjIFx1YzU0YyBcdWMyMTggXHVjNzg4XHViMmU0XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNmQwXHViOGUxXHVjNzc0XHViMjk0IFx1YzhmY1x1YzEzMVx1Yzg3MFx1YWQ1MFx1YjJkOFx1YWVkOCBcdWJlNDRcdWJjMDAgXHVkMGE0XHViOTdjIFx1YzgxY1x1Y2Q5Y1x1ZDU1OFx1YjgyNFx1YjM1OCBcdWJjMTRcdWI4NWMgXHVjOWMxXHVjODA0XHVjNWQwIFx1Yzc3NCBcdWMwYWNcdWMyZTRcdWM3NDQgXHVjNTRjXHVjNTQ0XHViMGM4XHViMmU0LiBcdWFkZjhcdWI3OThcdWMxMWMgXHViNDUwIFx1YzE4Y1x1YzIxOCBwLCBxIFx1YzkxMSBcdWQ1NThcdWIwOThcdWI3N2NcdWIzYzQgS1x1YmNmNFx1YjJlNCBcdWM3OTFcdWM3NDAgXHVjNTU0XHVkNjM4XHViMjk0IFx1Yzg4Ylx1YzljMCBcdWM1NGFcdWM3NDAgXHVjNTU0XHVkNjM4XHViODVjIFx1YWMwNFx1YzhmY1x1ZDU1OFx1YzVlYyBcdWM4MWNcdWNkOWNcdWQ1NThcdWM5YzAgXHVjNTRhXHVhZTMwXHViODVjIFx1ZDU1OFx1YzYwMFx1YjJlNC4gXHVjNzc0XHVhYzgzXHVjNzQ0IFx1YzE5MFx1YzczY1x1Yjg1YyBcdWM5YzFcdWM4MTEgXHVhZDZjXHVkNTc0XHViY2Y0XHViMjk0IFx1Yzc3Y1x1Yzc0MCBcdWI5ZTRcdWM2YjAgXHVkNzk4XHViNGU0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHViMmY5XHVjMmUwXHVjNzQwIFx1YzZkMFx1YjhlMVx1Yzc3NFx1Yjk3YyBcdWIzYzRcdWM2NDAgXHViNDUwIFx1YzE4Y1x1YzIxOFx1Yzc1OCBcdWFjZjFcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YzU1NFx1ZDYzOFx1YzY0MCBLXHVhYzAwIFx1YzhmY1x1YzViNFx1YzgzOCBcdWM3ODhcdWM3NDQgXHViNTRjLCBcdWFkZjggXHVjNTU0XHVkNjM4XHVhYzAwIFx1Yzg4Ylx1Yzc0MCBcdWM1NTRcdWQ2MzhcdWM3NzhcdWM5YzAgXHVjODhiXHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWM1NTRcdWQ2MzhcdWM3NzhcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWM1ZWNcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNTU0XHVkNjM4IFAoNCAmbGU7IFAgJmxlOyAxMDxzdXA+MTAwPFwvc3VwPilcdWM2NDAgSygyICZsZTsgSyAmbGU7IDEwPHN1cD42PFwvc3VwPikgXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWI5Y2NcdWM1N2RcdWM1ZDAgXHVhZGY4IFx1YzU1NFx1ZDYzOFx1YWMwMCBcdWM4OGJcdWM3NDAgXHVjNTU0XHVkNjM4XHVjNzc0XHViYTc0IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgR09PRFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWFjZTAsIFx1YjljY1x1YzU3ZFx1YzVkMCBcdWM4OGJcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YzU1NFx1ZDYzOFx1Yzc3NFx1YmE3NCBCQURcdWM2NDAgXHVjMThjXHVjMjE4IHBcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViMjk0XHViMzcwIHBcdWIyOTQgXHVjNTU0XHVkNjM4XHViOTdjIFx1Yzc3NFx1YjhlOFx1YjI5NCBcdWI0NTAgXHVjMThjXHVjMjE4Jm5ic3A7IFx1YzkxMSBcdWM3OTFcdWM3NDAgXHVjMThjXHVjMjE4XHViOTdjIFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxODM3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGhlIEVtYmFycmFzc2VkIENyeXB0b2dyYXBoZXIiLCJkZXNjcmlwdGlvbiI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDEwMDZcL1NjcmVlbiBzaG90IDIwMTAtMDYtMTEgYXQgNF80OF80MiBQTS5wbmdcIiBzdHlsZT1cImZsb2F0OnJpZ2h0OyBoZWlnaHQ6MjQ0cHg7IHdpZHRoOjI5MXB4XCIgXC8+VGhlIHlvdW5nIGFuZCB2ZXJ5IHByb21pc2luZyBjcnlwdG9ncmFwaGVyIE9kZCBFdmVuIGhhcyBpbXBsZW1lbnRlZCB0aGUgc2VjdXJpdHkgbW9kdWxlIG9mIGEgbGFyZ2Ugc3lzdGVtIHdpdGggdGhvdXNhbmRzIG9mIHVzZXJzLCB3aGljaCBpcyBub3cgaW4gdXNlIGluIGhpcyBjb21wYW55LiBUaGUgY3J5cHRvZ3JhcGhpYyBrZXlzIGFyZSBjcmVhdGVkIGZyb20gdGhlIHByb2R1Y3Qgb2YgdHdvIHByaW1lcywgYW5kIGFyZSBiZWxpZXZlZCB0byBiZSBzZWN1cmUgYmVjYXVzZSB0aGVyZSBpcyBubyBrbm93biBtZXRob2QgZm9yIGZhY3RvcmluZyBzdWNoIGEgcHJvZHVjdCBlZmZlY3RpdmVseS48XC9wPlxyXG5cclxuPHA+V2hhdCBPZGQgRXZlbiBkaWQgbm90IHRoaW5rIG9mLCB3YXMgdGhhdCBib3RoIGZhY3RvcnMgaW4gYSBrZXkgc2hvdWxkIGJlIGxhcmdlLCBub3QganVzdCB0aGVpciBwcm9kdWN0LiBJdCBpcyBub3cgcG9zc2libGUgdGhhdCBzb21lIG9mIHRoZSB1c2VycyBvZiB0aGUgc3lzdGVtIGhhdmUgd2VhayBrZXlzLiBJbiBhIGRlc3BlcmF0ZSBhdHRlbXB0IG5vdCB0byBiZSBcdWZiMDFyZWQsIE9kZCBFdmVuIHNlY3JldGx5IGdvZXMgdGhyb3VnaCBhbGwgdGhlIHVzZXJzIGtleXMsIHRvIGNoZWNrIGlmIHRoZXkgYXJlIHN0cm9uZyBlbm91Z2guIEhlIHVzZXMgaGlzIHZlcnkgcG93ZWZ1bCBBdGFyaSwgYW5kIGlzIGVzcGVjaWFsbHkgY2FyZWZ1bCB3aGVuIGNoZWNraW5nIGhpcyBib3NzJnJzcXVvOyBrZXkuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2Ygbm8gbW9yZSB0aGFuIDIwIHRlc3QgY2FzZXMuIEVhY2ggdGVzdCBjYXNlIGlzIGEgbGluZSB3aXRoIHRoZSBpbnRlZ2VycyA0ICZsZTsgSyAmbGU7IDEwPHN1cD4xMDA8XC9zdXA+IGFuZCAyICZsZTsgTCAmbGU7IDEwPHN1cD42PFwvc3VwPiAuIEsgaXMgdGhlIGtleSBpdHNlbGYsIGEgcHJvZHVjdCBvZiB0d28gcHJpbWVzLiBMIGlzIHRoZSB3YW50ZWQgbWluaW11bSBzaXplIG9mIHRoZSBmYWN0b3JzIGluIHRoZSBrZXkuIFRoZSBpbnB1dCBzZXQgaXMgdGVybWluYXRlZCBieSBhIGNhc2Ugd2hlcmUgSyA9IDAgYW5kIEwgPSAwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIG51bWJlciBLLCBpZiBvbmUgb2YgaXRzIGZhY3RvcnMgYXJlIHN0cmljdGx5IGxlc3MgdGhhbiB0aGUgcmVxdWlyZWQgTCwgeW91ciBwcm9ncmFtIHNob3VsZCBvdXRwdXQgJmxkcXVvO0JBRCBwJnJkcXVvOywgd2hlcmUgcCBpcyB0aGUgc21hbGxlc3QgZmFjdG9yIGluIEsuIE90aGVyd2lzZSwgaXQgc2hvdWxkIG91dHB1dCAmbGRxdW87R09PRCZyZHF1bzsuIENhc2VzIHNob3VsZCBiZSBzZXBhcmF0ZWQgYnkgYSBsaW5lLWJyZWFrLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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

  • 문제를 번역한 사람: author11
  • 데이터를 추가한 사람: doju
  • 어색한 표현을 찾은 사람: myungwoo