这是一个功能完备的数据生成器。它集成了标准题解算法（用于生成 .out）和针对性构造的测试数值（用于生成 .in）。

数据生成策略说明

为了保证测试数据的全面性和有效性，这 10 个测试点精心挑选了以下几种情况：

1. 边界情况：$M=1$（最小值）、$M=2000$（最大值）。
2. 样例数据：$M=15, 24, 10$，确保样例能通过。
3. 奇偶性与解的存在性：
   • 奇数：通常有解（除非 $M=1$）。
   • $M \equiv 2 \pmod 4$ 的偶数：数学上无整数解，测试程序是否输出 0。
   • 能被 4 整除的偶数：通常有解。
4. 特殊数字：
   • 质数：只有一组解。
   • 高合成数（因子很多）：有多组解，测试程序的循环是否遗漏。
   • 完全平方数：测试 $x, y$ 的计算逻辑。

C++ 数据生成器代码

/**
 * GESP 4级 [神奇的平方差] - 数据生成器
 * 功能：自动生成 1.in/1.out ~ 10.in/10.out
 * 作者：OI金牌教练
 */

#include <iostream>
#include <fstream>  // 文件操作
#include <string>   // 字符串处理
#include <cmath>    // 数学函数
#include <vector>

using namespace std;

// ==========================================
// Part 1: 标准题解逻辑 (用于计算正确答案)
// ==========================================
int solve(int M) {
    int ans = 0;
    // 逻辑说明：
    // 已知 x^2 - y^2 = M，则 x^2 = M + y^2
    // x, y 为正整数，故 x > y，最小差距 x = y+1
    // (y+1)^2 - y^2 = 2y + 1 <= M  =>  y <= (M-1)/2
    for (int y = 1; y <= (M - 1) / 2; ++y) {
        long long x_sq = 1LL * M + 1LL * y * y;
        int x = sqrt(x_sq);
        // 判断是否为完全平方数
        if (1LL * x * x == x_sq) {
            ans++;
        }
    }
    return ans;
}

// ==========================================
// Part 2: 数据构造与生成主程序
// ==========================================
int main() {
    // 预设 10 个具有代表性的测试点
    int test_cases[11] = {
        0,      // 占位符
        1,      // Case 1: 最小值边界，无解 (1^2-0^2不符题意y>0, 或2^2-1^2=3>1)
        2,      // Case 2: 最小的 M%4==2 的偶数，无解
        15,     // Case 3: 样例1，奇数，有解
        24,     // Case 4: 样例2，能被4整除的偶数，有解
        10,     // Case 5: 样例3，M%4==2，无解
        101,    // Case 6: 质数，只有一组解 (51, 50)
        840,    // Case 7: 高合成数(因子很多)，有多组解
        1681,   // Case 8: 完全平方数 (41^2)，奇数
        1998,   // Case 9: 接近最大值的 M%4==2，无解
        2000    // Case 10: 最大值边界，能被4整除
    };

    cout << "Start generating data..." << endl;

    for (int i = 1; i <= 10; ++i) {
        // 1. 构造文件名
        string in_name = to_string(i) + ".in";
        string out_name = to_string(i) + ".out";

        ofstream fin(in_name);
        ofstream fout(out_name);

        if (!fin.is_open() || !fout.is_open()) {
            cerr << "Error: Cannot create file for Case " << i << endl;
            continue;
        }

        int M = test_cases[i];

        // 2. 写入输入文件 (.in)
        fin << M << endl;

        // 3. 计算答案并写入输出文件 (.out)
        int ans = solve(M);
        fout << ans << endl;

        // 关闭文件流
        fin.close();
        fout.close();

        cout << "Generated Case " << i << ": M = " << M << ", Ans = " << ans << endl;
    }

    cout << "All done! 10 test cases generated successfully." << endl;
    return 0;
}

如何使用

1. 保存代码：将代码保存为 generator.cpp。
2. 编译代码：使用 C++ 编译器编译（例如 g++ generator.cpp -o generator）。
3. 运行程序：执行生成器（例如 Windows 下双击 generator.exe 或命令行运行 ./generator）。
4. 查看结果：程序运行结束后，当前文件夹下会出现 1.in 到 10.in 以及对应的 1.out 到 10.out。你可以使用这些文件上传到 OJ 或分发给学生进行本地测试。

你好！作为OI金牌教练，我为你整理了这道 GESP 4级难度题目《神奇的平方差》的标准题解代码。

这道题虽然数据范围较小，但非常适合用来练习枚举算法的边界控制以及数学性质的转化。

标准题解代码 (C++14 NOIP标准)

/**
 * 题目：神奇的平方差 (Difference of Squares)
 * 难度：GESP 4级 / CSP-J 普及-
 * 算法：枚举 (Brute Force) / 数学
 */

#include <iostream>
#include <cmath>    // 用于 sqrt 函数
#include <algorithm>

using namespace std;

// 建议在竞赛中开启 IO 优化，加快输入输出速度
void fast_io() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
}

