P4708 直角三角形（入门）

解题思路

第一步：看懂题目。 直角三角形的斜边 c 已知，两条直角边 a、b 都是正整数，并且 a ≤ b，要满足勾股定理 a² + b² = c²。题目保证一定有整数解，但如果有多组解，要输出 a 最小的那一组。

第二步：想出枚举的思路。 最直接的想法是枚举：让 a 从 1 开始，一个一个试。对每个 a，需要的 b² = c² - a²。如果 b² 正好是一个完全平方数（也就是存在整数 b 使 b×b = b²），就找到了一组解。因为 a 是从小到大试的，第一个找到的解就是 a 最小的那组。

第三步：怎么快速判断 b² 是不是完全平方数？ 如果每次都重新从 1 开始试 b，会有点慢。注意到：a 越大，c²-a² 越小，所以需要的 b 也跟着变小。我们可以让 b 从 c 开始，只往小走，永远不回头。因为 a 从小到大变大时，c²-a² 只减不增，对应的 b 也只可能变小。把 b 看作一根从右往左移动的指针，它总共只移动了 c 次，比每次都从头试 b 快得多。

第四步：举个例子验证。 c=5 时：a=1 时 b²=24，不是平方数；a=2 时 b²=21，也不是；a=3 时 b²=16=4²，找到 (3,4)。如果 c=25，会有 (7,24) 和 (15,20) 两组解，从 a=1 枚举，先遇到 a=7，输出 7 24，保证 a 最小。

第五步：注意边界与数据大小。 a 最大到 c-1（因为 b 至少是 1）；a、b 的平方可能很大（c 到 10000 时 c² 是 10^8），要用 long long 防止溢出。

参考代码

// 直角三角形：已知斜边 c，求正整数直角边 a、b，a 要尽量小
#include <iostream>
using namespace std;

int main() {
    long long c;
    cin >> c;
    long long b = c; // b 的候选值，随 a 增大而单调减小
    for (long long a = 1; a < c; a++) {
        long long needBSq = c * c - a * a; // 需要的 b 的平方
        while (b * b > needBSq) b--;       // 让 b*b 靠近 needBSq
        if (b * b == needBSq) {            // needBSq 正好是完全平方数，找到解
            cout << a << " " << b << endl;
            break; // a 从小到大枚举，第一个解就是 a 最小的
        }
    }
    return 0;
}

复杂度分析

a 从 1 枚举到 c，b 的指针总共只减少 c 次，时间复杂度 O(c)。c ≤ 10000，非常快。只用了几个变量，空间 O(1)。