自动搬运

查看原文

来自洛谷，原作者为

	LoongPig 人生中最大的遗憾，不是努力了没有成功，而是从未尝试过努力||发接龙拉黑

搬运于2025-08-24 21:14:49，当前版本为作者最后更新于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;
}