N×M纸张切割为1×1正方形的最少切割次数代码原理求解

代码逻辑说明 #

这个切割问题的核心结论非常确定：无论你选择什么顺序下刀，最终需要的总刀数固定为n * m - 1。给出的代码只是把切割过程拆成了两个分步计算，和核心结论完全等价：

• 第一步：先把整张N×M的纸沿着行方向切割，得到N张独立的1×M长条，只需要切n-1刀，对应代码里的(n - 1)项
• 第二步：对每一张1×M的长条单独切割，每张要切成M个1×1的小正方形需要切m-1刀，N张总共需要n * (m - 1)刀，对应代码里的第二项

把式子展开就能验证等价性：
(n-1) + n*(m-1) = n - 1 + n*m - n = n*m - 1

为什么这个求解是正确的 #

从切割规则的本质出发就很好理解：

每次只能选一张纸片完全切开，所以每一刀只会让总纸片数增加1。

初始状态只有1张整纸，最终要得到n*m张1×1的小正方形，总纸片数的增量是n*m - 1，所以不管你按什么顺序切割，总刀数必然是这个值。代码的写法只是选择了「先切所有行、再切所有列」的顺序来计算，结果完全符合要求。

另外代码里的1LL是为了做类型提升：如果n和m都是int类型，直接计算n*(m-1)可能会超出int的取值范围，乘以1LL后会把整个表达式的类型提升为long long，避免整数溢出问题。

内容的提问来源于stack exchange，提问作者kiddoP