51nod 1350 斐波那契表示（数学）

Description

每一个正整数都可以表示为若干个斐波那契数的和，一个整数可能存在多种不同的表示方法，例如：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示例

Output示例

1
3
8

思路

搞清楚斐波那契数列表示的本质这道题目就会变得非常简单。

其递推式： $f_0=f_1=1,f_i=f_{i-1}+f_{i-2}~(i>=2)$

显然，对于一个斐波那契数来说，$F_i=1$ ，否则它一定存在于两个斐波那契数之间，对于这样的数，它的最短表示一定和它之前的若干个斐波那契数有关。

有这样一个规律：

比如，当 i=6 时，13 开始的连续 8 项，即 F[13],F[14],F[15]……F[20] 为 1，2，2，2，3，2，3，3

前 5 项正好和 F[8],F[9],F[10],F[11],F[12] 一样

后 3 项为 F[5]+1,F[6]+1,F[7]+1

我们定义， $s_i$ 表示从 $f_i$ 开始的连续 $f_{i-1}$ 项的最短表示之和。

则 $s_i=s_{i-1}+s_{i-2}+f_{i-3}$ ，其中 $s_1=s_2=1$ 。

剩下的根据规律随便写写就可以了。

AC 代码

#include<bits/stdc++.h>
#define IO ios::sync_with_stdio(false);\
    cin.tie(0);\
    cout.tie(0);
using namespace std;
const int maxn = 88;
typedef long long LL;

LL f[maxn],s[maxn];

void init()
{
    f[0] = f[1] = 1;
    for(int i=2; i<maxn; i++)
        f[i] = f[i-1] + f[i-2];
    s[0] = s[1] = s[2] = 1;
    for(int i=3; i<maxn; i++)
        s[i] = s[i-1] + s[i-2] + f[i-3];
}

LL sear(int o,LL step)
{
    if(step<=0)return 0;
    if(o<=2)return 1;
    if(step==f[o-1])return s[o];
    return sear(o-1,min(f[o-2],(LL)step)) + sear(o-2,step-f[o-2]) + (step-f[o-2]>0?step-f[o-2]:0);
}

int main()
{
    IO;
    init();
    int T;
    cin>>T;
    while(T--)
    {
        LL n;
        cin>>n;
        LL ans = 0;
        int tmp = upper_bound(f,f+maxn,n)-f-1;
        for(int i=1; i<tmp; i++)
            ans+=s[i];
        cout<<ans + sear(tmp,n-f[tmp]+1)<<endl;
    }
    return 0;
}