AT_tenka1_2012_final_a ぶんたん

斐波那契数列是由以下递推式定义的数列 $F_0, F_1, F_2, \ldots$（即 $0, 1, 1, 2, 3, 5, 8, 13, \ldots$），其中斐波那契数是该数列中出现的数 $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 \leq N \leq 10^5$）给出正确答案，将获得满分 $100$ 分中的 $50$ 分的部分分数。 请输出能够表示成正整数 $n$ 的斐波那契数的个数的最小可能值，输出一行。 行末需要换行符。

一行一个正整数 $n$。

输出一行，表示能够表示成正整数 $n$ 的斐波那契数的个数的最小可能值。

由 ChatGPT 4.1 翻译