题解：P10415 [蓝桥杯 2023 国 A] 切割

huangyuze114514 · 2024-06-14 18:46:58 · 题解

思路

求出 W,N 的大于等于 2 的最小公因数，把大于等于 2 的最小公因数分别除 W,N，得出的两个数相乘即为所求。

所以我们按照思路写一篇代码：

#include <bits/stdc++.h>
using namespace std;
int main(){
    long long n,m;
    cin>>n>>m;
    for(long long i=2;;i++){
        if(n%i==0&&m%i==0){
            cout<<n/i*m/i;
            return 0;
        }
    }
    return 0;
}

发现超时了，因为本题数据较大，暴力显然不能过，所以对于遍历符合答案的边长 i，要进行一点优化：

• 首先，我们设 a 为 W 和 H 的最大公约数。然后，我们便可以得出，在最坏情况下，答案的值是 W 除以 a 和 H 除以 a 的积，即 \frac{W}{a}\times\frac{H}{a}。
• 因此，我们可以得出 i 的范围为：2 \le i \le a。
• 又因为 a 为 W 和 H 的最大公约数，所以 i 一定是 a 的因数。
• 然后，我们发现一个原理：如果 a 有一个大于 \sqrt{a} 的因数 k，那么它必然对应一个小于 \sqrt{a} 的因数 \frac{a}{k}。
• 综合最后两条，我们可以得出结论：当 i>\sqrt{a} 时，便可结束遍历。因为当前 i 对应的 \frac{a}{i} 已经被遍历过了，但并不符合答案，所以当前的 i 也不会符合答案，大于当前的 i 的值也不会符合。

综上，i 的范围便是 2 \le i \le \sqrt{a}。因此我们可以用如下代码进行遍历：

for(int i=2;i*i<=a;i++){ 
  if(n%i==0&&m%i==0){
    cout<<n/i*m/i;
    return 0;
  }
}

为了使结果更精确，要将遍历的条件 i<=sqrt(a) 改为 i*i<=a。

还有一个特殊条件，当 W 和 H 互质时，便是不存在满足要求的方案，输出 0 即可。

代码如下

#include <bits/stdc++.h>
using namespace std;
int main(){
    long long n,m;
    cin>>n>>m;
    int a=__gcd(n,m);//求最大公约数，也就是最大正方形的边长
    if(a==1){//互质不符合题目条件 
        cout<<0;
        return 0;
    }
    for(int i=2;i*i<=a;i++){//用i*i来比较的原因见上 
        if(n%i==0&&m%i==0){
            cout<<n/i*m/i;
            return 0;
        }
    }
    cout<<n/a*m/a;//没有符合条件便输出最大正方形的解 
    return 0;
}