假设有一个数对 (a,b)(a, b)(a,b)。一步之内,我们可以把它变成 (a+b,b)(a+b, b)(a+b,b) 或 (a,a+b)(a, a+b)(a,a+b)。
初始数对是 (1,1)。你的任务是求出最小的步数 kkk,使得 (1,1) 能经过 kkk 步变成一个至少有一个数等于 nnn 的数对。
输入只包含一个整数 nnn(1≤n≤1061 \le n \le 10^61≤n≤106)。
输出一个整数 kkk。
5
3
1
0
数对 (1,1) 可以经三步变成含 5 的数对:(1,1) → (1,2) → (3,2) → (5,2)。
登录后提交代码,查看评测结果并记录练习进度。
注册一个 d&f算法网 通用账户,您就可以在我们提供的所有在线评测服务上提交代码、参与讨论。
使用您的 d&f算法网 通用账户