题解：B3752 [信息与未来 2019] 新斐波那契数列

LoongPig · 2025-03-15 12:48:40 · 题解

题目传送门

题目思路

我们可以设传统的斐波那契数列第 n 项为 f(n)。

则新斐波那契数列的通项公式可以表示为：

然后我们要求的就变成了对于新斐波那契数列的某一项 x，解方程：

且 x\geq f(n-2)，f(n-1)\mid (x-f(n-2))，a\geq 1。

代码实现

首先，预处理传统的斐波那契数列；

然后，特殊处理 n=2，因为根据定义 f_a(2)=a，直接得到解 (2,x)；

最后，枚举 n 的值，如果对应的 a 合法，那么就输出这个解。

题目标程

#include <bits/stdc++.h>
using namespace std;
int fib[50] = {0, 1, 1};//传统斐波那契数列
void init() {
    //预处理
    for (int i = 3; i <= 50; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
}
int main() {
    init();
    int T;
    scanf("%d", &T);
    while (T--) {
        int x;
        scanf("%d", &x);
        int m = 2;
        while (fib[m] <= x) {
            m++;
            //求出 n 的范围
        }
        printf("%d %d\n", 2, x);
        //输出特殊解
        for (int i = 3; i < m; ++i) {
            int t = x - fib[i - 2];
            if (t > 0 && fib[i - 1] != 0 && t % fib[i - 1] == 0) {
                //判断对应的 a 是否合法
                int a = t / fib[i - 1];
                if (a >= 1) {
                    printf("%d %d\n", i, a);
                }
            }
        }
    }
    return 0;
}