🚀 LeetCode 3653 解題解析：從暴力解到「根號分治 × 乘法差分陣列」

題目連結：3653. XOR After Range Multiplication Queries I

這道題目要求我們對一個陣列進行多次查詢：每次以固定的步伐 k，將區間 [l, r] 內（每隔 k 步）的元素乘上某個數字 v，最後求整個陣列的 XOR 總和。

如果測資很小，雙層 for 迴圈就能輕鬆解決；但如果陣列長度 N 和查詢次數 Q 都高達十萬呢？這時就需要拿出更高階的武器了！

🛑 第一步：為什麼原本的方法會慢？（痛點分析）

讓我們先回顧一下原本直覺的寫法：

for l, r, k, v in queries:
    for i in range(l, r + 1, k):
        nums[i] = (nums[i] * v) % MOD

想像一下最壞的情況：
假設陣列長度 N = 100,000，然後有一萬筆查詢，每一筆的步伐 k = 1（也就是每次都要修改整個陣列）。
這時，內層迴圈每次都要跑十萬次，總共要跑 10,000 × 100,000 = 1,000,000,000（十億）次！程式絕對會跑到超時 (Time Limit Exceeded)。

💡 發現問題點： 當步伐 k 很小的時候，我們會浪費大量的時間在迴圈上。

⚔️ 第二步：降維打擊武器一 ——「根號分治」(分塊)

既然 k 很小的時候會出問題，那我們就根據 k 的大小來「分工合作」吧！這就是根號分治 (Square Root Decomposition) 的核心思想。

我們設定一個界線，通常是陣列長度的平方根，也就是 B = √N（當 N=100,000 時，B ≈ 316）。我們把查詢分成兩派：

• 🏃‍♂️ 大步伐派 (k > B)： 因為步伐很大（每次至少跳 316 格），就算跑完整個陣列，最多也只會跳 316 次。次數非常少！對於這類查詢，我們直接使用原本的 for 迴圈暴力更新，速度其實非常快。
• 🚶‍♂️ 小步伐派 (k ≤ B)： 步伐很小，每次查詢都要跳好幾萬次。對於這類查詢，我們絕對不能用迴圈慢慢跳，我們需要引入下一個武器來「批次處理」。

🛡️ 第三步：降維打擊武器二 ——「乘法差分陣列」

對於小步伐的查詢，我們怎麼批次處理呢？答案是 差分陣列 (Difference Array)。

想像一個情境：你要在 [l, r] 區間內的所有數字都乘上 v。

• 傳統做法： 一個一個乘。
• 差分做法： 我只在起點 l 做個記號「從這裡開始乘上 v」，然後在終點的下一格 r + 1 做個記號「從這裡開始取消乘上 v 的影響」。最後，我只要從頭走到尾掃描一次，就能把這些記號擴散到整個陣列！

⚠️ 致命的數學陷阱：如何取消乘法？
在普通的數學裡，要取消「乘以 v」，我們只要「除以 v」就好。
但是！我們的題目要求對 10**9 + 7 取餘數 (% MOD)。在有取餘數的世界裡，除法是會壞掉的！

這時，我們就要請出 Python 的內建魔法：模逆元 (Modular Multiplicative Inverse)。
簡單來說，模逆元就是一個神奇的數字，當你乘上這個數字時，效果就等同於「除以 v」。

在 Python 3.8 以後，計算模逆元只需要一行程式碼：

inv_v = pow(v, -1, MOD)  # 取得 v 的模逆元，完美代替除法！

💡 為什麼需要「差分陣列」？（用最簡單的話說）

先忘記乘法，想一下加法。如果我要把陣列中 [1] 到 [5] 的位置都 +10。
笨方法是：a[1]+=10, a[2]+=10, a[3]+=10, a[4]+=10, a[5]+=10。
聰明方法（差分）是：我只在起點做記號 diff[1] += 10，然後在終點的下一格做記號 diff[6] -= 10。
最後我只要「從左到右，把前一格的數字加到自己身上（前綴和）」，魔法就會發生：

• i=1: 拿到 +10
• i=2: 繼承前一格的 +10
• ... 一路繼承 ...
• i=6: 繼承了 +10，但是遇到自己這格的 -10，互相抵銷變成 0！從這裡開始又恢復原狀。

