当前位置：首页 > article >正文

蓝桥杯每日真题 - 第24天

article 2024/11/28 5:39:12

题目：（货物摆放）

题目描述（12届 C&C++ B组D题）

解题思路：

这道题的核心是求因数以及枚举验证。具体步骤如下：

因数分解： 通过逐一尝试小于等于 $\sqrt{n}$ 的数，找到 n 的所有因数，并保存到数组中，确保不会遗漏对称因数对。
三重循环验证： 枚举所有可能的 (L, W, H) 的组合，验证这三数的乘积是否等于 n。
优化计算： 对因数分解和组合的枚举部分进行优化，减少不必要的计算。

代码实现（C语言）：

#include <stdio.h>
#include <math.h>

int main() {
    long long n = 2021041820210418;
    long long factors[3000]; // 用于存储 n 的因数
    int factorCount = 0;
    
    // 找到所有因数
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            factors[factorCount++] = i;         // 添加因数 i
            if (i != n / i) {
                factors[factorCount++] = n / i; // 添加对称因数 n/i
            }
        }
    }

    int count = 0;

    // 枚举 (L, W, H)
    for (int a = 0; a < factorCount; a++) {
        for (int b = 0; b < factorCount; b++) {
            for (int c = 0; c < factorCount; c++) {
                if (factors[a] * factors[b] * factors[c] == n) {
                    count++;
                }
            }
        }
    }

    printf("%d\n", count); // 输出结果
    return 0;
}

得到运行结果：

难度分析

⭐️⭐️⭐️

总结

解题核心：
- 通过因数分解找到所有可能的 L,W,H 组合。
- 遍历验证组合的合法性。
优化方向：
- 如果问题规模更大，可以用分治法或者只枚举 L 和 W，通过 $H = n / (L \times W)$ 的关系计算，进一步降低复杂度。
结果：
输出的 count 即为符合条件的所有堆放方案总数，最终提交答案即可。