← 返回题目列表

AtCoder · arc051_b

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 。

制約

  • 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

对于每个输入/输出示例,都有许多其他满足条件的输出。