🔄 從「加法」變成「乘法」

這題只是把加法變乘法：

• 加法的起點是 +v，乘法的起點就是 *v。
• 加法的終點抵銷是 -v，乘法的終點抵銷就是 /v（也就是乘上模逆元 v⁻¹）。

🦘 加入「步伐 k」的跳躍魔法

這題更進階的地方在於，我們不是連續修改，而是每隔 k 步修改一次。

假設操作是：從 l=1 開始，到 r=5 結束，步伐 k=2，乘上 v=10。
實際要修改的位置是：1, 3, 5。

第一步：做記號

• 起點：diff[1] *= 10
• 終點外：我們實際上跳了 3 次（1, 3, 5），下一次會跳到哪？1 + 3 * 2 = 7。所以在越界的第一個位置做抵銷記號：diff[7] *= 10⁻¹

第二步：跳躍式前綴積展開

以前是「加上前一格」，現在因為步伐是 k=2，我們改成「乘上自己往前退 k 格的數字」。我們來跑一次看看：

一開始的 diff: [1, 10, 1, 1,  1,  1,  1, 10⁻¹]
(index)         0   1  2  3   4   5   6   7

從左到右，每個數字乘上「往前 2 格」的數字：
i=0: 1
i=1: 10
i=2: 1 * (往前2格的 diff[0]=1) = 1
i=3: 1 * (往前2格的 diff[1]=10) = 10  ✅ 成功傳遞給 3 了！
i=4: 1 * (往前2格的 diff[2]=1) = 1
i=5: 1 * (往前2格的 diff[3]=10) = 10  ✅ 成功傳遞給 5 了！
i=6: 1 * (往前2格的 diff[4]=1) = 1
i=7: 10⁻¹ * (往前2格的 diff[5]=10) = 1 ✅ 10 和 10⁻¹ 抵銷，變回 1，停止傳遞！
    

最後展開的 diff 就變成了：[1, 10, 1, 10, 1, 10, 1, 1]。
只有 1, 3, 5 這三個位置變成了 10！然後我們再把這個展開後的 diff 乘回原本的 nums 陣列，就大功告成了！

⚡ 核心加速關鍵：為什麼要「依照步數 k」分組 (Grouping)？

差分陣列本身只是工具，「把相同步伐 k 的查詢合併處理」才是真正的加速引擎。

讓我們來算一筆帳，假設有 10,000 筆查詢，其中有 5,000 筆的步伐都是 k=2。

❌ 做法一：不分組（每來一筆查詢就做一次差分展開）

• 拿一筆 k=2 的查詢，在 diff 陣列做頭尾記號 (2次操作)。
• 掃描一次陣列進行「前綴積展開」，把記號擴散出去 (N 次操作，約 100,000 次)。
• 把這 5,000 筆 k=2 的查詢都這樣做...
• 總運算量： 5,000 × 100,000 = 500,000,000（五億次，還是會超時！）

✅ 做法二：依照步伐分組（批次處理）

• 我們先不急著展開。把這 5,000 筆 k=2 的查詢，全部先在同一個 diff 陣列上「做記號」。
• 做記號非常快，每筆查詢只要修改頭尾兩個數字。5,000 筆查詢做完記號，只需要 10,000 次操作。
• 等這 5,000 筆的記號都做完了，我們只做「一次」前綴積展開 (100,000 次操作)。
• 在這次展開中，5,000 個區間的病毒與解藥會「同時」互相疊加、傳染、抵銷。
• 總運算量： 10,000 (做記號) + 100,000 (一次展開) = 110,000（十一萬次，整整快了近 5000 倍！）

這就是為什麼要配合「根號分治」：
因為我們規定小步伐派的 k ≤ B (約 316)。這代表我們最多只需要展開 316 次！
無論有幾萬筆小步伐查詢，它們都會被分類到這 316 個桶子裡。每個桶子（每種 k）只要花 O(N) 的時間展開一次。
因此，處理所有小步伐查詢的總時間被嚴格限制在 316 × 100,000 ≈ 3千萬次 以內，這在 1 秒的時限內綽綽有餘！

🚧 為什麼不同的步數 (k) 不能共用同一個差分陣列？

這是一個非常敏銳的問題！答案藏在「展開（前綴積）的公式」裡。

讓我們回顧一下展開差分陣列的那行程式碼：

