洛谷P2090《数字对》

更相减损术

题目描述

对于一个数字对(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

解析

先手玩一下样例,发现式子是这样的:

$(a,b) \leftarrow (a’ + b, b)$

反过来写

$(a’,b) \rightarrow (a - b, b)$

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


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

考虑枚举 $a$,上界怎么确定?

手玩的时候顺便发现从 $(1,1)$ 分出的两条分支是对称的,那么超出 $n$ 的枚举是没有必要的,所以 $1\leq a \leq n$


每一次 gcd 传下去的参数都是 b,a mod b,更相减损了 $\lfloor {a \over b} \rfloor$ 次, 每次步数要加上这个数;
最后如果 $b = 1$,那么步数要另加上 $a - 1$ (从 $(1,1)$ 转移到 $(a,1)$ 需要 $a - 1$ 步);
最后如果 $b = 0$ 那就无解,直接 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;
}