题面传送门

分析题目

这道题目描述了一个特殊的赚钱序列：

第一天赚 $p$ 摩拉
第二天赚 $p+1$ 摩拉
从第三天开始，每天赚的钱是前两天赚的钱之和

给定第

a

天赚的钱

x

，问第

b

天能赚多少钱。如果不存在这样的

p

，使得第

a

天赚

x

摩拉，则输出

-1

。

解题思路

序列生成规则：这个序列类似于斐波那契数列，但是前两项是

p

和

p+1

。我们可以预计算所有可能的

a

和

b

组合对应的关系。

推导：对于第

n

天赚的钱，可以表示为关于

p

的式子：f(n) = k[n] * p + c[n]

f(1) = p = 1 * p + 0
f(2) = p + 1 = 1 * p + 1
f(3) = f(1) + f(2) = 2 * p + 1
f(4) = f(2) + f(3) = 3 * p + 2
f(5) = f(3) + f(4) = 5 * p + 3

可以看出系数

k

和

c

都遵循斐波那契数列的规律

预处理系数：我们可以预先计算出对于每个

a

和

b

，对应的

k

和

c

系数，这样在处理查询时可以快速计算。

解方程求

p

：对于给定的

a

和

x

，我们有方程 k[a] * p + c[a] = x。需要解这个方程得到整数

p

且在

1 ≤ p ≤ 10^6

范围内。

验证并计算答案：如果找到合法的

p

，就用这个

p

计算第

b

天的值；否则返回

-1

。

知道了这些，我们就可以开始敲代码了！

代码实现：

CPP

#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int> k(21), c(21);
signed main() 
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	// 预计算系数 k 和c
	k[1] = 1;
	k[2] = 1;
	c[1] = 0;
	c[2] = 1;
	for (int i = 3; i <= 20; i++)
	{
		k[i] = k[i-1] + k[i-2];
		c[i] = c[i-1] + c[i-2];
	}
	int T;
	cin >> T;
	while (T--)
	{
		int a, b, x;
		cin >> a >> x >> b;
		// 解方程 k[a] * p + c[a] = x
		int num1 = x - c[a];
		int num2 = k[a];
		if (num1 <= 0 || num2 == 0)
		{
			cout << "-1\n";
			continue;
		}
		if (num1 % num2 != 0)
		{
			cout << "-1\n";
			continue;
		}
		int p = num1 / num2;
		if (p < 1 || p > 1000000)
		{
			cout << "-1\n";
			continue;
		}
		// 计算第 b 天的值
		int res = k[b] * p + c[b];
		cout << res << '\n';
	}
	return 0;
}

时间复杂度：

预处理 $O(20)$
每个查询 $O(1)$ ， $T$ 次就是 $O(T)$ 所以总复杂度 $O(20*T)$ ，省略常数就是 $O(T)$

不会超时哒

题解：P12036 [USTCPC 2025] 摩拉

文章操作