diff[i] = diff[i] * diff[i - k]

致命衝突：記號本身是「沒有記憶」的

假設我們硬把 k=2 和 k=3 的查詢，都做記號在同一個 diff 陣列裡：

• 查詢A (k=2)：在 diff[1] 標記了 *10
• 查詢B (k=3)：在 diff[2] 標記了 *99

現在陣列長這樣：diff = [1, 10, 99, 1, 1, 1...]

問題來了！當我們要掃描陣列把記號擴散出去時，我們該用哪種步伐 k 呢？

• 如果用 k=2 展開：diff[1] 的 10 會正確傳給 diff[3]。但是！diff[2] 上的 99（本來是 k=3 專用的），也會被當成 k=2，錯誤地傳給 diff[4]！
• 如果用 k=3 展開：diff[2] 的 99 會正確傳給 diff[5]。但是 diff[1] 上的 10 會被錯誤地傳給 diff[4]。

白話文比喻：

這就像是車站裡有「每 2 站停一次的區間車」和「每 3 站停一次的快車」。
你在第 1 站放了一個包裹 (記號)。如果沒有分開月台（不同的 diff 陣列），當列車進站時，包裹根本不知道自己該上哪一班車！它只是一個數字，無法告訴展開的迴圈：「嘿！我是屬於 k=2 的，請每隔 2 格複製我一次。」

結論：

因為擴散的步伐（傳染的方向）是由展開時的 k 決定的，所以：
👉 同一個 diff 陣列在展開時，只能服務一種 k。
這就是為什麼我們要在外層寫一個 for k in range(1, B + 1):，每次輪到一個新的 k，我們就把 diff 陣列清空重置，讓它專心只處理這批步伐為 k 的包裹！

🧩 第四步：將所有拼圖組合起來 (完整程式碼解析)

現在我們擁有了所有武器，來看看完整的高階寫法是如何運作的：

import math
from typing import List

class Solution:
    def xorAfterQueries(self, nums: List[int], queries: List[List[int]]) -> int:
        MOD = 10**9 + 7
        n = len(nums)
        
        # 【策略一：根號分治】計算閾值 B
        B = max(1, math.isqrt(n))
        
        # 準備空陣列，用來依照步長 k 分組存放小步伐查詢
        grouped_queries = [[] for _ in range(B + 1)]
        
        # 分流查詢
        for l, r, k, v in queries:
            if v == 1: continue  # 小優化：乘數為 1 不改變數字
            
            if k <= B:
                # 步伐小，存起來等一下批次處理
                grouped_queries[k].append((l, r, v))
            else:
                # 步伐大，直接暴力更新 (次數保證小於 B)
                for i in range(l, r + 1, k):
                    nums[i] = (nums[i] * v) % MOD
        
        # 【策略二：乘法差分】處理小步伐查詢
        diff = [1] * n
        for k in range(1, B + 1):
            if not grouped_queries[k]: continue
            
            # 每次換新的步長 k，重置差分陣列
            for i in range(n): diff[i] = 1
            
            for l, r, v in grouped_queries[k]:
                # 1. 區間起點：標記乘上 v
                diff[l] = (diff[l] * v) % MOD
                
                # 2. 區間終點外：計算越界的第一個位置
                num_steps = (r - l) // k
                next_idx = l + (num_steps + 1) * k
                
                if next_idx < n:
                    # 標記乘上 v 的反元素 (相當於除以 v，用來抵銷)
                    inv_v = pow(v, -1, MOD)
                    diff[next_idx] = (diff[next_idx] * inv_v) % MOD
            
            # 3. 前綴積展開：將記號擴散回原陣列
            for i in range(n):
                if i >= k:
                    diff[i] = (diff[i] * diff[i - k]) % MOD
                if diff[i] != 1:
                    nums[i] = (nums[i] * diff[i]) % MOD
                    
        # 【最終收尾】：計算 XOR 總和
        result = 0
        for num in nums:
            result ^= num
            
        return result

🚀 進階優化：極致的效能突破 (殘差類掃描)

如果把上述的「標準版根號分治」提交，已經能順利通過。但你會發現有些解法跑得快上數倍，這是因為標準寫法中仍有許多可以壓榨效能的空間。以下是四個極致優化的關鍵：

