自动搬运

查看原文

来自洛谷，原作者为

	SunnyLi 大切な人と、いつかまた巡り会えますように

搬运于2025-08-24 22:40:52，当前版本为作者最后更新于2023-04-22 08:18:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目传送门

看到几个大佬的题解，深感数学不行。本蒟蒻就来发一个小学生都能看懂的找规律题解。

思路

我们假设开始时有 $t$ 个机器人。我们记 $f(x)$ 为 $x$ 年后的机器人个数，然后我们开始尝试前几项：

$$\begin{aligned} f(1) &= t+(2t-1) &= 3t-1 \\ f(2) &= 3t-1+(2(2t-1)-1) &= 7t-4 \\ f(3) &= 7t-4+(2(4t-3)-1) &= 15t-11 \\ f(4) &= 15t-11+(2(8t-7)-1) &= 31t-26 \\ f(5) &= 31t-26+(2(16t-15)-1) &= 63t-57 \\ \cdots \end{aligned} $$

我们先看结果含 $t$ 的一次项：

$3t\quad7t\quad15t\quad31t\quad63t\cdots$

取他们系数的差可以发现，差的数列为：

$4\quad8\quad16\quad32\cdots$

又因为 $3=1+2$，我们记 $A(x)$ 为一次项系数，$x$ 为过去的时间，可以得到以下关系：

$$A(x)=1+2+4+\cdots+2^x=2^{x+1}-1$$

接下来看常数项：

$1\quad4\quad11\quad26\quad57\cdots$

取差：

$3\quad7\quad15\quad31\cdots$

有没有觉得很眼熟，这就是一次项系数的规律。

所以我们记 $B(x)$ 为常数项，$x$ 为所过的时间，可以得到以下关系：

$$B(x)=\sum^{x}_{i=1}A(i-1)$$

当然 $B(0)$ 是特例，$B(0)=0$。

现在我们来计算一下 $B(x)$ 的通项公式：

$$\begin{aligned} B(x) &= \sum^{x}_{i=1}A(i-1)\\ &= A(0)+A(1)+\cdots+A(x-1)\\ &= (2^1-1)+(2^2-1)+\cdots+(2^{x}-1)\\ &= (2^{x+1}-2)-x\\ \end{aligned} $$

所以基本上就大功告成了！

所以 $n$ 年后的机器总数为：

$$\begin{aligned} s &= A(n)t+B(n)\\ &= (2^{n+1}-1)t-[(2^n-2)-n]\\ &= 2^{n+1}t-t+n-2^{n+1}+2\\ &= (2^{n+1}-1)(t-1)+t+1\\ \end{aligned}$$

把它化简表示为 $t$ 的函数形式，易得

$$t=\frac{s-n-1}{2^{n+1}-1}+1$$

最后看到样例二的那一大串数字 $2218388550399401452619230609499$，我们肯定要用高精度。作为一个蒟蒻，高精度肯定用 Python 啦！

AC 代码

#Python代码
from math import pow
n,s = input().split(" ")
n,s = int(n),int(s)
print(str(int((s-n-1)/(int(pow(2,n+1))-1)+1)))

AC 记录