← 返回题目列表

AtCoder · tenka1_2012_final_a

A. 文丹

中文机器翻译题面 查看原题

問題文

fi 佛纳奇数列是以下递推公式表示的数列 F_0,\ F_1,\ F_2,\ …\ (=0,\ 1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ …) ,fi 佛纳奇数是出现在这个数列中的数 F_i\ (i \geq 0) 。

  • F_{0} = 0
  • F_{1} = 1
  • F_{i+2} = F_{i} + F_{i+1} (i \geq 0)

某个正整数 n ,考虑将其表示为若干 fi 佛纳奇数的和。
此时,作为和为正整数 n 的 fi 佛纳奇数的个数所能取的最小值。
但是,同一个fi斐波那契数也可以使用多次,每次使用都单独计算。


入力

输入是按以下格式从标准输入给出的。
n
  • 正整数 n (1 \leq n \leq 10^{10}) 是 1 行中给出。

部分点

给定的数较小的输入 (1 \leq N \leq 10^5) 是正确的,那么100 部分积分换满分 50 点。 如果您正确回答了所有满足

出力

和为正整数 n 被认为是fi斐波那契数的个数所能达到的最小值 1 行。
请注意,行尾需要换行。 定义

入力例 1

10

出力例 1

2
    10 是最小的 5 ,\ 5 可以得到第 2 可以表示为由最少个fi斐波那契数的和。

入力例 2

11

出力例 2

2
    11 是最小的 3 ,\ 8 可以得到第 2 可以表示为由最少个fi斐波那契数的和。

入力例 3

10000000000

出力例 3

16