1. 只處理「真正出現」的步伐 k

標準版中，for k in range(1, B + 1) 會跑滿所有可能的 k 值（例如 316 次），即使某些 k 根本沒有出現在查詢中。進階版改用字典 (Dictionary)，只迭代有實際查詢的 k。

2. 捨棄 O(N) 的全域陣列重置

標準版每換一個 k，就要花 O(N) 把整個 diff 陣列清為 1。進階版不再使用全域 diff，而是只把「事件 (起點與終點)」存起來，省去了巨大的重置開銷。

3. 殘差類 (Residue Class) 獨立掃描

這是最核心的架構改變。我們把查詢按照起點 l % k 分組（稱為殘差類）。例如 k=2 時，分成了「奇數索引組」和「偶數索引組」。

• 每個殘差類內的事件各自排序。
• 掃描時，用雙指標 (Two Pointers) 順著步長 k 往前跳，中途遇到事件就即時套用乘數。
• 好處：如果某個殘差類完全沒有查詢，就可以直接跳過，連掃描都不用掃！

4. 延遲寫回 nums (Lazy Update)

標準版每處理完一種 k，就去更新一次 nums 陣列。進階版準備了一個 factors 陣列來累積所有小步伐的乘積，最後才統一更新到 nums 陣列，將記憶體寫入次數降到最低。

以下是融合了上述所有優化技巧的「極速版」程式碼：

from typing import List
import math
from collections import defaultdict

class Solution:
    def xorAfterQueries(self, nums: List[int], queries: List[List[int]]) -> int:
        MOD = 10**9 + 7
        n = len(nums)
        if n == 0: return 0
        
        # 【策略一：根號分治】
        B = int(math.sqrt(n)) + 1
        
        # 只記錄有出現的小步伐查詢
        small = defaultdict(list)
        
        # 處理大步伐 (直接暴力做)
        for l, r, k, v in queries:
            if k >= B:
                idx = l
                while idx <= r:
                    nums[idx] = (nums[idx] * v) % MOD
                    idx += k
            else:
                small[k].append((l, r, v))
                
        # factors 用來累積所有小步伐造成的最終乘數
        factors = [1] * n
        
        # 【策略二：殘差類掃描 (Residue Class Sweep)】
        for k, qlist in small.items():
            # 依照 l % k 分組記錄事件
            events = [[] for _ in range(k)]
            
            for l, r, v in qlist:
                res = l % k
                step = (r - l) // k
                last = l + step * k
                
                # 放入事件：(起點, 乘上 v)
                events[res].append((l, v))
                
                # 放入事件：(終點外, 乘上 v 的模逆元抵銷)
                end_idx = last + k
                if end_idx < n:
                    inv_v = pow(v, MOD - 2, MOD) # 費馬小定理求模逆元
                    events[res].append((end_idx, inv_v))
                    
            # 針對每個殘差類獨立掃描
            for res in range(k):
                ev = events[res]
                if not ev: continue
                
                ev.sort() # 依照 index 排序事件
                cur_multiplier = 1
                ptr = 0
                m = len(ev)
                
                # 順著步伐 k 跳躍掃描
                i = res
                while i < n:
                    # 如果走到事件觸發點，更新目前的乘數
                    while ptr < m and ev[ptr][0] == i:
                        cur_multiplier = (cur_multiplier * ev[ptr][1]) % MOD
                        ptr += 1
                        
                    factors[i] = (factors[i] * cur_multiplier) % MOD
                    i += k
                    
        # 【最終收尾】統一將累積的乘數寫回 nums，並計算 XOR
        ans = 0
        for i in range(n):
            nums[i] = (nums[i] * factors[i]) % MOD
            ans ^= nums[i]
            
        return ans

🌟 同場加映：極速版 C++ 實作

競技程式設計界最受歡迎的 C++ 實作版本。邏輯與上述 Python 極速版完全相同，加上了快速冪 (Binary Exponentiation) 來手動實作模逆元，在 LeetCode 上能達到極低的執行時間與記憶體消耗。

#include <vector>
#include <cmath>
#include <unordered_map>
#include <algorithm>

using namespace std;

