转载自：five20,转载请注明出处
本来看到这题，蒟蒻是真心没有把握的，还是five20大佬巨orz
首先由于斐波拉契数的前两项是1,1 ，所以易得对于任何整数必能写成多个斐波拉契数加减的形式。
对于一个数x ，我们贪心找到与x 差值最小的斐波拉契数，将新的x 赋为差值，每次进行这个操作，统计次数，直到x 为0 为止，输出次数。
证明上述过程也很简单：由于我们知道任何整数必能写成多个斐波拉契数加减的形式，所以我们显然使xx 每次变得越小越好（即减的越多越好），因为每个斐波拉契数都等于前面两项的和，所以我们完全没必要将一步操作改为两步操作。
举个例子：当n=8 ，答案是1 （即8=8 ，8 为第6项），而我们不需要将前面的3,5 什么的记录进去，因为这样会多1 步操作。当n=11 ，答案是2 （即11=8+3 或11=13−2 ），显然不用将8 拆为更小的斐波拉契数之和，也不用将13 拆为更小的斐波拉契数之和，这样必然会徒增次数。
那么具体实现时，直接预处理斐波拉契数，然后对于每次询问，二分出第一个大于等于该值的位置p ，然后第一个小于该值的值位置p−1 ，则x=min(f[p]−x,x−f[p−1]) 。
Code：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
using namespace std;
typedef long long ll;
int n,tot;
ll m,f[];
int main()
{
ios::sync_with_stdio(false);
cin>>n;
f[]=f[]=;
for(int i=;i<=;i++)
f[i]=f[i-]+f[i-];
for(int t=;t<=n;t++){
cin>>m;tot=;
while(m){
ll p=lower_bound(f,f+,m)-f;
ll q=p-;
m=min(m-f[q],f[p]-m);
tot++;}
cout<<tot<<endl;
}
return ;
}