题目：

题目来源： Project Euler
基准时间限制： 1 秒 空间限制： 131072 KB 分值: 40 难度：4级算法题

每一个正整数都可以表示为若干个斐波那契数的和，一个整数可能存在多种不同的表示方法，例如：14 = 13 + 1 = 8 + 5 + 1，其中13 + 1是最短的表示（只用了2个斐波那契数）。定义F(n) = n的最短表示中的数字个数，F(14) = 2，F(100) = 3（100 = 3 + 8 + 89），F(16) = 2（16 = 8 + 8 = 13 + 3）。定义G(n) = F(1) + F(2) + F(3) + ...... F(n)，G(6) = 1 + 1 + 1 + 2 + 1 + 2 = 8。给出若干个数字n，求对应的G(n)。
Input 
第1行：一个数T，表示后面用作输入测试的数的数量（1 <= T <= 50000)。
第2 - T + 1行：每行1个数n(1 <= n <= 10^17)。
Output 
输出共T行：对应每组数据G(n)的值。
Input示例 
3
1
3
6
Output示例 
1
3
8
对于这种题目，个人认为首先看数据，n为10的17次方的话，明显是规律题，首先想到的应该是打表看看是否能够找到对应关系
我借用excel将打表的到的数据整理然后找到了规律，G(n)的排列显然是有规律的，他是按照斐波那契数列对应的数分层，第一层是G(1)(只有一个数)，第二层是G(2)(只有一个数)，第三层是G(3)、G(4)(两个数)，第四层三个数，第五层五个数，第六层八个数......依次类推
而其规律是后一层的G(n)共有fib(n)个的话，G(n)的前fib(n-1)个与之前一层完全相同，后fib(n)-fib(n-1)个等于前一层前fib(n)-fib(n-1)个对应的数加一，规律就是这样，然后直接写码就OK。
AC代码:
#include<cstdio>
using namespace std;
typedef long long ll;
ll fib[90],g[90];
//第90个斐波那契数约为3*10^20；
void init()
{
    fib[0]=fib[1]=1;
	g[0]=g[1]=1;
	for(int i=2;i<90;i++)
	{
		fib[i]=fib[i-1]+fib[i-2];
		g[i]=g[i-1]+g[i-2]+fib[i-2]-1;
	}
}//对fib和g进行打表
ll fibb(ll n)
{
	int res;
	for(int i=0;i<90;i++)
    {
        if(fib[i]>=n)
		{
			res=i;
			break;
		}
    }
	if(fib[res]==n)
		return g[res];
	res--;
	return g[res]+fibb(n-fib[res])+n-fib[res];
}//计算最后n-fib(res)的数目，然后与前面的相加
int  main()
{
	int T,i;
	ll n;
	init();
	scanf("%d",&T);
	while(T--)
	{
		scanf("%lld",&n);
		printf("%lld\n",fibb(n));
	}
    return 0;
}