B3752 题解

思路

普通的斐波那契数列递推公式为：

F(n)=F(n-1)+F(n-2)

同理，放到本题的“新斐波那契数列”中即为：

f_a(n)=F(n-2)\times a+F(n-1)

由于给定

f_a(n)=x

，将

x

代入，解得：

a=\frac{x-F(n-1)}{F(n-2)}

令

M

为斐波那契数列的长度（即至少需要几个数使

F_M>x

）。枚举

N

，若

x-F(n-3)

是

F(n-2)

的倍数，就输出

N

和

\frac{x-F(n-3)}{F(n-2)}

。

AC CODE

CPP

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=105;
int f[N];
int main(){
	int T=read();
	while(T--){
		int x=read();
		f[0]=f[1]=1;
		int m=2;
		while(f[m-1]+f[m-2]<=x)
			f[m]=f[m-1]+f[m-2],++m;
		printf("2 %d\n",x);
		for(int i=3;i<=m;++i)
			if((x-f[i-3])%f[i-2]==0&&(x-f[i-3])/f[i-2]>=1)
				printf("%d %d\n",i,(x-f[i-3])/f[i-2]);
	}
	return 0;
}

文章操作

思路

相关推荐

评论

B3752 题解