题目描述

塔子哥带领着一支拥有激情和创新的团队，决定建设一个全新的园区。他们经过深入调研和思考，最终选择了一块荒地，并开始了紧张而充满挑战的规划和建设工作。在大家的共同奋斗下，新园区建成了，它不仅令人刮目相看的现代化设计，更彰显着这个团队的勇气和实干精神。园区的诞生，也为附近居民和企业带来了无限机遇和福祉。

现在塔子哥打算购买一块 $m$$\times$$n$ 大小的土地，用于建设新土地。他希望将这块土地规划为尽可能少的正方形区域。他想起原先这个问题在acm竞赛中非常熟悉，但是由于他已经退役n年了，所以想寻求大家的帮助。

请注意，规划完这块土地以后，应该满足一个状态：没有任何一个正方形能放入！

思路：搜索+剪枝

给定一个 $n*m$ 的矩形，我们需要从中分割出若干个正方形，要求正方形个数最少，求该个数。

这道题初看很容易认为是用分治的做法，通过枚举分割长度将矩形分成两块，分别求两块最少能分割的正方形区域再相加，并不断递归求解。

先详细说明下错误的分治的做法：

假设当前矩形的长宽分别为 $a、b$，且有 $a \gt b$