Informatica Online Judge

  소인수 분해 순열 [2297 / 08F9]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 0   Total Tried : 1


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[ACM ICPC 2013 WF]

Background

1보다 큰 모든 정수는 1개 이상의 소수의 곱으로 표현 가능하고, 유일한 소인수 분해를 가진다는 산술의 기본 정리는 많이 알려져 있다.

소수의 곱으로 표현하는 방법은 유일하지만, 각 소인수들의 자리바꿈을 생각하면 여러 개의 순열을 만들 수 있다.

예시:

10 = 2*5 = 5*2

20 = 2*2*5 = 2*5*2 = 5*2*2



어떤 정수 k의 소인수 분해 자리바꿈 개수를 f(k)라고 하면, f(10) = 2 이고, f(20) = 3 이라고 할 수 있다.

어떤 양의 정수 n이 주어지면, f(k) = n 을 만족하는 k 가 1개 이상 존재한다. 그 중 가장 작은 값이 어떤 것인지 찾아내보자.

Input

최대 1000개의 값(ni)이 줄을 바꿔 입력된다.

단 ni < 2^63

Output

각 ni 값과 f(k) = n 을 만족하는 가장 작은 값 k 를 공백을 두고 줄을 바꿔가며 출력한다.

1 < k < 2^63

IO Example

입력1
1
2
3
105

출력1
1 2
2 6
3 12
105 720

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]