ACM模版

描述

提解

这道题，解法十分巧妙，思路不是自己想起来的，对斐波那契数列的性质不够了解，在相关讨论中找到一个ID为@wc的大牛的思路，然后实现了一下，大牛思路如下：

斐波那契数列定义为 f[0]=f[1]=1, f[i]=f[i-1]+f[i-2] (i>=2) 只需打表前90项
从f[i]开始的连续f[i-1]项 的最短表示F[t] 是有规律的。
其前f[i-2]项和 从f[i-1]开始的连续f[i-2]项相等，其后f[i-3]项为 从f[i-2]开始的连续> f[i-3]项 每项+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;

根据这个规律定义A[i]为 从f[i]开始的连续f[i-1]项 的最短表示F[t] 的和，也就是 A[i]=G[f[i+1] -1]-G[f[i]-1]
易知，A[1]=A[2]=1，A[i]=A[i-1]+A[i-2]+f[i-3]

然后就是XJB搞了

（大牛们说话比较粗犷，习惯就好了）

这个思路把前半段解题思路给的十分详细，但是最后直接省略了，最后的这个可能不够整段的序列，着实难住我了，经过观察数列，发现这又和斐波那契数列的性质相关，具体是什么不好形容，看代码吧，我用while循环实现的。

另外附一篇代码，是相同思路的另外一种表现形式，定义的数组有些不同而已。

代码

One：

#include <iostream>
#include <cstdio>

using namespace std;

const int MAXN = 90;

long long Fib[MAXN] = {
  1, 1};
long long A[MAXN] = {
  0, 1, 1};

void init()
{
    for (int i = 2; i < MAXN; i++)
    {
        Fib[i] = Fib[i - 1] + Fib[i - 2];
    }
    for (int i = 3; i < MAXN; i++)
    {
        A[i] = A[i - 1] + A[i - 2] + Fib[i - 3];
    }
    return ;
}

int main(int argc, const char * argv[])
{
    init();

    int T;
    cin >> T;

    long long n;
    while (T--)
    {
        long long ans = 0;
        scanf("%lld", &n);
        for (int i = 1; i < MAXN; i++)
        {
            if (Fib[i] + Fib[i - 1] - 1 <= n)
            {
                ans += A[i];
            }
            else
            {
                long long sur = n - Fib[i] + 1;
                while (sur)
                {
                    for (i--; i >= 1; i--)
                    {
                        if (Fib[i - 1] <= sur)
                        {
                            sur -= Fib[i - 1];
                            ans += A[i] + sur;
                            break;
                        }
                    }
                }
                break;
            }
        }
        printf("%lld\n", ans);
    }

    return 0;
}

Two：

#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 90;

ll f[MAXN], g[MAXN];

ll F(ll n)
{
    int x;
    x = (int)(lower_bound(f, f + MAXN, n) - f);
    if (f[x] == n)
    {
        return g[x];
    }
    x--;
    return g[x] + F(n - f[x]) + n - f[x];
}

int main()
{
    ll n;
    int i, T;

    f[0] = f[1] = 1;
    g[0] = g[1] = 1;
    for (i = 2; i < MAXN; i++)
    {
        f[i] = f[i - 1] + f[i - 2];
        g[i] = g[i - 1] + g[i - 2] + f[i - 2] - 1;
    }

    scanf("%d", &T);
    while (T--)
    {
        scanf("%lld", &n);
        printf("%lld\n", F(n));
    }

    return 0;
}