SDUT 1447：y² = x² + n 求最小正整數 x（因子分解 + 奇偶性）

方程變形

y² − x² = n → (y−x)(y+x) = n。
設 u = y−x，v = y+x，則 u·v = n，且 u, v 同奇偶（因 y = (u+v)/2, x = (v−u)/2 必須為整數）。
要求最小正整數 x = (v−u)/2，即在所有合法因子對 (u,v) 中最大化 u（最小化差值）。

算法

1. 枚舉 i 從 √n 遞減至 1，若 i 整除 n，設 u=i, v=n/i。
2. 檢查 u, v 同奇偶且 u ≠ v（否則 x=0 不為正整數）。
3. 第一個滿足條件的即為答案（因從大到小枚舉 u，差值最小）。
4. 若無解輸出 −1。

代碼

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n;
    while (cin >> n) {
        long long ans = -1;
        for (long long u = (long long)sqrt(n); u >= 1; --u) {
            if (n % u) continue;
            long long v = n / u;
            if (u == v) continue; // x=0
            if ((u & 1) != (v & 1)) continue; // 奇偶不同
            ans = (v - u) / 2;
            break;
        }
        cout << ans << '\n';
    }
    return 0;
}

複雜度

O(√n) 每測試用例，n < 10⁹ 完全足夠。