class Solution {
public:
    int xorAfterQueries(vector<int>& nums, vector<vector<int>>& queries) {
        long long MOD = 1e9 + 7;
        int n = nums.size();
        if (n == 0) return 0;
        
        // 【策略一：根號分治】
        int B = sqrt(n) + 1;
        
        // 紀錄小步伐查詢
        unordered_map<int, vector<vector<int>>> small;
        
        // 處理大步伐
        for (const auto& q : queries) {
            int l = q[0], r = q[1], k = q[2], v = q[3];
            if (v == 1) continue; // 小優化：乘數為 1 不改變數字
            
            if (k >= B) {
                int idx = l;
                while (idx <= r) {
                    nums[idx] = (1LL * nums[idx] * v) % MOD;
                    idx += k;
                }
            } else {
                small[k].push_back({l, r, v});
            }
        }
        
        // factors 用來累積所有小步伐的乘數
        vector<long long> factors(n, 1);
        
        // 快速冪 (用於費馬小定理求模逆元)
        auto power = [&](long long base, long long exp) {
            long long res = 1;
            base %= MOD;
            while (exp > 0) {
                if (exp % 2 == 1) res = (res * base) % MOD;
                base = (base * base) % MOD;
                exp /= 2;
            }
            return res;
        };
        
        // 【策略二：殘差類掃描】
        for (const auto& [k, qlist] : small) {
            // events[res] 存放 (index, factor) 對
            vector<vector<pair<int, long long>>> events(k);
            
            for (const auto& q : qlist) {
                int l = q[0], r = q[1];
                long long v = q[2];
                
                int res = l % k;
                int step = (r - l) / k;
                int last = l + step * k;
                
                events[res].push_back({l, v});
                
                int end_idx = last + k;
                if (end_idx < n) {
                    long long inv_v = power(v, MOD - 2);
                    events[res].push_back({end_idx, inv_v});
                }
            }
            
            // 獨立掃描每個殘差類
            for (int res = 0; res < k; ++res) {
                auto& ev = events[res];
                if (ev.empty()) continue;
                
                sort(ev.begin(), ev.end());
                
                long long cur_multiplier = 1;
                int ptr = 0;
                int m = ev.size();
                
                // 順著步伐 k 往前跳
                for (int i = res; i < n; i += k) {
                    while (ptr < m && ev[ptr].first == i) {
                        cur_multiplier = (cur_multiplier * ev[ptr].second) % MOD;
                        ptr++;
                    }
                    factors[i] = (factors[i] * cur_multiplier) % MOD;
                }
            }
        }
        
        // 統一寫回 nums 並計算 XOR
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            nums[i] = (1LL * nums[i] * factors[i]) % MOD;
            ans ^= nums[i];
        }
        
        return ans;
    }
};

🌍 走出競技場：這些技巧在工業界的真實身影

這道題目中用到的技巧，剝開數學的外衣後，其實就是工業界底層系統架構的核心哲學。我們來看看它們在真實世界中的對應：

1. 📷 影像處理 (Computer Vision)

• 積分圖 (Integral Image) = 二維前綴和/差分：
  在早期非常著名的 Viola-Jones 人臉偵測演算法 中，需要瘋狂計算圖片中任意矩形區域的像素總和。如果每次都用雙層迴圈加總，相機根本無法做到即時偵測。解法就是建構一張「積分圖」（二維前綴和）。建好之後，不管矩形多大，只要查表 4 個頂點的座標做加減，O(1) 就能得到總和！這就是差分陣列的二維直系血親。
• Bayer 濾色陣列與步伐 k：
  相機感光元件 (CMOS) 上的像素排列通常是 RGGB（Bayer pattern）。如果你要對所有的綠色 (G) 像素做白平衡補償，你就必須在記憶體中進行「跨步 (Strided)」的陣列修改。這就是我們題目中 k=2 步伐操作的物理硬體展現。

2. 🧠 AI 與深度學習 (Deep Learning)

• FlashAttention = 分塊處理 (Tiling / Block Decomposition)：
  最近幾年大語言模型 (LLM) 最重要的突破之一就是 FlashAttention。當輸入文本很長時，Attention 矩陣會大到 GPU 記憶體塞不下。FlashAttention 的做法就是「分塊 (Tiling)」：把大矩陣切成一塊塊能塞進 GPU 超高速 SRAM 的小區塊，算完再合併。這與「根號分治 (把 N 切成 √N 的區塊)」在精神上完全一致：根據硬體的極限（閾值 B）來決定任務的切分方式。
