시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 256 MB168373026.316%

문제

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+XHJcblxyXG48cD5mKGspXHViOTdjIGtcdWM3NTggXHVjMThjXHVjNzc4XHVjMjE4XHViOTdjIFx1YmMzMFx1YzVmNFx1ZDU1YyBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHViNzdjXHVhY2UwIFx1ZDU1OFx1YmE3NCwmbmJzcDtmKDEwKSA9IDIsIGYoMjApID0gM1x1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YjU0YywgZihrKSA9IG5cdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IGtcdWIyOTQgXHVkNTZkXHVjMGMxIFx1YzgwMVx1YzViNFx1YjNjNCBcdWQ1NThcdWIwOTggXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAga1x1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWI5Y2VcdWM1NDRcdWM1N2MgMSwwMDBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IG4gJmx0OyAyPHN1cD42MzxcL3N1cD5cdWM3NzggXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIG5cdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHVhY2UwIGYoaykgPSBuIFx1Yzc3OCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIGsgJmd0OyAxXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gayAmbHQ7IDI8c3VwPjYzPFwvc3VwPlx1Yzc3OCBcdWM3ODVcdWI4MjVcdWI5Y2MgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6Ijg4ODAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJGYWN0b3JzIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgZnVuZGFtZW50YWwgdGhlb3JlbSBvZiBhcml0aG1ldGljIHN0YXRlcyB0aGF0IGV2ZXJ5IGludGVnZXIgZ3JlYXRlciB0aGFuIDEgY2FuIGJlIHVuaXF1ZWx5IHJlcHJlc2VudGVkIGFzIGEgcHJvZHVjdCBvZiBvbmUgb3IgbW9yZSBwcmltZXMuIFdoaWxlIHVuaXF1ZSwgc2V2ZXJhbCBhcnJhbmdlbWVudHMgb2YgdGhlIHByaW1lIGZhY3RvcnMgbWF5YmUgcG9zc2libGUuIEZvciBleGFtcGxlOjxcL3A+XHJcblxyXG48cD4xMCA9IDImdGltZXM7NSA9IDUmdGltZXM7MjxcL3A+XHJcblxyXG48cD4yMCA9IDImdGltZXM7MiZ0aW1lczs1ID0gMiZ0aW1lczs1JnRpbWVzOzIgPSA1JnRpbWVzOzImdGltZXM7MjxcL3A+XHJcblxyXG48cD5MZXQgZihrKSBiZSB0aGUgbnVtYmVyIG9mIGRpZmZlcmVudCBhcnJhbmdlbWVudHMgb2YgdGhlIHByaW1lIGZhY3RvcnMgb2Ygay4gU28gZigxMCkgPSAyIGFuZCBmKDIwKSA9IDMuPFwvcD5cclxuXHJcbjxwPkdpdmVuIGEgcG9zaXRpdmUgbnVtYmVyIG4sIHRoZXJlIGFsd2F5cyBleGlzdHMgYXQgbGVhc3Qgb25lIG51bWJlciBrIHN1Y2ggdGhhdCBmKGspID0gbi4gV2Ugd2FudCB0byBrbm93IHRoZSBzbWFsbGVzdCBzdWNoIGsuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2YgYXQgbW9zdCAxIDAwMCB0ZXN0IGNhc2VzLCBlYWNoIG9uIGEgc2VwYXJhdGUgbGluZS4gRWFjaCB0ZXN0IGNhc2UgaXMgYSBwb3NpdGl2ZSBpbnRlZ2VyIG4gJmx0OyAyPHN1cD42MzxcL3N1cD4uPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBkaXNwbGF5IGl0cyBudW1iZXIgbiBhbmQgdGhlIHNtYWxsZXN0IG51bWJlciBrICZndDsgMSBzdWNoIHRoYXQgZihrKSA9IG4uIFRoZSBudW1iZXJzIGluIHRoZSBpbnB1dCBhcmUgY2hvc2VuIHN1Y2ggdGhhdCBrICZsdDsgMjxzdXA+NjM8XC9zdXA+LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

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

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