[ARC051B] 互除法

## 题目描述 高桥君学习了欧几里得算法，他很好奇它能以多快的速度运行。 因此，他写了以下代码。 ```cpp #include <stdio.h> 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); } ``` 这个代码输入两个整数，然后用欧几里得计算它们的 $\gcd$，然后输出它递归了多少次的代码。 你想让这个程序输出各种各样的值。 具体来说，输入一个 $K$，输出一组可以使得这个程序的输出为 $K$ 的 $A$、$B$。 ## 输入格式 一个正整数 $K$。 ## 输出格式 一行，两个正整数 $A$ 和$B$。 但是，必须满足 $1\le A,B\le 10^9$。 ## 说明\提示 对于 $30\%$ 的数据，$1\le K \le 10$； 对于 $100\%$ 的数据，$1\le K \le 40$。 只输出其中一种可能的解即可。

[problemUrl]: https://atcoder.jp/contests/arc051/tasks/arc051_b 高橋君は、ユークリッドの互除法というアルゴリズムを学びましたが、これがどのぐらいの速度で動くのか気になりました。 なので、以下のようなC言語のコードを書きました。 ``` #include <stdio.h> 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

1 1

3

4 5

12

314159265 358979323

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