12935.长方形面积

markdown
复制
1# 长方形面积 题解
2
3## 题目分析
4题目要求统计面积为 $A$ 的长方形的种类数。长方形的长和宽都必须是整数，且长大于等于宽。正方形也被视为长方形的一种（长宽相等）。
5
6换句话说，我们要找所有满足以下条件的正整数对 $(l, w)$：
7- $l \times w = A$
8- $l \ge w$
9
10## 解题思路
11由于长和宽都是整数，且乘积固定为 $A$，长和宽必然是 $A$ 的一对因子。因此，问题转化为：统计 $A$ 有多少对因子 $(l, w)$ 满足 $l \ge w$，并且每对因子只计一次（即不考虑顺序）。
12
13为了不重复统计，我们可以让宽 $w$ 从 $1$ 枚举到 $\sqrt{A}$。对于每个 $w$，如果 $A$ 能被 $w$ 整除，那么 $l = A / w$ 就是一个满足条件的长（显然 $l \ge w$，因为 $w \le \sqrt{A}$）。此时我们就找到了一种合法的长方形。
14
15为什么枚举到 $\sqrt{A}$ 就够了？  
16因为如果 $w > \sqrt{A}$，那么对应的 $l = A / w < \sqrt{A}$，此时 $l < w$，不满足“长大于等于宽”的条件。所以 $w$ 只需枚举到 $\sqrt{A}$ 即可覆盖所有不重复的情况。
17
18### 算法步骤
191. 读入整数 $A$。
202. 初始化计数器 $cnt = 0$。
213. 令 $w$ 从 $1$ 到 $\lfloor\sqrt{A}\rfloor$ 遍历：
22   - 如果 $A \bmod w = 0$，说明 $w$ 是 $A$ 的因子，对应的长 $l = A / w$，此时 $l \ge w$，计数加一。
234. 输出 $cnt$。
24
25## 时间复杂度分析
26枚举 $w$ 的范围为 $1 \sim \sqrt{A}$，每次判断整除是 $O(1)$ 操作，因此总时间复杂度为 $O(\sqrt{A})$。  
27在题目限制 $A \le 1000$ 的情况下，$\sqrt{1000} \approx 31.6$，运算量极小，完全可以在时间限制内运行完毕。
28
29## 参考代码
30```cpp
31#include <iostream>
32#include <cmath>
33using namespace std;
34
35int main() {
36    int A;
37    cin >> A;
38
39    int cnt = 0;
40    // 枚举宽 w，w <= sqrt(A) 才能保证长 >= 宽
41    for (int w = 1; w * w <= A; ++w) {
42        if (A % w == 0) {
43            // w 是因子，对应的长 l = A / w，且 l >= w
44            cnt++;
45        }
46    }
47    cout << cnt << endl;
48    return 0;
49}

代码说明

• 使用 w * w <= A 作为循环条件，等价于 $w \le \sqrt{A}$，且避免了浮点数运算。
• 当 A % w == 0 成立时，说明 $w$ 能整除 $A$，此时 $(l, w) = (A/w, w)$ 是一对满足要求的整数长宽，长 $l$ 必定大于等于 $w$。
• 每找到一对就使计数器 cnt 加一。
• 最后输出 cnt 即可。

样例验证

样例 1

输入：4

• $w = 1$：$4 \bmod 1 = 0$，$l = 4$，计数 +1（长方形 $4 \times 1$）
• $w = 2$：$4 \bmod 2 = 0$，$l = 2$，计数 +1（长方形 $2 \times 2$）
  输出：2（与题目解释一致）

样例 2

输入：6

• $w = 1$：$l = 6$，计数 +1（$6 \times 1$）
• $w = 2$：$l = 3$，计数 +1（$3 \times 2$）
• $w = 3$：$3 \times 3 = 9 > 6$ 终止循环
  输出：2（与题目解释一致）

总结

本题实质上是求整数 $A$ 的不大于 $\sqrt{A}$ 的因子个数。利用长宽乘积等于面积，以及长不小于宽的限制，可以轻松通过枚举较小的因子解决。注意题目中的参考代码有误（与本题目无关），不可直接套用。