HDU 5047 Sawtooth：平面分割與「M」型圖形的最大區域數

問題背景

在平面幾何中，直線劃分平面區域是經典問題：一條直線分成 2 區域，兩條最多 4 區域，三條最多 7 區域，以此類推。HDU 5047 Sawtooth 將此推廣到由兩條同向平行射線與兩條線段組成的「M」型圖形。給定 N 個這樣的「M」，求它們能將平面劃分出的最大區域數。

幾何觀察與公式推導

觀察可知，任意兩個「M」之間最多產生 16 個交點。若將 N 個「M」依次加入，第 i 個「M」與前 i-1 個各產生 16 個交點，總交點數為：

\[ \sum_{i=1}^{N-1} 16i = 8N(N-1) \]

根據平面圖的歐拉特性：區域數 = 邊數 + 點數 + 1。經推導，最大區域數公式為：

\[ R(N) = 8N^2 - 7N + 1 \]

也可寫作 \( N(8N-7) + 1 \)。

大數處理策略

因 \( N \le 10^{12} \)，\( 8N^2 \) 達 \( 8 \times 10^{24} \)，超出 64 位整數範圍。解法採用 分塊乘法：設 \( M = 8N - 7 \)，將 M 分為高低兩段（基數 \( 10^6 \)），分別與 N 相乘，再合併進位。具體步驟：

• \( M_{\text{low}} = M \bmod 10^6 \)，\( M_{\text{high}} = M / 10^6 \)
• \( \text{low} = M_{\text{low}} \times N + 1 \)，\( \text{high} = M_{\text{high}} \times N \)
• 處理 low 進位到 high，最後按高低段輸出

核心代碼（C++）

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const ll MOD = 1000000;

int main() {
    int T, cas = 1;
    scanf("%d", &T);
    while (T--) {
        ll n;
        scanf("%lld", &n);
        ll m = (n << 3) - 7;        // 8*n - 7
        ll high = m / MOD;
        ll low  = m % MOD;
        high *= n;
        low  = low * n + 1;
        high += low / MOD;
        low  %= MOD;
        printf("Case #%d: ", cas++);
        if (high) printf("%lld%06lld\n", high, low);
        else      printf("%lld\n", low);
    }
    return 0;
}

複雜度分析

每測試案例僅涉及常數次 64 位運算，時間複雜度 \( O(1) \)，空間 \( O(1) \)。可輕鬆應對 \( T \le 10^5 \) 的大規模輸入。

總結

本題結合了組合幾何與大整數技巧，關鍵在於發現「M」型圖形的固定交點數 16，進而推導出二次多項式公式，並以分塊乘法繞過語言內建類型限制。這類「找規律 + 推公式 + 高精度」的思路在 ACM/ICPC 區域賽中極為常見。