TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3862
  • 题目
  • P3862数字对
    限制 : 时间限制 : - MS   空间限制 : 265536 KB
    评测说明 : 1s
    问题描述

    对于一个数字对(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