题目描述
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;
}
