** 题目传送门**
本题没有样例，这里随便先给四个样例供各位测试，一个正常样例，两个特殊样例，一个大样例：
样例1：
30， 3
样例2：
13， 1
样例3：
1， 1
样例4：
314159265， 11
都能过就差不多了
看到“同一个数可以使用多次”就可以推测出这题是贪心了。
不然的数据你也不好，再说这道题很明显就具备贪心选择性。
这道题可以直接推出来斐波那契数列，反正复杂度不高。
不过既然斐波那契数列递推不是很麻烦，所以可以提前打表，避免毒瘤出题人出的卡常数优化的数据。
虽然这道题不需要表，但这是一个技巧，考试可以用到。
所以先贴上打表代码：
#include<bits/stdc++.h>
using namespace std;
long long f[65];
int main(){
f[0]=f[1]=1;
printf("1,1,");
for(register int i=2;i<65;++i){
f[i]=f[i-1]+f[i-2]; //斐波那契递推公式
printf("%lld,",f[i]);
}
return 0;
}
把表运行一下，简单整理即可
现在来处理贪心策略：
既然我要让最终结果，也就是选的数量尽量少，该怎么办呢？
结论是：每次选择中选数字尽量大的。
本来这里想写我不会证的，本着做良心题解的观念，我摸索出了大致的证明：
证明：
首先直接上：
齐肯多夫定理表示任何正整数都可以表示成若干个不连续的斐波那契数（不包括第一个斐波那契数）之和。这种和式称为齐肯多夫表述法。
齐肯多夫表述法可以通过贪心得到：每次选最大的。
现在证明为什么这样是个数最小的：
假设有两个数相邻：
直接 合并。
所以不是齐肯多夫表述法的分解方法一定不是最小的。
继续证……
假设一个斐波那契数，在不超过的斐波那契数中选若干不连续的，最大和是多少呢？
举个例子，。在里面怎么选呢？当然是。
这是一个简单的结论，在不超过的斐波那契数中选若干不连续的，最大和是
所以一个数，我想找到它的种齐肯多夫表述法，现已用贪心找到一种。
假设贪心出来要分，但我不想分，那么剩下的分法中，最大和是？
当然是。
这一坨加起来是。
所以如果我不分出，随我怎么分我也凑不出一个。
到这里我们证了一个推论：齐肯多夫分解是唯一的。
而刚刚我们还证出不是齐肯多夫表述法的分解方法一定不是最小的。
所以得出结论了，齐肯多夫表述法的分解方法一定是最小的，而且是唯一的。
这个齐肯多夫表述法怎么来的？看看上文……
用贪心，每次选最大的。
得证：每次选最大的数的策略一定可以得到最少的分解数字数量。
那么找到比小（或相等）的最大的斐波那契数，顺序查找、二分、STL……都可以解决。
既然其他题解都是顺序查找，那我上一个代码吧，顺带练习二分。
inline int bs(){
int l=0,r=64; //待会解释为什么是0和64
while(l<=r){
int m=(l+r)>>1; //位运算，等价于（l+r）/2
if(f[m]<=a && f[m+1]>a) return m;
if(f[m]<=a) l=m+1;
else r=m-1;
}
}
（注意：代码不完整，缺少快读快写函数和那张超级丑的表）
#include<bits/stdc++.h> //万能头，CSP可以用，亲测
using namespace std;
// 省去快读快写函数
long long a;// 省去表
int n,s;
inline int bs(){
int l=0,r=64; //0和64分别为数组的首项与末项下标
while(l<=r){
int m=(l+r)>>1;
if(f[m]<=a && f[m+1]>a) return m;
if(f[m]<=a) l=m+1;
else r=m-1;
}
}
// 二分，不熟练者可以请教神犇或者直接百度
int main(){
a=read(); //已经很少遇见如此简单的输入了
while(a>0){
n=bs(); // 二分找到小于等于 a 的最大的斐波那契数是第几项
a-=f[n]; // 贪心，直接减不用管
s++; //统计我选了几个数
}
write(s),putchar('\n');
// 不要忘记AT的题目在末尾要输出一个换行，不然会WA
return 0;
}
结果：AC，全部 1ms。
题解修改史：
updata： 修改了一个错别字和部分句子
updata：（深夜）题解审核失败，原因【排版不整齐】，修改了题解部分内容
再次丑拒，放弃本题。
updata： 抱着最后一丝希望，重构题解，提交……
