题目分析

我们有一个序列： $a_n = k + n^2, \quad n \ge 0$ 我们要找最小的非负整数 $m$，使得存在某个 $n \ge 0$ 满足： $k + n^2 = m^2$ 即： $m^2 - n^2 = k$ $(m - n)(m + n) = k$

设 $d = m - n$，则 $m + n = k / d$，于是： $ m = \frac{k/d + d}{2}, \quad n = \frac{k/d - d}{2} $ 要求：

1. $d$ 整除 $k$
2. $k/d \ge d$（保证 $n \ge 0$）
3. $k/d$ 与 $d$ 同奇偶（保证 $m, n$ 为整数）

特殊情况

• 当 $k \ge 0$ 时，只需枚举 $d$ 从 $1$ 到 $\lfloor \sqrt{k} \rfloor$。
• 当 $k < 0$ 时，令 $t = -k$，方程变为： $n^2 - m^2 = t$ 设 $d = n - m$，则 $n + m = t / d$，于是： $m = \frac{t/d - d}{2}$ 要求 $t/d \ge d$ 且同奇偶。

C++ 代码

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    long long k;
    cin >> k;

    if (k >= 0) {
        long long ans = -1;
        for (long long d = 1; d * d <= k; d++) {
            if (k % d == 0) {
                long long y = k / d;
                if ((y + d) % 2 == 0) {
                    long long m = (y + d) / 2;
                    if (ans == -1 || m < ans) {
                        ans = m;
                    }
                }
            }
        }
        if (ans != -1) {
            cout << ans * ans << endl;
        } else {
            cout << "none" << endl;
        }
    } else {
        long long t = -k;
        long long ans = -1;
        for (long long d = 1; d * d <= t; d++) {
            if (t % d == 0) {
                long long y = t / d;
                if ((y + d) % 2 == 0) {
                    long long m = (y - d) / 2;
                    if (m >= 0 && (ans == -1 || m < ans)) {
                        ans = m;
                    }
                }
            }
        }
        if (ans != -1) {
            cout << ans * ans << endl;
        } else {
            cout << "none" << endl;
        }
    }

    return 0;
}

复杂度分析

• 时间复杂度：$O(\sqrt{|k|})$，对于 $k \le 10^{12}$ 是可行的。
• 空间复杂度：$O(1)$。

样例验证

1. 输入 0 → 输出 0
2. 输入 -5 → 输出 4
3. 输入 2 → 输出 none