當數學遇上程式：用質因數分解優雅解決「三角和」問題

***此篇文章由 Gemini AI 產生*** 在程式解題的世界裡，我們時常在尋找暴力解法之外的、那條更優雅、更高效的康莊大道。今天，讓我們來深入探討一個經典問題 — LeetCode 上的「找出陣列的三角和」，並一步步揭示如何將一個直觀的 $O(n^2)$ 解法，昇華為一個令人驚嘆的 $O(n)$ 數論解法。 ### 問題的起點：模擬與組合數 「三角和」問題要求我們對一個數字陣列進行反覆操作：不斷將相鄰的兩個數字相加（對 10 取餘）形成一個新陣列，直到陣列只剩下最後一個數字。 一個最直觀的想法是**模擬**這個過程。這個方法可行，但時間複雜度是 $O(n^2)$。以下是不使用額外空間、直接在原陣列上操作的優化版本： ```cpp // O(n^2) Simulation Method (In-place, O(1) extra space) // This approach directly simulates the process without creating new vectors. int n = nums.size(); if (n == 1) return nums[0]; // We perform n-1 passes of transformation. // After each pass, the effective size of the array shrinks by one. for (int pass = 0; pass < n - 1; ++pass) { // This inner loop iterates up to the new boundary. // We update each element based on its next neighbor. for (int i = 0; i < n - 1 - pass; ++i) { nums[i] = (nums[i] + nums[i + 1]) % 10; } } // After all passes, the result is the first element of the array. return nums[0]; ``` 稍微深入思考，你會發現這個過程其實與數學上的**帕斯卡三角形**（或稱楊輝三角）如出一轍。最終的結果可以表示為一個組合數公式： $$S = \left( \sum_{k=0}^{n-1} C(n-1, k) \cdot \text{nums}[k] \right) \pmod{10}$$ 這是一個巨大的突破！但當我們嘗試用程式實現這個公式時，很快就會撞上兩堵高牆： 1. **整數溢位**：組合數 $C(n, k)$ 的值增長極快，即便是 `unsigned long long` 也無法承受。 2. **模運算下的除法**：為了避免溢位，我們想在計算過程中就取餘。但遞迴公式 $C(n,k) = C(n,k-1) \cdot \frac{n-k+1}{k}$ 涉及除法，而模 10 的運算下，許多數字（如 2, 4, 5）並不存在模反元素，這條路也被堵死了。 難道我們只能止步於 $O(n^2)$ 嗎？ ### 思維躍遷：用質因數取代數值 真正的優化來自於一個核心思想的轉變：**如果我們不能直接處理數值，那就去處理它們的組成部分 — 質因數。** 既然模數是 10，其質因數就是 2 和 5。我們可以將任何數字 `N` 表示為一種特殊形式： $$N = 2^{p_2} \cdot 5^{p_5} \cdot R$$ 其中 `R` 是除去所有 2 和 5 之後的剩餘部分。我們只需要追蹤這三個值 (`p2`, `p5`, `R % 10`)，就可以在不產生大數的情況下，完成所有計算！ ### 質因數的四則運算 我們定義一個新的數字結構 `FactorRep` (Factor Representation)，並為它實現乘法和除法： * **乘法**：兩個 `FactorRep` 相乘時，`p2` 和 `p5` 指數各自相加，`R` 則直接相乘後取餘。 * **除法**：指數各自相減，`R` 的除法則透過一個預先計算好的「模反元素」表來轉換為乘法。 這個技巧完美地繞過了模運算除法的限制，為我們的 $O(n)$ 解法鋪平了最後一哩路。 ### 最終解法：$O(n)$ 的優雅實現 現在，讓我們將所有想法整合起來，呈現這份兼具性能與巧思的最終程式碼。在這個版本中，我們將計算係數的複雜邏輯抽離到一個獨立的 `get_coeffs` 函式中，讓主函式 `triangularSum` 的意圖更加清晰：**先取得係數，再計算總和**。 ```cpp // Represents a number N as N = 2^p2 * 5^p5 * rem struct FactorRep { int p2 = 0; // Exponent of prime factor 2 int p5 = 0; // Exponent of prime factor 5 int rem = 1; // Remainder part, coprime to 10 }; class Solution { private: // Decomposes an integer n into its FactorRep form. FactorRep get_factors(int n) { if (n == 0) return {0, 0, 0}; FactorRep rep; rep.p2 = 0; while (n > 0 && n % 2 == 0) { rep.p2++; n /= 2; } rep.p5 = 0; while (n > 0 && n % 5 == 0) { rep.p5++; n /= 5; } rep.rem = n % 10; return rep; } // A simple integer power helper. int power(int base, int exp) { int res = 1; for (int i = 0; i < exp; ++i) res *= base; return res; } // Converts a FactorRep back to its integer value mod 10. int to_int(const FactorRep& rep) { if (rep.p2 > 0 && rep.p5 > 0) return 0; int term2 = power(2, rep.p2); int term5 = power(5, rep.p5); return (term2 * term5 * rep.rem) % 10; } // Calculates the binomial coefficients C(m, k) % 10 for k = 0 to m. vector<int> get_coeffs(int m) { array<int, 10> inv_mod10{}; inv_mod10[1] = 1; inv_mod10[3] = 7; inv_mod10[7] = 3; inv_mod10[9] = 9; vector<int> coeffs(m + 1); FactorRep current_coeff = {0, 0, 1}; coeffs[0] = 1; coeffs[m] = 1; for (int k = 1; k <= m / 2; ++k) { FactorRep num_factors = get_factors(m - k + 1); FactorRep den_factors = get_factors(k); current_coeff.p2 += num_factors.p2 - den_factors.p2; current_coeff.p5 += num_factors.p5 - den_factors.p5; int inv = inv_mod10[den_factors.rem]; current_coeff.rem = (current_coeff.rem * num_factors.rem * inv) % 10; coeffs[k] = to_int(current_coeff); coeffs[m - k] = coeffs[k]; } return coeffs; } public: int triangularSum(vector<int>& nums) { const int m = nums.size() - 1; if (m < 0) return 0; if (m == 0) return nums[0]; // Step 1: Get the binomial coefficients. // All complex logic is now encapsulated in the get_coeffs helper function. vector<int> coeffs = get_coeffs(m); // Step 2: Calculate the final weighted sum. int ans = 0; for (int i = 0; i <= m; ++i) { ans = (ans + coeffs[i] * nums[i]) % 10; } return ans; } }; ``` ### 結語 從一個看似簡單的陣列問題出發，我們經歷了從模擬到組合數學，再到最終的數論解法。這個過程完美地展示了演算法優化的魅力所在：它不僅僅是寫出能運作的程式碼，更是尋找一種更深刻、更本質的數學結構，並將其轉化為高效的計算策略。 下一次當你遇到一個看似只能暴力解決的問題時，不妨停下來想一想，背後是否也隱藏著這樣一條通往 $O(n)$ 的優雅捷徑呢？