• 空洞卷積 (Dilated Convolution) = 跳躍 k 步的修改：
  在影像語意分割 (如 DeepLab) 中，為了在不增加計算量的情況下擴大 AI 的「視野 (Receptive Field)」，卷積核會「跳著」掃描像素（例如每隔 2 格、4 格取樣）。這與我們題目的跳躍步伐 k 概念如出一轍。
• 線性 RNN (如 Mamba, RWKV) = 前綴積的極致：
  為了取代 Transformer 龐大的注意力機制，最新的架構利用「前綴和 / 前綴積 (Cumulative Sum/Prod)」的概念，把歷史的對話記憶壓縮成一個狀態向量（只跟前一時刻有關），這正是我們在差分陣列最後一步 diff[i] = diff[i] * diff[i-k] 所做的事情！

3. 🐧 Linux Kernel 與底層系統

• 差分陣列的靈魂 = 延遲計算 (Lazy Evaluation) & 批次寫入：
  差分陣列的本質是「先記帳，最後再一次結帳」。這在 Linux 裡無處不在：
  • Page Cache (Dirty Pages)： 寫入檔案時不會立刻動到硬碟，而是在記憶體標記 Dirty（像差分做記號），等到作業系統覺得夠多了，再一次 Flush 到磁碟（像前綴和展開）。
  • CFS (完全公平排程器)： 在計算 CPU 任務的虛擬運行時間 (vruntime) 時，Kernel 也是累積時間的 Delta (差值)，而不是每個 CPU 時脈週期都去更新所有 Process 的樹狀結構。
• 大小任務分流 (Heavy/Light Routing)：
  我們在演算法中把查詢分成「大步伐」和「小步伐」。在網路封包處理（如 Linux NAPI）或中斷處理 (Interrupt Handling) 中，如果封包量少（小任務），就觸發中斷；如果封包量如海嘯般湧來（大任務），網卡驅動會關閉中斷，改用「輪詢 (Polling)」把封包整批掃進來。這就是真實世界的根號分治：根據流量的閥值，切換兩種完全不同的處理策略！

總結：
你在這題看到的「差分陣列」，在系統工程裡叫做 Delta Tracking (差分追蹤) 或 Lazy Evaluation (延遲計算)。
你看到的「根號分治」，在系統工程裡叫做 Tiling (快取分塊) 或 Heavy/Light Routing (冷熱路徑分流)。
演算法題目，其實就是把這些複雜的系統瓶頸，抽象成了純粹的數學遊戲！

🎉 總結

透過「根號分治」，我們巧妙地避開了 k 極大或極小的極端情況；再透過「乘法差分」與 Python 的 pow(v, -1, MOD)，我們把複雜的多次區間操作，壓縮成了輕鬆的頭尾標記。這就是演算法之美！

喜歡這篇解析的話，也歡迎到 LeetCode 3653 實際挑戰看看！

🚀 深入淺出模逆元：費馬小定理與快速冪的完美結合

在解決涉及「巨大數字」與「取餘數 (Modulo)」的演算法題目時，我們經常會遇到一個棘手的問題：加、減、乘法都可以直接在取餘數的狀態下進行，唯獨「除法」不行。

為了解決除法失效的問題，數學家們引入了「模逆元 (Modular Multiplicative Inverse)」的概念，而最優雅的實作方式，莫過於結合「費馬小定理」與「快速冪」。這篇文章將帶您一步步拆解其中的奧秘。

🛑 第一步：為什麼取餘數的世界裡，除法會壞掉？

讓我們先來看一個簡單的例子：我們想要計算 (12 / 4) % 7。

• 在正常的數學裡：12 / 4 = 3，然後 3 % 7 = 3。答案是 3。

現在，如果我們在計算過程中，數字已經因為太大而被取過餘數了呢？

• 12 % 7 = 5。
• 如果我們拿取完餘數的數字直接去除：5 / 4 = 1.25。
• 1.25 是小數！在取餘數的整數運算世界裡，這完全失去了意義。

🔄 第二步：模逆元的救贖 (Modular Multiplicative Inverse)

既然不能「除以 4」，那我們能不能改成「乘以某個數字」？

