問題文
高桥先生了解了一种称为欧几里得算法的算法,但他很好奇它的运行速度有多快。
所以我写了下面的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 。
制約
- 1 ≦ K ≦ 40
但是,如果满足以下约束的所有测试用例都得到正确回答, 30 点。
- 1 ≦ K ≦ 10
入力
输入是按以下格式从标准输入给出的。
K
出力
a, b 以空格分隔 在 1 行输出。但是,必须满足以下限制。
1 ≦ a, b ≦ 1,000,000,000
入力例1
1
出力例1
1 1
入力例2
3
出力例2
4 5
入力例3
12
出力例3
314159265 358979323
对于每个输入/输出示例,都有许多其他满足条件的输出。