Pairs of Numbers

## 【题目描述】 让我们假设有一对数$(a,b)$。我们可以从前一步得到后一对数$(a+b,b)$或者$(a,a+b)$。 让我们规定一开始这对数为$(1,1)$。你的任务就是找到数$k$，使$k$为从$(1,1)$转换到一对至少含有一个$n$的数对的最少步骤。 ## 【输入格式】 输入只包括一个整数$n(1<=n<=10^6)$。 ## 【输出格式】 输出唯一的整数$k$。

重题请做P2090

Let's assume that we have a pair of numbers ( $ a,b $ ). We can get a new pair ( $ a+b,b $ ) or ( $ a,a+b $ ) from the given pair in a single step. Let the initial pair of numbers be (1,1). Your task is to find number $ k $ , that is, the least number of steps needed to transform (1,1) into the pair where at least one number equals $ n $ .

The input contains the only integer $ n $ ( $ 1<=n<=10^{6} $ ).

Print the only integer $ k $ .

5

3

1

0

The pair (1,1) can be transformed into a pair containing 5 in three moves: (1,1) $ → $ (1,2) $ → $ (3,2) $ → $ (5,2).