Informatica Online Judge

  Operation Complexity [0566 / 0236]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 101   Total Tried : 120


The Champion of this Problem (C++) : gs17067 - 0ms / 104byte
My Best Submission (C++) : N/A

[]

Background

태호와 태양이는 각각 하나의 정수를 생각했다. 태호가 생각한 수를 a, 태양이가 생각한 수를 b라고 한다. (단, 태호가 생각한 정수가 태양이가 생각한 정수보다 항상 같거나 크다. 즉 a>=b)

태호와 태양이가 생각한 정수 a, b의 최대공약수를 구하려고 하면 가장 빠른 방법이 유클리드 알고리즘이다. 유클리드 알고리즘은 다음 원리를 이용해서 구한다.

* GCD(a,0) = a
* GCD(a,b) = GCD(b,a%b)

여기서 태호와 태양이는 이 방법이 얼마나 빠른지를 알기 위해서 %의 연산횟수를 측정했다.

연산횟수를 측정해 보니 오~~~~~~~~~~ 대박!!!

정말로 빠르다는 것을 알 수 있었다. 여기서 의문이 생겼다. "%"의 연산횟수가 주어질 때, 이 횟수로 최대공약수를 구할 수 있는 a와 b의 최소값을 구하고 싶어졌다.

의문을 풀 수 있도록 태호와 태양이를 도와주자.

Input

첫 번째 줄에 "%" 연산의 횟수 n이 주어진다. (단, n은 90이하의 자연수)

Output

입력조건을 만족하는 최소의 출력값 a와 b를 공백으로 구분하여 출력한다.
(단, a>=b, 그리고 a,b는 32bit정수를 초과할 수도 있다.)

IO Example

입력
20

출력
17711 10946

* 설명 : 17711과 10946을 입력하고 유클리드 알고리즘으로 두 수의 최대공약수를 구하려면 "%"연산을 20회 해야 한다. 이보다 더 적은 정수들로 20회를 할 수 있는 방법은 없다.

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