CF142A.Help Farmer
普及/提高-
通过率:0%
时间限制:1.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Once upon a time in the Kingdom of Far Far Away lived Sam the Farmer. Sam had a cow named Dawn and he was deeply attached to her. Sam would spend the whole summer stocking hay to feed Dawn in winter. Sam scythed hay and put it into haystack. As Sam was a bright farmer, he tried to make the process of storing hay simpler and more convenient to use. He collected the hay into cubical hay blocks of the same size. Then he stored the blocks in his barn. After a summer spent in hard toil Sam stored A·B·C hay blocks and stored them in a barn as a rectangular parallelepiped A layers high. Each layer had B rows and each row had C blocks.
At the end of the autumn Sam came into the barn to admire one more time the hay he'd been stacking during this hard summer. Unfortunately, Sam was horrified to see that the hay blocks had been carelessly scattered around the barn. The place was a complete mess. As it turned out, thieves had sneaked into the barn. They completely dissembled and took away a layer of blocks from the parallelepiped's front, back, top and sides. As a result, the barn only had a parallelepiped containing (A - 1) × (B - 2) × (C - 2) hay blocks. To hide the evidence of the crime, the thieves had dissembled the parallelepiped into single 1 × 1 × 1 blocks and scattered them around the barn. After the theft Sam counted n hay blocks in the barn but he forgot numbers A, B и C.
Given number n, find the minimally possible and maximally possible number of stolen hay blocks.
从前,在遥远遥远的王国里住着一位农夫——山姆。山姆养了一头名叫“黎明”的奶牛,他对她感情深厚。整个夏天,山姆都在忙着收割干草,为冬天喂养“黎明”做准备。他用镰刀割下干草,并将其堆成草垛。由于山姆是一位聪明的农夫,他试图让干草储存过程变得更简单、更便于使用。他将干草收集起来,制成大小相同的立方体干草块,然后把这些干草块存放在谷仓中。经过一个辛苦的夏天,山姆共储存了 A⋅B⋅C 块干草,并将它们以长方体(矩形平行六面体)的方式堆放在谷仓中:共 A 层高,每层有 B 行,每行有 C 块。
秋末,山姆走进谷仓,想再欣赏一次自己在这个辛苦夏天里堆起的干草。不幸的是,山姆惊恐地发现干草块被随意散落在谷仓各处,现场一片狼藉。原来,小偷潜入了谷仓!他们完全拆散了长方体,并从该长方体的前面、后面、顶部以及左右两侧各偷走了一层干草块。结果,谷仓中只剩下了一个尺寸为 (A−1)×(B−2)×(C−2) 的长方体干草块。为了掩盖罪行,小偷又将这个剩余的长方体彻底拆解成一个个 1×1×1 的单个干草块,并把它们散落在谷仓各处。失窃之后,山姆清点出谷仓中还剩 n 块干草,但他却忘记了 A、B 和 C 的具体数值。
已知整数 n,求被盗干草块数量的最小可能值和最大可能值。
输入格式
The only line contains integer n from the problem's statement (1 ≤ n ≤ 109).
唯一的一行包含题目描述中的整数 n(1 ≤ n ≤ 109)。
输出格式
Print space-separated minimum and maximum number of hay blocks that could have been stolen by the thieves.
Note that the answer to the problem can be large enough, so you must use the 64-bit integer type for calculations. Please, do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specificator.
输出被窃贼偷走的干草块数量的最小值和最大值,两个数之间用空格分隔。
注意:本题答案可能非常大,因此计算时必须使用 64 位整数类型。在 C++ 中,请勿使用 %lld 格式说明符读取或写入 64 位整数;推荐使用 cin/cout 流,或使用 %I64d 格式说明符。
输入输出样例
输入#1
4
输出#1
28 41
输入#2
7
输出#2
47 65
输入#3
12
输出#3
48 105
说明/提示
Let's consider the first sample test. If initially Sam has a parallelepiped consisting of 32 = 2 × 4 × 4 hay blocks in his barn, then after the theft the barn has 4 = (2 - 1) × (4 - 2) × (4 - 2) hay blocks left. Thus, the thieves could have stolen 32 - 4 = 28 hay blocks. If Sam initially had a parallelepiped consisting of 45 = 5 × 3 × 3 hay blocks in his barn, then after the theft the barn has 4 = (5 - 1) × (3 - 2) × (3 - 2) hay blocks left. Thus, the thieves could have stolen 45 - 4 = 41 hay blocks. No other variants of the blocks' initial arrangement (that leave Sam with exactly 4 blocks after the theft) can permit the thieves to steal less than 28 or more than 41 blocks.
我们来考虑第一个样例测试。如果最初山姆的谷仓中有一个由 32=2×4×4 个干草块组成的平行六面体,那么被盗后谷仓中剩余 4=(2−1)×(4−2)×(4−2) 个干草块。因此,窃贼最多可能偷走了 32−4=28 个干草块。如果山姆最初在谷仓中有一个由 45=5×3×3 个干草块组成的平行六面体,那么被盗后谷仓中剩余 4=(5−1)×(3−2)×(3−2) 个干草块。因此,窃贼最多可能偷走了 45−4=41 个干草块。不存在其他初始干草块排列方式(使得盗窃后恰好剩余 4 个干草块),能使窃贼偷走的干草块数少于 28 或多于 41。
输入解题思路,AI测评打分。不知道怎么写?