51nod-斐波那契表示（找规律）

第1行：一个数T，表示后面用作输入测试的数的数量（1 <= T <= 50000)。第2 - T + 1行：每行1个数n(1 <= n <= 10^17)。Output
输出共T行：对应每组数据G(n)的值。Input示例
3136Output示例
138李陶冶 (题目提供者)题目浅显易懂，n很大，呢就是硬着头皮找规律了，这道题的规律不好一眼看出，甚至在纸上表示出前10项也没看先端倪，搜了一发题解，发现仍是规律，不过比较难看出，因此直接采用了结论。这里只是简单较少下结论好了。首先需要说的是一个数能用最少的斐波那契数表示的话一定包括当前能组成该数的最大斐波那契数，想到这里，剩下的就是简单打表找规律了for example ：i=6时的fib[i]=13,从13开始的fib[i-1]项的最少斐波那契数为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]
#include<stdio.h>#include<algorithm>using namespace std;#define maxn 90typedef long long ll;ll fib[maxn],g[maxn];ll work(ll n){	int x;	for(int i=0;i<maxn;i++)		if(fib[i]>=n)		{			x=i;			break;		}	if(fib[x]==n)		return g[x];	x--;	return g[x]+work(n-fib[x])+n-fib[x];}int  main(){	int T,i;	ll n;	fib[0]=fib[1]=1;	g[0]=g[1]=1;	for(i=2;i<maxn;i++)	{		fib[i]=fib[i-1]+fib[i-2];		g[i]=g[i-1]+g[i-2]+fib[i-2]-1;	}	scanf("%d",&T);	while(T--)	{		scanf("%lld",&n);		printf("%lld/n",work(n));	}}