시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 93 31 22 33.846%

문제

1보다 큰 모든 자연수는 하나 또는 그 이상의 소수의 곱으로 유일하게 나타낼 수 있다. 하지만, 이러한 소인수들을 배열하는 방법은 여러 가지가 있을 수 있다.

10 = 2×5 = 5×2

20 = 2×2×5 = 2×5×2 = 5×2×2

f(k)를 k의 소인수를 배열한 방법의 수라고 하면, f(10) = 2, f(20) = 3이 된다.

양의 정수 n이 주어진다. 이 때, f(k) = n을 만족하는 k는 항상 적어도 하나 존재한다. 이 때, 가장 작은 k를 구하는 프로그램을 작성하시오.

입력

입력은 많아야 1,000개의 테스트 케이스로 이루어져 있고, 한 줄에 하나씩 주어진다. 각 테스트 케이스는 n < 263인 양의 정수이다.

출력

각 테스트 케이스에 대해서, n을 출력하고 f(k) = n 인 가장 작은 k > 1을 출력한다. k < 263인 입력만 주어진다.

예제 입력 1

1
2
3
105

예제 출력 1

1 2
2 6
3 12
105 720
W3sicHJvYmxlbV9pZCI6Ijg4ODAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3NzhcdWMyMTgiLCJkZXNjcmlwdGlvbiI6IjxwPjFcdWJjZjRcdWIyZTQgXHVkMDcwIFx1YmFhOFx1YjRlMCBcdWM3OTBcdWM1ZjBcdWMyMThcdWIyOTQgXHVkNTU4XHViMDk4IFx1YjYxMFx1YjI5NCBcdWFkZjggXHVjNzc0XHVjMGMxXHVjNzU4IFx1YzE4Y1x1YzIxOFx1Yzc1OCBcdWFjZjFcdWM3M2NcdWI4NWMgXHVjNzIwXHVjNzdjXHVkNTU4XHVhYzhjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWMxOGNcdWM3NzhcdWMyMThcdWI0ZTRcdWM3NDQgXHViYzMwXHVjNWY0XHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzAwXHVjOWMwXHVhYzAwIFx1Yzc4OFx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD4xMCA9IDImdGltZXM7NSA9IDUmdGltZXM7MjxcL3A+XHJcblxyXG48cD4yMCA9IDImdGltZXM7MiZ0aW1lczs1ID0gMiZ0aW1lczs1JnRpbWVzOzIgPSA1JnRpbWVzOzImdGltZXM7MjxcL3A+XHJcblxyXG48cD5mKGspXHViOTdjIGtcdWM3NTggXHVjMThjXHVjNzc4XHVjMjE4XHViOTdjIFx1YmMzMFx1YzVmNFx1ZDU1YyBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHViNzdjXHVhY2UwIFx1ZDU1OFx1YmE3NCwmbmJzcDtmKDEwKSA9IDIsIGYoMjApID0gM1x1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIGYoaykgPSBuXHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBrXHViMjk0IFx1ZDU2ZFx1YzBjMSBcdWM4MDFcdWM1YjRcdWIzYzQgXHVkNTU4XHViMDk4IFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YjU0YywgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBrXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YjljZVx1YzU0NFx1YzU3YyAxLDAwMFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgbiAmbHQ7IDI8c3VwPjYzPFwvc3VwPlx1Yzc3OCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgblx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWFjZTAgZihrKSA9IG4gXHVjNzc4IFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgayAmZ3Q7IDFcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBrICZsdDsgMjxzdXA+NjM8XC9zdXA+XHVjNzc4IFx1Yzc4NVx1YjgyNVx1YjljYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiODg4MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZhY3RvcnMiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBmdW5kYW1lbnRhbCB0aGVvcmVtIG9mIGFyaXRobWV0aWMgc3RhdGVzIHRoYXQgZXZlcnkgaW50ZWdlciBncmVhdGVyIHRoYW4gMSBjYW4gYmUgdW5pcXVlbHkgcmVwcmVzZW50ZWQgYXMgYSBwcm9kdWN0IG9mIG9uZSBvciBtb3JlIHByaW1lcy4gV2hpbGUgdW5pcXVlLCBzZXZlcmFsIGFycmFuZ2VtZW50cyBvZiB0aGUgcHJpbWUgZmFjdG9ycyBtYXliZSBwb3NzaWJsZS4gRm9yIGV4YW1wbGU6PFwvcD5cclxuXHJcbjxwPjEwID0gMiZ0aW1lczs1ID0gNSZ0aW1lczsyPFwvcD5cclxuXHJcbjxwPjIwID0gMiZ0aW1lczsyJnRpbWVzOzUgPSAyJnRpbWVzOzUmdGltZXM7MiA9IDUmdGltZXM7MiZ0aW1lczsyPFwvcD5cclxuXHJcbjxwPkxldCBmKGspIGJlIHRoZSBudW1iZXIgb2YgZGlmZmVyZW50IGFycmFuZ2VtZW50cyBvZiB0aGUgcHJpbWUgZmFjdG9ycyBvZiBrLiBTbyBmKDEwKSA9IDIgYW5kIGYoMjApID0gMy48XC9wPlxyXG5cclxuPHA+R2l2ZW4gYSBwb3NpdGl2ZSBudW1iZXIgbiwgdGhlcmUgYWx3YXlzIGV4aXN0cyBhdCBsZWFzdCBvbmUgbnVtYmVyIGsgc3VjaCB0aGF0IGYoaykgPSBuLiBXZSB3YW50IHRvIGtub3cgdGhlIHNtYWxsZXN0IHN1Y2ggay48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiBhdCBtb3N0IDEgMDAwIHRlc3QgY2FzZXMsIGVhY2ggb24gYSBzZXBhcmF0ZSBsaW5lLiBFYWNoIHRlc3QgY2FzZSBpcyBhIHBvc2l0aXZlIGludGVnZXIgbiAmbHQ7IDI8c3VwPjYzPFwvc3VwPi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIGRpc3BsYXkgaXRzIG51bWJlciBuIGFuZCB0aGUgc21hbGxlc3QgbnVtYmVyIGsgJmd0OyAxIHN1Y2ggdGhhdCBmKGspID0gbi4gVGhlIG51bWJlcnMgaW4gdGhlIGlucHV0IGFyZSBjaG9zZW4gc3VjaCB0aGF0IGsgJmx0OyAyPHN1cD42MzxcL3N1cD4uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ACM-ICPC > World Finals > 2013 World Finals D번

  • 문제를 번역한 사람: baekjoon
  • 어색한 표현을 찾은 사람: joonas