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

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

3136

Output示例

138

思路

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

其递推式： f0=f1=1,fi=fi−1+fi−2 (i>=2)

显然，对于一个斐波那契数来说，Fi=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

我们定义， si 表示从 fi 开始的连续 fi−1

则 si=si−1+si−2+fi−3 ，其中 s1=s2=1

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

AC 代码

#include#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; i0?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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。