辗转数对

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
© 2015 HUST ACMICPC TEAM. All Right Reserved.