Nowcoder 105D Fibonacci 进制 (数论)

题目描述

Fibonacci 数是非常有名的一个数列,它的公式为 $f(n)=f(n-1)+f(n-2),f(0)=1,f(1)=2$ 。

我们可以把任意一个数 $x$ 表示成若干不相同的 Fibonacci 数的和,比如说 $14 = 13+1 = 8+5+1 = 8+3+2+1$。

如果把 Fibonacci 数列作为数的位权,即 $f(i)$ 作为第 $i$ 位的位权,每位的系数只能是 $0$ 或者 $1$ ,从而得到一个 $01$ 串。比如 $14$ 可以表示成 $100001,11001,10111$ 。 我们再把这个 $01$ 串看成 $2$ 进制,再转成 $10$ 进制以后就变成了 $33,25,23$ 。为了避免歧义,我们将使用最小的那个值 $23$ 。

请按照这个过程计算一下 $10$ 进制整数通过上述转换过程得到的 $10$ 进制整数。

 

输入描述

第一行是一个整数 $T(1 ≤ T ≤ 10000)$ ,表示样例的个数。

以后每行一个样例,为一个十进制正整数 $x(1 ≤ x ≤ 10^9)$ 。

 

输出描述

每行输出一个样例的结果。

 

输入

5
1
10
100
1000
1000000000

 

输出

1
14
367
10966
4083305275263

 

思路

因为我们要让这一个数 $x$ 表示的最终结果最小,所以要将他展开的越彻底越好(注意不能出现相同的斐波那契数)

最好的情况下 $x$ 刚好可以表示为前 $k$ 项的斐波那契数的和减一(因为标准的斐波那契数列前面有两个重复的 $1$ )

于是我们有:
$$
x=(\sum_{i=1}^{k}Fibonacci[i])-1
$$
根据斐波那契数列的性质我们还有:
$$
\sum_{i=1}^{n}Fibonacci[i]=Fibonacci[n+2]-1
$$
因此得出:
$$
x=Fibonacci[k+2]-2
$$
等价于:
$$
x+2=Fibonacci[k+2]
$$
打表得出 $10^9$ 以内所有的斐波那契数,然后二分求出一个 $k$ 使得 $Fibonacci[k+2]≥x+2$ 。

  • 对于特殊的情况( $Fibonacci[k+2]=x+2$ ):显然此时的答案等于 $2^k-1$
  • 对于一般的情况( $Fibonacci[k+2]>x+2$ ):我们需要从中去除可以组合出 $Fibonacci[k+2]-(x+2)$ 的极大项(常识不加解释),最终所剩余的部分便是这道题的答案

 

AC 代码

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

LL f[52] = {
    1,          1,           2,           3,           5,          8,
    13,         21,          34,          55,          89,         144,
    233,        377,         610,         987,         1597,       2584,
    4181,       6765,        10946,       17711,       28657,      46368,
    75025,      121393,      196418,      317811,      514229,     832040,
    1346269,    2178309,     3524578,     5702887,     9227465,    14930352,
    24157817,   39088169,    63245986,    102334155,   165580141,  267914296,
    433494437,  701408733,   1134903170,  1836311903,  2971215073, 4807526976,
    7778742049, 12586269025, 20365011074, 32951280099,
};

void solve(LL x) {
    LL now = lower_bound(f, f + 52, x + 2) - f;
    LL cha = f[now] - x - 2;
    now = (1LL << (now - 2)) - 1;
    while (cha > 0) {
        LL sn = upper_bound(f, f + 52, cha) - 1 - f;
        now &= ~(1LL << (sn - 1));
        cha -= f[sn];
    }
    cout << now << endl;
}

int main() {
#ifdef LOCAL_IM0QIANQIAN
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#else
    IO;
#endif // LOCAL_IM0QIANQIAN
    int T;
    cin >> T;
    while (T--) {
        LL x;
        cin >> x;
        solve(x);
    }
    return 0;
}