AT_arc051_b [ARC051B] 互除法

[problemUrl]: https://atcoder.jp/contests/arc051/tasks/arc051_b 高橋君は、ユークリッドの互除法というアルゴリズムを学びましたが、これがどのぐらいの速度で動くのか気になりました。 なので、以下のようなC言語のコードを書きました。 ``` #include int counter = 0; int gcd(int a, int b) { if (b == 0) return a; counter++; return gcd(b, a%b); } int main() { int a, b; scanf("%d %d", &a, &b); gcd(a, b); printf("%d\n", counter); } ``` これは、$ 2 $ つの整数を標準入力から受け取り、そのgcdをユークリッドの互除法で求め、求める際に何回再帰したかを出力するコードです。 あなたは、このプログラムにいろんな値を出力させたくなりました。 具体的には、$ K $ が与えられるので、このプログラムの出力が $ K $ となるような $ a,\ b $ を一組求めてください。

入力は以下の形式で標準入力から与えられる。 > $ K $

$ a,\ b $ を空白区切りで $ 1 $ 行に出力せよ。ただし、以下の制約を満たしていなければいけない。 $ 1\ ≦\ a,\ b\ ≦\ 1,000,000,000 $

### 制約 - $ 1\ ≦\ K\ ≦\ 40 $ ただし、以下の制約を満たすテストケースにすべて正解すれば $ 30 $ 点が与えられる。 - $ 1\ ≦\ K\ ≦\ 10 $ ### Sample Explanation 3 どの入出力例も、これ以外にも条件を満たす出力はたくさんあります。