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示例

3
1
3
6

 

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;
}