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

上一题我们练习了勾股定理（$a^2+b^2=c^2$），这次我们利用另一个初中代数核心公式——平方差公式（$a^2-b^2=(a+b)(a-b)$），设计一道新的GESP 4级难度题目。

这道题考察的重点是循环结构的运用、数学边界条件的分析以及简单的时间复杂度估算。

---

题目名称：神奇的平方差 (Difference of Squares)

题目描述

在初中数学代数课上，小杨学习了著名的平方差公式：$x^2 - y^2 = (x+y)(x-y)$。

老师告诉小杨，对于给定的一个正整数 $M$，可能存在多对正整数 $(x, y)$，满足它们的平方之差恰好等于 $M$，即 $x^2 - y^2 = M$。

例如，当 $M=15$ 时：

1. $4^2 - 1^2 = 16 - 1 = 15$，所以 $(4, 1)$ 是一组解。
2. $8^2 - 7^2 = 64 - 49 = 15$，所以 $(8, 7)$ 是一组解。

现在请你编写程序，输入一个正整数 $M$，计算出共有多少对正整数 $(x, y)$ 满足 $x^2 - y^2 = M$。

输入格式

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

输出格式

输出一行，一个整数，表示满足条件的正整数对 $(x, y)$ 的数量。

输入输出样例 #1

输入：

15

输出：

2

输入输出样例 #2

输入：

24

输出：

2

解释：满足 $x^2 - y^2 = 24$ 的正整数对有 $(5, 1)$ 和 $(7, 5)$。

输入输出样例 #3

输入：

10

输出：

0

解释：不存在正整数 $x, y$ 使得 $x^2 - y^2 = 10$。

数据范围

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

---

题目分析与思路提示

作为教练，我来带你在草稿纸上分析这道题，避免盲目写代码。

1. 读题关键词

• “$x^2 - y^2 = M$”：这是核心等式。
• “正整数”：$x \ge 1, y \ge 1$。
• “数量”：只需要输出个数，不需要输出具体的 $x$ 和 $y$。
• 数据范围 $M \le 2000$：范围很小，我们可以尝试枚举法。

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

思路一：双重循环枚举（暴力法） 能不能像上一题一样枚举 $x$ 和 $y$？

• $x$ 一定比 $y$ 大（因为 $M$ 是正数）。
• $x$ 最大可能是多少？
  • 考虑 $y$ 最小为 1。此时 $x^2 - 1 = M \Rightarrow x = \sqrt{M+1}$。
  • 等等，这个思路不对！
  • 看样例 $M=15$，解有 $(8, 7)$。此时 $x=8$，而 $\sqrt{15} \approx 3.8$。这说明 $x$ 可以比 $\sqrt{M}$ 大得多。
  • 我们看最极端的情况：$x$ 和 $y$ 挨得很近，即 $x = y + 1$。
  • 此时 $(y+1)^2 - y^2 = M \Rightarrow 2y + 1 = M \Rightarrow y = (M-1)/2$。
  • 如果 $M=2000$，那么 $y$ 大约是 1000，$x$ 也是 1000 左右。
  • 结论：如果枚举 $x$ 和 $y$，范围都要到 $M/2$ 左右。两层循环大概是 $1000 \times 1000 = 10^6$ 次运算。完全可行！

思路二：单层循环枚举（优化解法） 既然 $x^2 - y^2 = M$，那么 $x^2 = M + y^2$。 我们只需要枚举 $y$，算出 $M + y^2$，然后判断这个结果是不是完全平方数。 如果是，说明找到了对应的 $x$，计数器加 1。

• $y$ 的枚举范围是多少？
  • 我们知道 $x > y$，最小的差距是 $x = y+1$。
  • 此时 $x^2 - y^2 = (y+1)^2 - y^2 = 2y + 1$。
  • 因为 $x^2 - y^2 = M$，所以 $2y + 1 \le M$。
  • 推导出 $y \le (M - 1) / 2$。
  • 当 $M=2000$ 时，$y$ 只需要循环到 999。运算量只有 1000 次，非常快！

3. 草稿纸上的模拟（以 M=24 为例）

目标：$x^2 = 24 + y^2$，且 $x$ 为整数。 枚举 $y$：

• $y=1$: $24 + 1^2 = 25$。$\sqrt{25}=5$，是整数。✅ 找到一组 (5, 1)
• $y=2$: $24 + 2^2 = 28$。$\sqrt{28} \approx 5.29$，不是整数。❌
• $y=3$: $24 + 3^2 = 33$。不是完全平方数。❌
• $y=4$: $24 + 4^2 = 40$。不是。❌
• $y=5$: $24 + 5^2 = 49$。$\sqrt{49}=7$，是整数。✅ 找到一组 (7, 5)
• $y=6$: $24 + 6^2 = 60$。不是。
• $y=7$: $24 + 7^2 = 73$。不是。
• ... $y$ 还要继续吗？
  • 根据公式 $y \le (24-1)/2 = 11.5$。枚举到 11 即可停止。

---

参考代码实现 (C++14)

/**
 * 题目：神奇的平方差
 * 难度：GESP 4级
 * 算法：枚举 (Enumerate)
 */

#include <iostream>
#include <cmath> // 必须包含，用于 sqrt

using namespace std;

int main() {
    // 1. 输入 M
    int M;
    if (!(cin >> M)) return 0;

    int ans = 0;

    // 2. 循环枚举 y
    // 根据数学推导，y 的上限是 (M - 1) / 2
    // 如果不会推导，直接让 y 循环到 M 也可以，因为 M <= 2000，不会超时
    for (int y = 1; y <= (M - 1) / 2; ++y) {
        
        // 计算 x^2 应该是多少
        long long x_sq = 1LL * M + 1LL * y * y; // 使用 long long 防止溢出(虽然M=2000时int够用)
        
        // 计算 x
        int x = sqrt(x_sq);

        // 3. 检查 x 是否是整数 (完全平方数判断)
        // 也就是看算出来的 x 平方回去是否等于 x_sq
        if (1LL * x * x == x_sq) {
            ans++;
            // 调试输出（提交时建议注释掉）：
            // cout << "Found: x=" << x << ", y=" << y << endl;
        }
    }

    // 4. 输出结果
    cout << ans << endl;

    return 0;
}

考点总结与复杂度分析

1. 时间复杂度：$O(M)$。最坏循环约 $M/2$ 次。对于 $M=2000$，计算量忽略不计。即使 $M=10^8$，这种做法也是勉强能接受的（1秒以内）。
2. 空间复杂度：$O(1)$。
3. 初中数学联系：
   • 理解 $x, y$ 的增长关系。
   • 如果不使用枚举，这道题其实等价于分解因数：$M = A \times B$，令 $x-y=A, x+y=B$，解方程组得 $x=(A+B)/2, y=(B-A)/2$。这要求 $A, B$ 同奇偶。这是更高级的 $O(\sqrt{M})$ 解法，但对于 GESP 4级，枚举法是更标准、更易写的解法。

快去动手试试吧！