【算法】【蓝桥23国A软件C】四版代码思路分析与逐步优化

题目来源：第十四届蓝桥杯大赛软件赛国赛C/C++ 大学 A 组

题目描述：

问题描述

给定一个 W×H 的长方形，两边长度均为整数。小蓝想把它切割为很多个边长为整数的小正方形。假设切割没有任何损耗，正方形的边长至少为 2，不允许出现余料，要求所有正方形的大小相等，请问最多能切割出多少个?

输入格式

输入一行，包含两个整数 W, H，用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。如果不存在满足要求的方案，输出 0。

【测试用例及其规模见文末】

题目解析：

方法一：暴力求解（无关数论）（得分：7/10）

#include <iostream>
using namespace std;
#define ll long long
int main()
{ll w,h;cin>>w>>h;ll a=min(w,h);ll b=max(w,h);  // 取较小的边为 a，较大为 bll ans=0;// 枚举 a 的约数（通过 a/i 形式间接枚举，a/i >= 2 保证正方形边长 ≥2）for(ll i=1; a/i >= 2; i++){if(a % i != 0) continue;   // i 不是 a 的约数，跳过ll cur = a / i;            // cur 是一个候选的正方形边长if(b % cur == 0)           // 如果 b 也能整除 cur，说明 w 和 h 都能被 cur 整除ans = cur;             // 更新当前满足条件的最大正方形边长}// 计算可以切多少个边长为 ans 的正方形ans = (a / ans) * (b / ans);cout << ans;return 0;
}

问题之一：粗心：没有判断找不到的情况，即输出ans=0的情况

思路分析：

• 目标是找一个最大的正方形边长 d（d ≥ 2），使得 w % d == 0 && h % d == 0，即正方形能完全铺满矩形；

• 枚举的是 i，通过 cur = a / i，我们得到了 a 的一个因数 cur；

• 如果 b % cur == 0，那说明 cur 也整除 b，即 cur 同时整除 w 和 h；

• 记录这个满足条件的最大 cur（实际上随着 i 增加，cur 减小，所以最后 ans 是最大满足条件的正方形边长）；

• 用这个 ans 去计算：一共能切 (w / ans) * (h / ans) 个正方形。

方法二：暴力求解（优化方法一）（得分：8/10）

#include <iostream>
using namespace std;
#define ll long long
int main()
{ll w,h;cin>>w>>h;ll a=min(w,h);ll b=max(w,h);ll ans=0;for(ll i=1;a/i>=2;i++){if(a%i!=0)continue;ll cur=a/i;if(b%cur==0)ans=cur;}if(ans!=0)ans=(a/ans)*(b/ans);cout<<ans;return 0;
}

优化了ans可能为0的情况

问题：该方法时间复杂度极高，因此有两组测试用例没有通过在 W, H ≤ 10^9 的范围下会超时，尤其在最坏情况（比如 W=10^9, H=10^9-1）下要跑上亿次循环。

假设 a = 10^9，那么最坏情况下你会从 i = 1 枚举到 i ≈ 5×10^8，也就是5亿次循环，这肯定爆了

方法三：暴力求解（优化方法二）（得分：10/10）

#include <iostream>
using namespace std;
#define ll long long
int main()
{ll w,h;cin>>w>>h;ll a=min(w,h);ll b=max(w,h);ll ans=0;for(ll i=a/2;i>=1;i--){if(a%i!=0)continue;ll cur=a/i;if(b%cur==0){ans=cur;break;}}if(ans!=0)ans=(a/ans)*(b/ans);cout<<ans;return 0;
}

为什么它能过所有测试？

1. 从 a/2 开始倒序找 a 的因数，最早遇到的符合条件的就是最大可行边长；

2. 一旦找到了合法边长就 break，省下后续判断；

3. a/2 → 1 最多只跑 5e8 次（极限），但实际用例中基本很快找到；

方法四：数论方法——最大公因数（得分：10/10）

#include<iostream>
using namespace std;
int gcd(long long a,long long b) {return b==0?a:gcd(b,a%b);//辗转相除法计算最大公约数
}signed main() {int w, h;cin >> w >> h;int up = gcd(w, h);if (up == 1) {cout << 0 << endl;return 0;}int ans = 0;for (int i = 2; i * i <= up; i++) {if (up % i == 0) {ans = i;break;}}if (!ans)ans = up;ans = (w * h) / (ans * ans);cout << ans << endl;return 0;
}

利用辗转相除法计算最大公约数（gcd函数）

方法：

• 把大数变成小数（用模 %）

• 交换位置继续递归

直到余数为 0，此时的另一个数就是答案。

测试用例：

样例输入1

10 20

样例输出1

50

样例说明：切割成 5×10=505×10=50 个边长为 22 的正方形。

样例输入2

6 9

样例输出2

6

样例输入3

8 13

样例输出3

0

评测用例规模与约定

对于 30%30% 的评测用例，1≤W,H≤10001≤W,H≤1000;

对于 60%60% 的评测用例，1≤W,H≤1061≤W,H≤106;

对于所有评测用例，1≤W,H≤1091≤W,H≤109。