题解

题目解析

• 输入输出：输入一个整数 $n$；输出满足条件的不同直角三角形数量，其中直角边长 $a, b$ 均为不超过 $n$ 的正整数，且两直角边无序（即 $(a,b)$ 与 $(b,a)$ 视为同一种）。
• 数据范围：$1 \leq n \leq 1000$，规模允许 $O(n^2)$ 枚举。
• 复杂度要求：时间复杂度 $O(n^2)$，空间复杂度 $O(1)$。
• 算法知识点：数学、枚举、奇偶性分析、去重策略

思路解析

1. 面积整数条件：直角三角形面积 $S = \frac{a \times b}{2}$。要使 $S$ 为整数，必须满足 $a \times b$ 为偶数，即 $a$ 和 $b$ 中至少有一个是偶数（若两者均为奇数，则乘积为奇数，面积为半整数）。
2. 去重策略：题目规定 $(a,b)$ 与 $(b,a)$ 视为相同的三角形。为避免重复计数，在枚举时强制规定 $a \leq b$（代码中体现为内层循环 $j$ 从 $i$ 开始），这样每个无序数对仅被统计一次。
3. 枚举统计：使用双重循环遍历所有满足 $1 \leq i \leq j \leq n$ 的无序对，判断 $i \times j$ 的奇偶性。若为偶数，则该组合对应的三角形面积必为整数，答案加一。

完整代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int ans = 0;
    
    // 枚举所有无序对 (i, j)，满足 1 ≤ i ≤ j ≤ n
    for (int i = 1; i <= n; i++) {
        // 关键：j 从 i 开始，确保 i ≤ j，自动处理 (a,b) 与 (b,a) 的去重
        for (int j = i; j <= n; j++) {
            // 判断面积是否为整数：i*j/2 为整数 ⟺ i*j 为偶数
            if (i * j % 2 == 0) {
                ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}