每一个正整数都可以表示为若干个斐波那契数的和，一个整数可能存在多种不同的表示方法，例如：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
#include <bits/stdc++.h> using namespace std; #define ll long long #define F(i,a,b) for(int i=a;i<=b;++i) #define R(i,a,b) for(int i=a;i<b;++i) #define mem(a,b) memset(a,b,sizeof(a)) int t; ll n; ll f[101],A[101]; void init() { A[2]=A[1]=1; f[1]=f[2]=1; F(i,3,84) { f[i]=f[i-1]+f[i-2]; A[i]=A[i-1]+A[i-2]+f[i-2]; } } ll solve(int id,ll num) { if(f[id]==num) return A[id]; if(f[id-1]>=num) return solve(id-1,num); return A[id-1]+num-f[id-1]+solve(id-2,num-f[id-1]); } int main() { init(); for(scanf("%d",&t);t--;) { scanf("%lld",&n); ll sum=0,ans=0; int id=0; while(sum+f[id+1]<n) sum+=f[++id]; F(i,1,id) ans+=A[i]; ans+=solve(id+1,n-sum); printf("%lld\n",ans); } return 0; }
不是太明白，贴了一下别人的代码供以后学习