因数分解与矩形组合：编程基础算法解析

1. 问题理解与需求拆解

这道题目看似简单，实则蕴含了编程初学者需要掌握的多个核心概念。我们先从数学角度重新梳理问题：给定一个正整数A（2≤A≤1000），需要找出所有满足长×宽=A且长≥宽的正整数对（长，宽），并统计这些组合的数量。

举个例子，当A=12时：

• 有效组合有：(12,1), (6,2), (4,3)
• 无效组合如：(2,6)因为与(6,2)重复
• 因此输出结果应为3

关键点：这里的"不同"指的是不考虑顺序的组合，即(3,4)和(4,3)视为同一种长方形。

2. 基础解法实现

2.1 暴力遍历法

最直观的解法是遍历所有可能的宽，然后检查是否存在对应的长：

cpp复制#include <iostream>
using namespace std;

int main() {
    int A, count = 0;
    cin >> A;
    
    for (int width = 1; width <= A; width++) {
        if (A % width == 0) {
            int length = A / width;
            if (length >= width) {
                count++;
            }
        }
    }
    
    cout << count << endl;
    return 0;
}

这个解法的时间复杂度是O(A)，对于A≤1000来说完全够用。但我们可以思考更优的解法。

2.2 优化遍历范围

观察到一个重要性质：当width > √A时，对应的length必然小于width。因此我们只需要遍历width从1到√A：

cpp复制#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int A, count = 0;
    cin >> A;
    int sqrtA = sqrt(A);
    
    for (int width = 1; width <= sqrtA; width++) {
        i