题目内容

塔子哥买了一个长为 $a$ ,宽为 $b$的大饼,一共有 $n$ 个人来一起吃这张大饼，要求每个人必须获得相同面积的大饼。现在塔子哥被要求每一切只能平行于一块大饼的一边(任意一边)，并且必须把这块大饼切成两块。那么我们要切成 $n$ 块饼的话，塔子哥必须切 $n-1$ 次。

题目思路

首先我们假设当前的矩形长为 $x$，宽为 $y$，要分出 $k$ 块，那么不难想到分出的一块的长 $dx$ 最短为$x/k$，宽 $dy$ 最短为 $y/k$，而且每次切的长度一定是 $dx$ 的倍数或 $dy$ 的倍数，于是我们递归搜索能切的每个比例，每次切长或者宽，在分出的两块中取比值的最大值，更新最大值的最小值，返回即可。

代码

Python代码

def dfs(x, y, n):