의석이는 종강 기념 피자 파티를 열기 위해서 피자를 사러 왔다.
하지만 피자 가게 주인 동욱이는 피자를 순순히 판매하지 않는 사람이다.
돈 보다 문제 내는 것을 더 좋아하는 이상한 동욱이는 피자를 사러 온 의석이에게 3개의 시련을 부여했고, 모두 통과해야만 거래를 시작한다.
두 번째 관문에서는 GCD에 관련된 내용을 물어본다.
GCD(a,0) = a
GCD(a,b) = GCD(b, a%b)
GCD는 위와 같은 성질을 가진 함수이다.
동욱이가 원하는 것은 두 개의 숫자 A, B(A>B)를 찾는 것이다.
단, 이 두 개의 숫자에 대해서 GCD(A,B)를 실행하면 % 연산자가 총 K 번 수행된다는 사실을 알고 있다.
이러한 두 개의 숫자 조합 중에서 A가 가장 작으며 그런 조합이 여러 가지라면 B가 가장 작은 조합을 원한다.
예를 들어서, % 연산자가 3번 수행되는 조합은 (5, 3), (8, 3), (10, 6) 등이 있다.
그 중 원하는 조합은 (5, 3) 이 되는 것이다.
의석이를 도와서 K가 주어졌을 때, 관문 2의 정답을 구하는 프로그램을 작성하라.
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 정해진 % 연산자의 수행 회수 K(1≤K≤90)이 주어진다.
각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,
각 테스트 케이스마다 원하는 조합을 만족하는 두 개의 수 A, B (A>B)를 공백으로 출력한다.
3 // 테스트 케이스 개수
1 // 첫 번째 테스트 케이스 K = 1
3
20
#1 2 1 // 첫 번째 테스트 케이스 결과
#2 5 3
#3 17711 10946
import java.util.Scanner;
class Solution
{
public static void main(String args[]) throws Exception
{
Scanner sc = new Scanner(System.in);
int T;
T=sc.nextInt();
for(int test_case = 1; test_case <= T; test_case++)
{
int N = sc.nextInt();
long a=1;
long b=1;
long k=0;
for(int i=0; i<N; i++) {
k=a;
a=a+b;
b=k;
}
System.out.println("#"+test_case+" "+a+" "+b);
}
}
}