题解：B4269square

· · 题解

思路

一看完题，我心里就萌生出了两个字——递归！ 直接写函数 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;//华丽结尾
}

制作不易，给个赞吧（）