在普通的數學裡，除以 4 等同於乘以 0.25（因為 4 × 0.25 = 1，它們互為倒數）。
在模 7 的世界裡，我們也在尋找一個數字 X，使得 (4 × X) % 7 = 1。這個 X 就是 4 在模 7 底下的模逆元。

讓我們暴力找找看 X 是多少：

• 4 × 1 = 4 ≡ 4 (mod 7)
• 4 × 2 = 8 ≡ 1 (mod 7) 🎯 找到了！

所以，在模 7 的世界裡，「除以 4」就等同於「乘以 2」！

我們回頭驗證一開始的算式：
先取餘數：12 % 7 = 5
把除以 4 改成乘以 2：5 × 2 = 10
再取餘數：10 % 7 = 3。答案完美吻合！

📜 第三步：費馬小定理 (Fermat's Little Theorem)

雖然我們可以用迴圈暴力找出模逆元，但當模數 P = 10^9 + 7（十億等級的質數）時，暴力尋找會非常慢。這時候，偉大的費馬小定理就派上用場了。

💡 費馬小定理：
如果 P 是一個質數，且 A 不是 P 的倍數，那麼：

A^P-1 ≡ 1 (mod P)

我們把這個等式稍微拆解一下，把其中一個 A 獨立出來：

A × A^P-2 ≡ 1 (mod P)

看出來了嗎？根據模逆元的定義（A × X ≡ 1），這個 AP-2 完美符合 X 的位置！

結論：在模 P 的世界裡，數字 A 的模逆元就是 A^P-2 (mod P)。

⚡ 第四步：快速冪 (Binary Exponentiation) —— O(log N) 的超光速引擎

雖然我們得出模逆元是 AP-2，但當 P = 10^9 + 7 時，我們要計算 A1000000005。如果傻傻地用 for 迴圈乘十億次，肯定會超時 (TLE)。

為了解決這個問題，我們使用快速冪 (Binary Exponentiation) 技巧。它的核心概念是「倍增」。

💻 第五步：程式碼實作

有了費馬小定理與快速冪的觀念，求模逆元的實作就非常簡單了。在 Python 中甚至有內建的高效寫法；而在 C/C++ 中，我們通常會自己實作一個 power 函數。

Python 實作

Python 從 3.8 版本開始，內建的 pow 函數直接支援了求模逆元，只要將指數設為 -1 即可（底層自動採用快速冪與擴展歐幾里得演算法）：

MOD = 10**9 + 7
v = 4

# Python 內建魔法，直接求 4 在模 10^9+7 下的模逆元
inv_v = pow(v, -1, MOD)

# 或是手動利用費馬小定理：v^(MOD-2) % MOD
inv_v_fermat = pow(v, MOD - 2, MOD)

print(inv_v) # 輸出：250000002

C++ 實作

在 C++ 中，我們需要手動實作快速冪函數（Binary Exponentiation）：

#include <iostream>

long long MOD = 1e9 + 7;

// 快速冪實作：計算 (base^exp) % MOD
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        // 如果當前二進位最低位是 1，則乘上當前的 base
        if (exp % 2 == 1) {
            res = (res * base) % MOD;
        }
        // base 自我平方 (A^1 -> A^2 -> A^4 -> A^8 ...)
        base = (base * base) % MOD;
        // 將 exp 右移一位 (等同於 exp /= 2)
        exp /= 2;
    }
    return res;
}

// 求模逆元
long long modInverse(long long n) {
    // 根據費馬小定理，逆元為 n^(MOD-2)
    return power(n, MOD - 2);
}

int main() {
    long long v = 4;
    std::cout << "4 的模逆元是: " << modInverse(v) << std::endl;
    // 驗證： (4 * 250000002) % 1000000007 == 1
    return 0;
}

🎉 總結

在涉及大數取餘數的運算中，模逆元是我們繞過「除法禁區」的唯一橋樑。而費馬小定理與快速冪的結合，不僅在數學上極具美感，更是將工業界效能極限（將十億次迴圈化為 30 次運算）展現得淋漓盡致！

ChromeOS Flex 內建 WireGuard VPN 連線 Tailscale 指南

這算是個 workaround 等到哪天 ChromeOS Flex 可以支援使用 Tailscale 就不需要了，筆記在 https://hackmd.io/@fourdollars/UsingTailscaleOnChromeOSFlex