猴子分桃子問題的逆向思維解法：從最後一只猴子推導最小桃子數

題目回顧

5 只猴子分桃子，每只將剩餘桃子分 5 份，多 1 個扔海裡，拿走 1 份。求最少初始桃子數。

正向模擬難點

正向枚舉初始數 `N`，每步驗證 `(N-1)%5==0` 並更新 `N = (N-1)/5*4`，需嘗試大量 `N`，效率低且邏輯易寫錯 (如題主代碼)。

逆向推導 (數學本質)

設第 5 只猴子操作**前**剩 `x5` 個，操作**後**剩 `x6` 個。
根據規則：`x5 = x6 * 5 / 4 + 1`，且 `x5` 必須是整數 → `x6` 必須使 `x6*5` 能被 4 整除 → `x6` 是 4 的倍數。
同理倒推到第 1 只猴子操作前 (`x1`)，即初始桃子數。

精簡 Java 實現

public class MonkeyPeach {
    public static void main(String[] args) {
        // 從第 5 只猴子操作後剩餘桃子數開始嘗試 (最小為 4 的倍數)
        for (int after = 4; ; after += 4) {
            int current = after;
            boolean valid = true;
            // 倒推 5 步
            for (int i = 0; i < 5; i++) {
                // 逆向公式：前 = 後 * 5 / 4 + 1
                if ((current * 5) % 4 != 0) { // 中間必須整除
                    valid = false;
                    break;
                }
                current = current * 5 / 4 + 1;
            }
            if (valid) {
                System.out.println("最少桃子數: " + current); // 輸出 3121
                break;
            }
        }
    }
}

關鍵點解析

• **起始值 `after = 4`**：最後一只猴子操作後剩餘桃子必須是 4 的倍數 (因為倒推需 `*5/4` 整除)。
• **步長 `+= 4`**：只檢查 4 的倍數，減少 75% 迭代。
• **循環 5 次**：對應 5 只猴子，每次應用逆向公式。
• **整除檢查** `(current * 5) % 4 == 0`：確保中間狀態合法。

結果驗證

輸出 `3121`。正向驗證：

3121 -> 猴1: (3121-1)/5=624 拿走, 剩 2496
2496 -> 猴2: (2496-1)/5=499 拿走, 剩 1996
1996 -> 猴3: (1996-1)/5=399 拿走, 剩 1596
1596 -> 猴4: (1596-1)/5=319 拿走, 剩 1276
1276 -> 猴5: (1276-1)/5=255 拿走, 剩 1020
全程滿足條件。

總結

**逆向思維 + 數學約束 (整除性) + 最小枚舉** 是解決此類「連續分割取餘」問題的通用高效模式，時間復雜度近乎 O(1)。