#P2090. 数字对
数字对
题目描述
对于一个数字对(a, b),我们可以通过一次操作将其变为新数字对(a+b, b)或(a, a+b)。
给定一正整数n,问最少需要多少次操作可将数字对(1, 1)变为一个数字对,该数字对至少有一个数字为n。
输入格式
第一行一个正整数 n
输出格式
一个整数表示答案。
5
3
提示
样例解释:
(1,1) → (1,2) → (3,2) → (5,2)
对于30%的数据, 1 <= n <= 1000
对于60%的数据, 1 <= n <= 20000
对于100%的数据,1 <= n <= 10^6