1588 - 辗转数对
Time Limit : 1 Second
Memory Limit : 128 MB
Submission: 161
Solved: 28
- Description
- 假设当前有一个数对(a, b)，我们可以通过一步将这个数对变为一个新数对(a + b, b)或者是(a, a + b)。
初始的数对为(1, 1)，你的任务是找到一个数字k，即通过最少的步数使得这个数对中至少一个数字等于n。
- Input
- 输入包括多组数据，每组数据包括一行，每行有一个整数n。
- Output
- 每组数据输出一行，每行一个整数n。
- sample input
-
5 3
- sample output
-
3 0
- hint
- 第一个样例的方法是 (1,1) → (1,2) → (3,2) → (5,2)，共3步。
- source