很久很久以前,在遥远的王国里住着农夫山姆。山姆有一头名叫黎明的母牛,他对她情有独钟。山姆整个夏天都在放牧干草,冬天喂黎明。山姆用镰刀把干草放进干草堆里。由于山姆是一个聪明的农民,他试图让储存干草的过程更简单、更方便使用。他把干草收集成同样大小的立方体干草块。然后他把积木存放在他的谷仓里。经过一个夏天的辛勤劳作,山姆 将 A⋅B⋅C干草块储存在谷仓中,作为一个长方体 A 层高。每层有 B 行,每行有 C 块。 秋天结束时,山姆走进谷仓,再次欣赏他在这个严酷的夏天堆放的干草。不幸的是,山姆惊恐地看到干草块被漫不经心地散落在谷仓周围。这个地方一团糟。事实证明,小偷已经潜入谷仓。他们完全拆散并从平行六面体的正面、背面、顶部和侧面剥去了一层积木。结果,谷仓只有一个包含 (A−1)×(B−2)×(C−2)干草块的平行六面体。为了隐藏犯罪的证据,小偷将平行六面体组装成一个1×1×1块,散落在谷仓周围。盗窃后,山姆数了谷仓里的 n个干草块,但他忘记了数字 A、B 和 C。 给定数字 n,找出被盗干草块的最小可能和最大可能数量。 输入格式 唯一的一行包含来自问题陈述的整数 n (1≤n≤109)。 输出格式 打印可能被小偷偷走的干草块的最小和最大数量,以空格分隔。
时间: 2024-03-28 14:40:48 浏览: 22
这是一道数学题,需要用到一些数学知识和推理。我们可以从最小的干草块数量开始推导,然后逐渐增加干草块数量,直到找到最大的干草块数量。具体方法如下:
假设被盗走的干草块数量为 x,则有:
x = A*B*C - (A-1)*(B-2)*(C-2)
化简可得:
x = A*B + 2*A + 2*B + 4 - n
我们可以看出,x 是一个关于 A 和 B 的二次方程,可以用求根公式解出 A 和 B 的值。但是这样的时间复杂度较高,不适用于本题的数据范围。
我们可以采用另一种方法,先枚举 A 的可能取值,然后计算对应的 B 的取值范围,再计算对应的干草块数量。如果干草块数量等于 x,则说明找到了一组解。具体步骤如下:
1. 从 1 开始枚举 A 的可能取值,直到 A^2 > n。因为如果 A^2 > n,则 A*B+C > n,不可能有解。
2. 对于每个 A,计算出对应的 B 的取值范围。B 的最小值为 4,因为如果 B < 4,则 (B-2)*(C-2) < 0,无论 C 取多少,都有 (A-1)*(B-2)*(C-2) < 0,因此 x < A*B,不可能有解。B 的最大值为 (n-x)/(2*A+2),因为如果 B > (n-x)/(2*A+2),则 C < 2,无论 C 取多少,都有 (A-1)*(B-2)*(C-2) < 0,因此 x < A*B,不可能有解。
3. 对于每个 A 和满足条件的 B,计算对应的干草块数量,如果等于 x,则找到了一组解。
4. 如果没有找到解,则继续枚举下一个 A。
最小值即为找到的第一个解,最大值即为最后一个解。注意,如果没有找到解,则最小值和最大值相等,都为 -1。
代码实现如下: