你好！我是你的OI金牌教练。

为了贴合初中数学背景并符合GESP 4级（涉及循环、分支、基本算法思维，通常数据范围在 $1000$ 到 $10^5$ 之间，时间复杂度允许 $O(N^2)$ 或 $O(N \log N)$）的难度，我为你设计了下面这道题目。

这道题考察了初中数学中著名的 “勾股定理” 以及编程中的 枚举算法与优化。

题目名称：寻找勾股数 (Pythagorean Triples)

题目描述

小杨最近在初中数学课上学习了“勾股定理”。老师告诉他，如果三个正整数 $a, b, c$ 满足 $a^2 + b^2 = c^2$，那么这三个数就构成了一组“勾股数”，它们可以作为直角三角形的三条边长。

现在老师给出一个整数 $L$，请你编写程序帮助小杨找出，有多少组勾股数 $(a, b, c)$，使得由这三条边组成的直角三角形的周长不超过 $L$。

为了避免重复计算，我们约定每组勾股数必须满足 $a < b < c$。

输入格式

输入一行，包含一个正整数 $L$。

输出格式

输出一行，一个整数，表示满足条件的勾股数有多少组。

输入输出样例 #1

输入：

30

输出：

3

样例 #1 解释： 周长不超过 30 的勾股数有以下 3 组：

1. $a=3, b=4, c=5$。周长 $3+4+5=12 \le 30$，满足条件。
2. $a=6, b=8, c=10$。周长 $6+8+10=24 \le 30$，满足条件。
3. $a=5, b=12, c=13$。周长 $5+12+13=30 \le 30$，满足条件。

注意：虽然 $(8, 15, 17)$ 也是勾股数，但周长 $8+15+17=40 > 30$，不符合要求。

数据范围

对于 $100\%$ 的数据，保证 $1 \le L \le 2000$。

题目分析与思路提示

作为教练，我来引导你如何在草稿纸上推导这道题。

1. 读题关键词

• “勾股数”：公式 $a^2 + b^2 = c^2$。
• “周长不超过 $L$”：$a + b + c \le L$。
• “$a < b < c$”：这大大减少了我们需要枚举的范围，且不用考虑去重。
• 数据范围 $L \le 2000$：这意味着 $O(L^3)$ 的算法（约 $8 \times 10^9$ 次运算）会超时，但 $O(L^2)$ 的算法（约 $4 \times 10^6$ 次运算）是完全可以接受的（通常 C++ 1秒能跑 $10^8$ 次运算）。

2. 启发式思考过程（草稿纸推演）

思路一：暴力枚举（Naive Approach） 我们写三层循环枚举 $a, b, c$？

// 伪代码
ans = 0
for a from 1 to L:
    for b from a+1 to L:
        for c from b+1 to L:
            if a*a + b*b == c*c AND a+b+c <= L:
                ans++

• 复杂度分析：三层循环，接近 $O(L^3)$。当 $L=2000$ 时肯定超时 (TLE)。我们需要优化。

思路二：利用数学关系降维（GESP 4级标准解法） 其实我们不需要枚举 $c$。 因为在直角三角形中，$c$ 是由 $a$ 和 $b$ 决定的：$c = \sqrt{a^2 + b^2}$。 只要确定了 $a$ 和 $b$，我们就算出了 $c$，然后检查两点：

1. 算出来的 $c$ 是整数吗？
2. $a+b+c$ 是否小于等于 $L$？

• 草稿纸上画范围：

  • 因为 $a < b < c$ 且 $a+b+c \le L$，最小的 $a$ 是 3 (3-4-5三角形)，最大呢？$3a < a+b+c \le L$，所以 $a$ 最多到 $L/3$。
  • $b$ 从 $a+1$ 开始枚举，到多少呢？$a+2b < a+b+c \le L$，所以 $b$ 大约到 $(L-a)/2$。

• 优化后的流程：

  1. 第一层循环枚举 $a$ （从 1 到 $L/3$）。
  2. 第二层循环枚举 $b$ （从 $a+1$ 开始）。
  3. 计算 $a^2 + b^2$。
  4. 判断 $a^2 + b^2$ 是否是完全平方数（即开根号后是整数）。
  5. 如果是，得到 $c$，判断 $a+b+c \le L$。
  6. 剪枝优化：如果在内层循环中发现 $a+b+b > L$（因为 $c>b$，如果 $a+b+b$ 都超了，$a+b+c$ 肯定超），就可以直接 break 退出内层循环了。

3. 复杂度分析

• 时间复杂度：两层循环，$O(L^2)$。代入 $L=2000$，运算次数约为 $4 \times 10^6$，在 1 秒限制内非常安全。
• 空间复杂度：$O(1)$，只需要几个变量。

4. 代码实现细节（易错点）

• 判断完全平方数：可以使用 sqrt 函数，但要注意浮点数误差。
  • 推荐写法：int c = sqrt(a*a + b*b); 然后判断 if (c*c == a*a + b*b)。
• 数据类型：$L=2000$，那么 $a^2 + b^2$ 最大约为 $2000^2 = 4 \times 10^6$，int（最大 $2 \times 10^9$）完全存得下，不需要 long long。

参考代码框架 (C++)

#include <iostream>
#include <cmath> // 需要用到 sqrt 函数

using namespace std;

int main() {
    int L;
    cin >> L;

    int ans = 0;

    // a 枚举范围：从 3 开始到 L/3
    for (int a = 3; a <= L / 3; a++) {
        // b 枚举范围：从 a+1 开始
        // 剪枝条件：如果 a + b + (b+1) 已经超过 L，就没必要继续增大了
        for (int b = a + 1; ; b++) {
            // 这里可以做一个粗略的预判剪枝，c 肯定大于 b
            if (a + b + b > L) break; 
            
            // 计算斜边的平方
            int c_square = a * a + b * b;
            
            // 计算 c
            int c = sqrt(c_square);
            
            // 检查 c 是否是整数 (即 c*c 是否等于原值)
            if (c * c == c_square) {
                // 检查周长
                if (a + b + c <= L) {
                    ans++;
                } else {
                    // 如果当前 a, b 算出来的 c 导致周长超了，
                    // 那么更大的 b 肯定也超，直接 break
                    break;
                }
            }
        }
    }

    cout << ans << endl;
    return 0;
}

快去试试把代码写出来并提交吧！这种结合数学知识的枚举题在 GESP 4级和 CSP-J 中都很常见。