UVA 10025 ? 1 ? 2 ... ? n = k：數學規律與 O(√k) 求解

問題重述

在 1, 2, ..., n 前填 + 或 -，使表達式值等於 k（|k| ≤ 10⁹）。求最小 n。多測試用例，輸出間隔空行。

核心數學洞察

奇偶性不變量

設 S = 1+2+...+n = n(n+1)/2。
翻轉符號相當於從 S 中減去 2×(被翻轉數之和)。
故最終結果 ≡ S (mod 2)。
必要條件：S ≥ |k| 且 S ≡ k (mod 2)（即 S-k 為偶數）。

充分性證明

若 S ≥ k 且 S-k 為偶數，設 d = (S-k)/2。
只需從 {1..n} 中選出若干數和為 d 並翻轉其符號。
因 1..n 可組成任意 [0, S] 區間內的整數（經典結論），條件亦充分。

求解算法

1. 取 k = |k|（符號對稱）
2. 求最小 n 使 S = n(n+1)/2 ≥ k：
   n ≈ ceil((√(8k+1)-1)/2)，用整數迭代調整
3. 若 (S-k) % 2 == 0 → 答案 n
4. 否則 n++ 重新計算 S，最多再試 1-2 次必找到（連續整數必含奇數，翻轉奇偶性）

代碼實現

#include 
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        long long k; cin >> k;
        if (k == 0) { cout << 0 << '\n'; if (T) cout << '\n'; continue; }
        k = llabs(k);
        long long n = sqrt(2*k); // 初始估計
        while (n*(n+1)/2 < k) ++n; // 確保 S >= k
        while (true) {
            long long S = n*(n+1)/2;
            if ((S - k) % 2 == 0) break;
            ++n;
        }
        cout << n << '\n';
        if (T) cout << '\n';
    }
    return 0;
}

關鍵細節

複雜度分析

• 每測試用例：O(1) 算術運算 + 至多 3 次循環調整
• 總時間：O(T)，T 為測試用例數
• 空間：O(1)

數學拓展：子集和覆蓋性

引理：集合 {1,2,...,n} 的子集和覆蓋 [0, n(n+1)/2] 所有整數。
證明：數學歸納法。n=1 明顯。假設 n-1 成立，對於 n，新子集和為舊子集和 ∪ (舊子集和 + n)。兩區間 [0, S_{n-1}] 和 [n, S_{n-1}+n] 重疊（因 n ≤ S_{n-1}+1），故合併覆蓋 [0, S_n]。

總結

UVA 10025 是數學洞察力轉化為 O(1) 算法的典範：

1. 識別不變量：S ≡ k (mod 2)
2. 證明充要條件：S ≥ k 且 同奇偶
3. 直接構造最小 n：從 √(2k) 起步微調

無需 DP、BFS、遞歸，純數學解法極致高效。此類「符號分配達到目標值」問題，核心均為奇偶性/模數不變量分析。