自动搬运

查看原文

来自洛谷，原作者为

	WYXkk Zzz Zzz

搬运于2025-08-24 22:45:41，当前版本为作者最后更新于2023-03-07 23:06:44，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

观察样例解释，可以得到结论：在完成的前一步，老板来之前，必须有至少 $2$ 个拧好至少 $n-k$ 个螺丝的模块。无论老板收走其中的任何一个，都可以马上拧好另一个。

为了讨论方便，下面继续用 $k=3$ 举例，并假设 $n$ 是很大的数。

而再往前一步呢？再上一步收走后，需要两个分别至少拧好 $n-3,n-6$ 个螺丝的模块，或者 $n-4,n-5$。

老板的最优策略显然是每次收走最大的那个，因此，再上一步收走前，需要三个分别至少拧好 $n-3,n-3,n-6$ 或 $n-4,n-4,n-5$ 个螺丝的模块。

后者需要更少的总螺丝达成，且最大值更小，因此需要准备被老板收走的其它模块需要的螺丝也更少，所以后者优于前者。

再往前一步，用类似的道理，可以证明需要四个分别至少拧好 $n-5,n-5,n-5,n-6$ 个螺丝的模块；再往前一步是 $n-6,n-6,n-6,n-6,n-6$；等等。

这样的状态可以用三元组 $(width,height,remain)$ 表示：总共需要准备 $width$ 个模块，其中每个都需要拧好至少 $height$ 个，而其中 $remain$ 个需要再多一个。

这样取名是因为，状态可以用添加一个不完整的行的矩形来表示：$height$ 行 $width$ 列再加上仅有 $remain$ 个的不完整的一行。

可以参考下面的可视化：

o
o
o
o  oo
o  oo  oo
o  oo  ooo  ooo
o  oo  ooo  oooo  ooooo  ooo

容易发现，每次倒推一步相当于：

• 计算当前总个数
• 减去 $k$ 个
• 平均地重排，多一个的列放在左侧
• 在左侧添加一列，高度与当前最左列相同

很容易写出倒推一步的程序。如果倒推了 $x$ 步后发现状态相当于不需要额外准备模块，此时 $width=x+1$，那么输出 $width-1$ 即可。

最后再特判 $k=1$，此时 $n=1$ 时答案为 $1$，否则为不可能。

那么这样就做完了……吗？

每次只能在最上面一列消除 $k-1$ 个，所以 $width$ 的增长是 $\left(\dfrac{k}{k-1}\right)^n$ 级别；在 $k$ 很小而 $n$ 很大时，答案将会无比巨大。

因此，不仅需要使用高精度，而且也不再能一步一步模拟。

不过，当 $remain>k$ 时，每一步仅仅相当于 remain-=k-1;width+=1;，可以直接一次性模拟多步；而 $remain\le k$ 时，下一步就会让 $height$ 减少 $1$，$remain$ 相应变化。

如此特殊处理后就差不多做完了……吗？

来算一下时间复杂度：需要 $O(n)$ 次 $O(n)$ 位高精与低精的运算，也就是 $O(n^2)$ 的复杂度；再看一眼数据范围，$n=10^5$。看起来似乎不太过得了。

不过，可以注意到，$k=2$ 时，答案为简单的 $2^{n-2}(n\ge 2)$，可以简化计算；而 $k=3$ 时，底数仅仅有 $1.5$，再压一压位似乎常数可以变得很小。所以就可以过了。

参考代码（懒得实现高精，所以直接使用了 python）：

n,k=map(int,input().split(' '))
if k==1: # 特判 k=1
    if n==1:
        print(1)
    else:
        print('Poor E.S.!')
else:
    if k==2: # 特判 k=2
        if n<=2:
            print(1)
        else:
            print(2**(n-2))
    else:
        width,height,remain=1,n,0
        while width<2*k and (height>0 or (height==0 and remain>0)): # width 很小时，无需一次模拟多步
            cnt=width*height+remain
            cnt=cnt-k
            height=cnt//width
            remain=cnt-height*width
            width+=1
            if remain!=0:
                remain+=1
        while height>0 or (height==0 and remain>0): # width 现在很大，必须一次模拟多步
            if remain>=2:
                mult=(remain-2)//(k-1)
                remain=remain-mult*(k-1)
                width+=mult
            height-=1
            width+=1
            remain=width-(k-remain)
        print(width-1)