ぶんたん
题意翻译
## 题目大意:
读入一个正整数$ n $(1<=$ n$<=$10^{10}$).
$ n $表示为$ k $个斐波纳契数的总和。
同一个斐波那契数可以使用多次。
问:$ k $最小是多少?
题目描述
[problemUrl]: https://atcoder.jp/contests/tenka1-2012-final/tasks/tenka1_2012_final_a
フィボナッチ数列は、以下のような漸化式で表される数列 $ F_0,\ F_1,\ F_2,\ …\ (=0,\ 1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ …) $ であり、フィボナッチ数はこの数列に現れる数 $ F_i\ (i\ \geq\ 0) $ です。
- $ F_{0}\ =\ 0 $
- $ F_{1}\ =\ 1 $
- $ F_{i+2}\ =\ F_{i}\ +\ F_{i+1} $ ($ i\ \geq\ 0 $)
ある正整数 $ n $ をいくつかのフィボナッチ数の和として表すことを考えます。
このとき、和が正整数 $ n $ となるフィボナッチ数の個数として考えられる最小の値を答えなさい。
ただし、同じフィボナッチ数を複数回用いることもできるものとし、複数回用いた場合はそれぞれ別々に数えるものとします。
入力は以下の形式で標準入力から与えられる。 > $ n $
- 正整数 $ n $ ($ 1\ \leq\ n\ \leq\ 10^{10} $) が $ 1 $ 行で与えられる。
与えられる数が小さい入力 ($ 1\ \leq\ N\ \leq\ 10^5 $) のみ正解すると、$ 100 $ 点満点に対して部分点として $ 50 $ 点が与えられる。 和が正整数 $ n $ となるフィボナッチ数の個数として考えられる最小の値を $ 1 $ 行で出力せよ。
なお、行の終端には改行が必要である。