B3752 题解

getchar_unlocked · 2025-03-16 19:03:37 · 题解

题目传送门

思路

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

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

由于给定 f_a(n)=x，将 x 代入，解得：

令 M 为斐波那契数列的长度（即至少需要几个数使 F_M>x）。枚举 N，若 x-F(n-3) 是 F(n-2) 的倍数，就输出 N 和 \frac{x-F(n-3)}{F(n-2)}。

AC CODE

#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;
}