自动搬运

查看原文

来自洛谷，原作者为

	zzq3 “愛の強制ミューティレーツョソ！”

搬运于2025-08-24 21:18:14，当前版本为作者最后更新于2025-03-30 20:17:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

一看完题，我心里就萌生出了两个字——递归！ 直接写函数 $f(a,b)$ 代表长为 $a$ ，宽为 $b$ 的长方形能分割出的正方形边长之和最小值。于是我写出了以下代码：

#include <bits/stdc++.h>
using namespace std;
using ll = unsigned long long;//不用这个只能得30分
ll f(ll a, ll b) {
    if (a == b) {
        return a;//是正方形直接返回
    }
    if (a < b) {
        swap(a,b);// a 长边 b 短边
    }
  // 切出一个边长为 B 的正方形，递归处理剩余部分
    return b + f(a - b, b);
}
int main() {
    for (int i = 1; i <= 10;i++) {
        ll a, b;
        cin >> a >> b;
        cout << f(a, b) << endl;
    }
    return 0;
}    

完事！提交！AC !

完不了一点

如你所见我喜提一个 TLE ……

优化

不难发现，如果数据是 $a=1,b=n$ 那么递归将会运行 $n$ 次。题目中还说了 $a,b$ 的范围到 long long ，明显大于时间范围。
所以我们可以做如下优化：取 $a/b=sum$ ,每次递归直接取走 $sum$ 个边长为 $b$ 的正方形，这样就可以大大减少递归的次数。

#include <bits/stdc++.h>
using namespace std;
using ll = unsigned long long;
ll f(ll a, ll b) {
	if(a==0||b==0) return 0;//边界条件
    if (a < b) swap(a,b);
    ll sum = a/b;//取sum个边长为b的正方形
    ll yu = a%b;//a线剩余的长度
    return b*sum + f(yu, b);//继续递归
}
int main() {
    for (int i = 1; i <= 10;i++) {
        ll a, b;
        cin >> a >> b;
        cout << f(a, b) << endl;
    }
    return 0;//华丽结尾
}    

制作不易，给个赞吧（）