更相减损术

题目描述

对于一个数字对(a, b)，我们可以通过一次操作将其变为新数字对(a+b, b)或(a, a+b)。

给定一正整数n，问最少需要多少次操作可将数字对(1, 1)变为一个数字对，该数字对至少有一个数字为n。

输入格式

第一行一个正整数 n

输出格式

一个整数表示答案。

输入输出样例

输入 #1

1

5

输出 #1

1

3

说明/提示

样例解释：

(1,1)  →  (1,2)  →  (3,2)  →  (5,2)

对于30%的数据， 1 <= n <= 1000

对于60%的数据， 1 <= n <= 20000

对于100%的数据，1 <= n <= 10^6

解析

先手玩一下样例，发现式子是这样的：

反过来写

这个不是。。。更相减损术？

所以题目就转化成了：找到一个数字对 使得 gcd(n, a) 进行更相减损的次数最小。

考虑枚举 ，上界怎么确定？

手玩的时候顺便发现从 分出的两条分支是对称的，那么超出 的枚举是没有必要的，所以

每一次 gcd 传下去的参数都是 b,a mod b，更相减损了 次， 每次步数要加上这个数；
最后如果 ，那么步数要另加上 （从 转移到 需要 步）；
最后如果 那就无解，直接 return inf 别让答案更新就好

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

//
// Created by HandwerSTD on 2019/11/1.
// Copyright (c) 2019 HandwerSTD. All rights reserved.
// Title: 数字对
//
// sto Qingyu orz
// 感谢真神sqy无私的教诲。膜时队者处处阿克，只因大师sqy在他背后。不膜大师者违背了真神的旨意，真神必将降下天谴，
// 使其天天爆零
// 我不由自主地膜拜真神sqy。
//

#include <cstdio>
#include <algorithm>

int n, ans = 0x7f7f7f7f;

int gcd(int a, int b) {
    if (b == 1) return a - 1;
    if (b == 0) return 0x7f7f7f7f;
    return a / b + gcd(b, a % b);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        ans = std::min(ans, gcd(n, i));
    }
    printf("%d\n", ans);
    return 0;
}