int main() {
    fast_io();

    int M;
    // 输入检查，这是良好的编程习惯
    if (!(cin >> M)) return 0;

    int ans = 0;

    // 核心逻辑：枚举 y，检查是否存在对应的整数 x
    // 
    // 【循环范围推导】
    // 已知 x^2 - y^2 = M，且 x, y 均为正整数，故 x > y。
    // x 与 y 最小的差距是 x = y + 1。
    // 此时平方差最小，为 (y+1)^2 - y^2 = 2y + 1。
    // 如果这个最小差值 2y + 1 都已经大于 M 了，那么更大的 x 只会让差值更大。
    // 所以必须满足：2y + 1 <= M  =>  2y <= M - 1  =>  y <= (M - 1) / 2
    // 
    // 注：对于 M=2000，即使 y 循环到 M 也能过，但推导边界是 4级考生的必备能力。
    for (int y = 1; y <= (M - 1) / 2; ++y) {
        
        // 计算 x^2 的值：x^2 = M + y^2
        // 虽然 M=2000 时 int 不会溢出，但在数值计算中习惯性转 long long 防止溢出是好习惯
        long long x_sq = 1LL * M + 1LL * y * y;
        
        // 尝试开平方求 x
        // sqrt 返回的是 double，强制转换为 int 取整数部分
        int x = sqrt(x_sq);

        // 【关键点】：完全平方数判定
        // 如果 x_sq 是完全平方数，那么 x*x 应该恰好等于 x_sq
        // 这一步利用了整数运算的精确性来验证浮点运算的结果
        if (1LL * x * x == x_sq) {
            ans++;
            // 调试时可以取消注释查看具体解：
            // cout << "Found solution: " << x << "^2 - " << y << "^2 = " << M << endl;
        }
    }

    cout << ans << endl;

    return 0;
}

详细分析与思考过程

1. 时间复杂度分析

• 思考过程：
  • 如果我们暴力枚举 $x$ 和 $y$ 两层循环，复杂度是 $O(M^2)$ 或 $O(M)$，取决于边界。
  • 通过数学变形 $x^2 = M + y^2$，我们将问题转化为“枚举 $y$，判断 $M+y^2$ 是否为完全平方数”。
  • 根据数学推导（代码注释中的不等式），$y$ 的上限是 $M/2$。
  • 循环内部的操作（乘法、加法、开根号）都是 $O(1)$ 的。
• 结论：时间复杂度为 $O(M)$。
  • 代入数据 $M=2000$，循环次数约为 1000 次，耗时忽略不计（微秒级）。即使 $M$ 增大到 $10^7$，该算法依然能在 1 秒内通过。

2. 空间复杂度分析

• 分析：只使用了几个整型变量存储输入和中间结果，没有申请数组。
• 结论：空间复杂度为 $O(1)$。

3. 易错点提示

1. 枚举方向：
   • 有些同学可能会去枚举 $x$。如果枚举 $x$，公式变为 $y^2 = x^2 - M$。
   • 此时 $x$ 的起点应该是 $\lceil\sqrt{M+1}\rceil$（因为 $y^2 \ge 1 \Rightarrow x^2-M \ge 1$），上界依然是 $M/2$ 左右。虽然也能做，但边界条件比枚举 $y$ 稍微复杂一点（涉及到起点的计算）。枚举 $y$ 从 1 开始非常自然。
2. 浮点数精度：
   • 直接判断 sqrt(n) == floor(sqrt(n)) 是可行的，但最稳妥的方式永远是 算出整数根后再平方回去验证，这样可以避开所有浮点数精度陷阱。

进阶优化建议（适合 GESP 6级+）

如果数据范围加强到 $M \le 10^{12}$，$O(M)$ 的算法会超时。我们需要利用因数分解来优化到 $O(\sqrt{M})$。

数学推导：

令 $A = x - y, B = x + y$。 则 $A \times B = M$。 且由于 $x, y$ 是正整数，必有 $B > A > 0$。 联立解得：

要使 $x, y$ 为整数，必须满足：

1. $(A + B)$ 是偶数 $\Rightarrow A, B$ 同奇偶。
2. 因为 $A \times B = M$，如果 $M$ 是奇数，则 $A, B$ 必都为奇数（同奇）；如果 $M$ 是偶数，则 $A, B$ 必都为偶数（同偶）。
   • 注意：如果 $M$ 是偶数但不能被 4 整除（即 $M \equiv 2 \pmod 4$），则 $M = 2 \times \text{Odd}$，必然是一个奇数乘以一个偶数，此时无解。

优化算法：

1. 枚举 $i$ 从 $1$ 到 $\sqrt{M}$。
2. 如果 $i$ 能整除 $M$（即 $i$ 是 $M$ 的因子），令 $A = i, B = M/i$。
3. 判断 $A$ 和 $B$ 是否同奇偶（即 (A + B) % 2 == 0）。
4. 如果满足且 $B > A$（题目要求正整数解，通常 $x^2-y^2=M$ 隐含 $x>y$），则计数加 1。

复杂度：$O(\sqrt{M})$。对于 $10^{12}$ 的数据也能秒杀。