# 分治算法专题讲义

---

## 一、 引导案例：找假币问题

为了理解分治算法的思想，我们先来看一个经典的**找假币问题**：

> **问题描述**：袋子中装有 16 个硬币，其中有一个是伪造的。已知伪造的硬币比真硬币稍轻。现有一台天平（无砝码），可以通过比较两组硬币的重量来判断其轻重。如何找出这个假币？

*   **方法一（逐个比较）**：
    先称量硬币 1 和硬币 2。如果重量不等，轻的那枚就是假币；如果相等，再称量硬币 3 和硬币 4……以此类推。这种方法在最坏情况下需要比较 **8 次**才能找到假币。
*   **方法二（二分法）**：
    将 16 个硬币均分为两组（每组 8 个）进行称量。较轻的那组必含有假币。接着将该组再均分为两组（每组 4 个）进行称量……如此循环，只需 **4 次**便能确定假币。
*   **方法三（三分法）**：
    将 16 个硬币分成三组：A 组 5 个、B 组 5 个、C 组 6 个。
    首先称量 A 组和 B 组：
    *   如果 A 和 B 重量相等，说明假币在 C 组（6 个）。接下来把 C 组分成 2 个、2 个、2 个三组继续称量。
    *   如果 A 和 B 重量不等，假币就在较轻的那一组。
    通过这种方法，最多只需 **3 次**称量即可找出假币。

**核心结论**：将一个规模较大的问题，分解为若干个规模较小的同类子问题，然后逐个击破，这就是**分治（Divide and Conquer）**的核心思想。

---

## 二、 分治算法基本概念

### 1. 定义与基本策略
分治法是将一个难以直接解决的大问题，**分割**成 $k$ 个规模较小的子问题。这些子问题相互独立，且与原问题结构相同（或类似）。我们递归地解决这些子问题，然后将子问题的解**合并**，从而得到原问题的解。

为了使算法保持平衡，通常采用**平衡子问题**的设计思想，即将大问题均匀地分解为 $k$ 个规模几乎相等的子问题（最常见的是 $k=2$，即二分法）。

### 2. 分治法的三步曲
在每一层递归上，分治法都包含以下三个核心步骤：
1.  **分解（Divide）**：将原问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。
2.  **解决（Conquer）**：若子问题规模较小且易于解决，则直接求解；否则，递归地求解各个子问题。
3.  **合并（Combine）**：将各个子问题的解合并为原问题的解。

---

## 三、 经典应用解析与程序实现

### 例 1. 循环比赛日程表

#### 问题描述
设有 $n = 2^m$ 名选手进行循环比赛。要求：
1.  每名选手要与其他 $n-1$ 名选手各赛一次。
2.  每名选手每天只能比赛一次。
3.  循环赛共进行 $n-1$ 天，且每天没有选手轮空。

#### 问题分析
以 8 名选手为例，其日程表是一个具有对称性的 $8 \times 8$ 方阵：

$$
\begin{array}{cccc|cccc}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\\
2 & 1 & 4 & 3 & 6 & 5 & 8 & 7 \\\
3 & 4 & 1 & 2 & 7 & 8 & 5 & 6 \\\
4 & 3 & 2 & 1 & 8 & 7 & 6 & 5 \\\
\hline
5 & 6 & 7 & 8 & 1 & 2 & 3 & 4 \\\
6 & 5 & 8 & 7 & 2 & 1 & 4 & 3 \\\
7 & 8 & 5 & 6 & 3 & 4 & 1 & 2 \\\
8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 
\end{array}
$$

将方阵一分为四：
*   **左上角**的 $4 \times 4$ 方阵是前 4 位选手的日程表。
*   **右上角**的 $4 \times 4$ 方阵是后 4 位选手的日程表，它在本质上与左上角相同，只需将左上角的所有元素加上 $4$ 即可。
*   **左下角**和**右下角**则表示两组选手之间的交叉比赛情况。利用对称性：
    *   左下角方阵可以通过复制右上角方阵得到。
    *   右下角方阵可以通过复制左上角方阵得到。

由此，我们可以通过递归或迭代，将大方阵分解为小方阵来构造。

#### 完整代码实现

##### 递归写法
```cpp
#include <iostream>
using namespace std;

const int MAXN = 65;
int table[MAXN][MAXN];

// 填充矩形区域 [a1..a2] × [b1..b2]，填入数值范围 [x..y]
void make_table(int a1, int b1, int a2, int b2, int x, int y) {
    if (x == y) {
        table[a1][b1] = x;
    } else {
        // 计算区域的中点坐标
        int a3 = (a1 + a2) / 2;
        int b3 = (b1 + b2) / 2;
        // 计算数值的中点
        int xy = (x + y) / 2;
        
        make_table(a1, b1, a3, b3, x, xy);                 // 左上角
        make_table(a1, b3 + 1, a3, b2, xy + 1, y);         // 右上角
        make_table(a3 + 1, b1, a2, b3, xy + 1, y);         // 左下角
        make_table(a3 + 1, b3 + 1, a2, b2, x, xy);         // 右下角
    }
}

int main() {
    int m;
    if (!(cin >> m)) return 0;
    int n = 1 << m;  // n = 2^m
    
    make_table(1, 1, n, n, 1, n); // 填充整个 n×n 区域，数值范围 [1, n]
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << table[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}
```

##### 迭代写法
```cpp
#include <iostream>
using namespace std;

const int MAXN = 1025;
int a[MAXN][MAXN];

int main() {
    int m;
    if (!(cin >> m)) return 0;
    
    int n = 1 << m;  // n = 2^m
    a[1][1] = 1;
    
    // 从 1x1 方阵开始，逐步向外扩展
    for (int size = 1; size < n; size *= 2) {
        // 构造右上角方阵 = 左上角 + size
        for (int i = 1; i <= size; i++) {
            for (int j = 1; j <= size; j++) {
                a[i][j + size] = a[i][j] + size;
            }
        }
        // 构造左下角方阵 = 右上角方阵
        for (int i = 1; i <= size; i++) {
            for (int j = 1; j <= size; j++) {
                a[i + size][j] = a[i][j + size];
            }
        }
        // 构造右下角方阵 = 左上角方阵
        for (int i = 1; i <= size; i++) {
            for (int j = 1; j <= size; j++) {
                a[i + size][j + size] = a[i][j];
            }
        }
    }
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}
```

---

### 例 2. 求方程的根

#### 问题描述
输入整数 $m, n, p, a, b$（其中 $a < b$，$m, n, p \ge 1$），求方程 $f(x) = m^x + n^x - p^x = 0$ 在区间 $[a, b]$ 内的根。若有根则输出，精确到 $10^{-11}$；若无根则输出 `NO`。

#### 问题分析
由于 $m, n, p \ge 1$，函数 $f(x) = m^x + n^x - p^x$ 在给定区间内通常表现出单调性。若满足 $f(a) \times f(b) \le 0$，根据零点存在定理，区间 $[a, b]$ 内必存在解。
我们可以通过**二分法**来逼近这个解：
1.  令 $x = (a + b) / 2$ 为区间中点。
2.  若 $f(a) \times f(x) < 0$，说明根在 $[a, x]$ 区间，令 $b = x$。
3.  否则，根在 $[x, b]$ 区间，令 $a = x$。
4.  当区间长度 $|b - a|$ 小于给定的精度阈值时，停止迭代。

*注意：在计算 $y^x$ 时，直接使用 `pow(y, x)` 或通过换底公式 `exp(x * log(y))` 计算均可。*

#### 完整代码实现
```cpp
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;

const double ZERO = 1e-11;  // 精度控制

int m, n, p;
double a, b;

// 计算 f(x) = m^x + n^x - p^x
double f(double x) {
    return exp(x * log(m)) + exp(x * log(n)) - exp(x * log(p));
}

int main() {
    if (!(cin >> m >> n >> p >> a >> b)) return 0;
    
    // 判断区间内是否有解
    if (f(a) * f(b) > 0) {
        cout << "NO" << endl;
        return 0;
    }
    
    double x, fa, fx;
    do {
        x = (a + b) / 2;
        fa = f(a);
        fx = f(x);
        
        if (fa * fx < 0) {
            b = x;      // 解在 [a, x] 内
        } else {
            a = x;      // 解在 [x, b] 内
        }
    } while (abs(b - a) >= ZERO);
    
    // 输出结果，使用科学计数法
    printf("%.10E\n", (a + b) / 2);
    printf("%.10E\n", f((a + b) / 2));
    
    return 0;
}
```

---

### 例 3. 取余运算（快速幂）

#### 问题描述
输入三个长整型数 $b, p, k$，求 $b^p \bmod k$ 的值。

#### 问题分析
当 $p$ 很大时，直接计算 $b^p$ 会导致数据溢出且时间复杂度过高。我们可以利用同余定理：

$$(A \times B) \bmod K = ((A \bmod K) \times (B \bmod K)) \bmod K$$

为了降低复杂度，我们可以将指数 $p$ 进行二分分解：
*   若 $p$ 为偶数：$b^p = (b^{p/2})^2$
*   若 $p$ 为奇数：$b^p = (b^{p/2})^2 \times b$

这样可以将计算 $b^p$ 的时间复杂度从 $O(p)$ 降到 $O(\log p)$。

#### 完整代码实现（递归与迭代）

##### 递归写法
```cpp
#include <iostream>
using namespace std;

// 递归快速幂：计算 a^b % n
long long power_mod(long long a, long long b, long long n) {
    if (b == 0) return 1 % n;

long long ans = power_mod(a, b / 2, n);     // 递归计算一半
    ans = (ans * ans) % n;                      // 平方
    if (b & 1) ans = (ans * (a % n)) % n;       // 奇数时额外乘以底数
    
    return ans;
}

int main() {
    long long b, p, k;
    if (cin >> b >> p >> k) {
        long long result = power_mod(b, p, k);
        cout << b << "^" << p << " mod " << k << " = " << result << endl;
    }
    return 0;
}
```

##### 迭代写法
```cpp
long long power_mod(long long a, long long b, long long n) {
    long long res = 1 % n;          
    long long base = a % n;     
    
    while (b > 0) {
        if (b & 1) {               // 如果当前二进制位是 1
            res = (res * base) % n;  
        }
        base = (base * base) % n;    // 底数平方
        b >>= 1;                   // 指数右移一位（相当于除以 2）
    }
    
    return res;
}
```

---

### 例 4. 快速排序

#### 问题描述
给定一个长度为 $n$ 的数组，将其按升序排序。

#### 问题分析
快速排序（Quick Sort）采用分治思想，其核心在于**划分（Partition）**：
1.  **分解**：选择一个基准值（pivot）。通过双指针向中间扫描，将数组划分为两部分，使得左侧所有元素均小于等于基准，右侧所有元素均大于等于基准。
2.  **解决**：递归地对左、右两个子数组进行快速排序。
3.  **合并**：因为在分解的过程中元素已经就位，所以合并步骤不需要进行任何操作。

#### 完整代码实现
```cpp
#include <iostream>
#include <algorithm>
using namespace std;

void qsort(int* arr, int left, int right) { 
    int mid = (left + right) / 2;
    int flag = arr[mid]; // 基准值
    int i = left, j = right;
    
    while (i <= j) {
        // 注意：不取等号。如果取等号，当 flag 是最大值时，i 会溢出越界。
        while (arr[i] < flag) i++;        
        while (arr[j] > flag) j--;        
        if (i <= j) {
            swap(arr[i], arr[j]);
            i++;
            j--;
        }
    }
    
    if (left < j) qsort(arr, left, j);      // 递归处理左半部分
    if (right > i) qsort(arr, i, right);    // 递归处理右半部分
}

int main() {
    int n;
    if (!(cin >> n)) return 0;
    int* a = new int[n];
    for (int i = 0; i < n; i++) cin >> a[i];    
    
    qsort(a, 0, n - 1);
    
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    
    delete[] a;
    return 0;
}
```

---

### 例 5. 归并排序

#### 问题描述
给定一个长度为 $n$ 的数组，将其按升序排序。

#### 问题分析
归并排序（Merge Sort）是标准的分治算法：
1.  **分解**：将数组从中间切成两半。
2.  **解决**：递归地对左半部分和右半部分进行归并排序。
3.  **合并**：使用双指针将两个已经排好序的子序列合并为一个完整的有序序列。

#### 完整代码实现
```cpp
#include <iostream>
using namespace std;

const int N = 100005;
int a[N], tmp[N];

// 合并两个有序区间 [l, mid] 和 [mid+1, r]
void merge(int l, int mid, int r) {
    int i = l;          // 左半部分指针
    int j = mid + 1;    // 右半部分指针
    int k = l;          // 临时数组指针
    
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            tmp[k++] = a[i++];
        } else {
            tmp[k++] = a[j++];
        }
    }
    
    while (i <= mid) tmp[k++] = a[i++];    
    while (j <= r) tmp[k++] = a[j++];    
    
    // 写回原数组
    for (int p = l; p <= r; p++) {
        a[p] = tmp[p];
    }
}

void mergeSort(int l, int r) {
    if (l >= r) return;  
    
    int mid = (l + r) / 2;
    mergeSort(l, mid);      
    mergeSort(mid + 1, r);  
    merge(l, mid, r);       
}

int main() {
    int n;
    if (!(cin >> n)) return 0;
    for (int i = 1; i <= n; i++) cin >> a[i];

mergeSort(1, n);
    
    for (int i = 1; i <= n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}
```

---

### 例 6. 地毯填补问题（棋盘覆盖问题）

#### 问题描述
在一个 $2^k \times 2^k$ 的正方形方格迷宫中，除一个特定的方格（“公主”站立的方格）不能覆盖外，其余方格都需要用 L 型地毯（由三个小方格组成，共四种旋转形态）覆盖。请给出铺满地毯的方案。

#### 问题分析
采用分治策略，将 $2^k \times 2^k$ 的大棋盘划分为四个 $2^{k-1} \times 2^{k-1}$ 的子棋盘：
1.  确定“特殊方格”（公主）落在四个子棋盘中的哪一个。
2.  在中心连接处，放置一个 L 型地毯，使其拐角覆盖除含有公主外的另外三个子棋盘的角格。
3.  通过这种放置方式，另外三个原本没有特殊方格的子棋盘在角格被覆盖后，也转化为了含有“特殊方格”的子问题。
4.  递归处理这四个子棋盘，直至规模缩减为 $1 \times 1$。

#### 完整代码实现
```cpp
#include <iostream>
#include <cstdio>
using namespace std;

// (row, col)：当前子棋盘左上角坐标
// (px, py)：公主（特殊方格）坐标
// n：当前子棋盘大小的对数，即 2^n × 2^n
void dfs(int row, int col, int px, int py, int n) {
    if (n == 0) return;
    
    int k = 1 << (n - 1);  // 子棋盘大小的一半
    
    // 情况1：公主在左上角
    if (px <= row + k - 1 && py <= col + k - 1) {
        printf("%d %d %d\n", row + k, col + k, 3); // 放置3号毯子，拐角在右下
        dfs(row, col, px, py, n - 1);
        dfs(row, col + k, row + k - 1, col + k, n - 1);
        dfs(row + k, col, row + k, col + k - 1, n - 1);
        dfs(row + k, col + k, row + k, col + k, n - 1);
    }
    // 情况2：公主在右上角
    else if (px <= row + k - 1 && py > col + k - 1) {
        printf("%d %d %d\n", row + k, col + k - 1, 1); // 放置1号毯子
        dfs(row, col, row + k - 1, col + k - 1, n - 1);
        dfs(row, col + k, px, py, n - 1);
        dfs(row + k, col, row + k, col + k - 1, n - 1);
        dfs(row + k, col + k, row + k, col + k, n - 1);
    }
    // 情况3：公主在左下角
    else if (px > row + k - 1 && py <= col + k - 1) {
        printf("%d %d %d\n", row + k - 1, col + k, 2); // 放置2号毯子
        dfs(row, col, row + k - 1, col + k - 1, n - 1);
        dfs(row, col + k, row + k - 1, col + k, n - 1);
        dfs(row + k, col, px, py, n - 1);
        dfs(row + k, col + k, row + k, col + k, n - 1);
    }
    // 情况4：公主在右下角
    else {
        printf("%d %d %d\n", row + k - 1, col + k - 1, 4); // 放置4号毯子
        dfs(row, col, row + k - 1, col + k - 1, n - 1);
        dfs(row, col + k, row + k - 1, col + k, n - 1);
        dfs(row + k, col, row + k, col + k - 1, n - 1);
        dfs(row + k, col + k, px, py, n - 1);
    }
}

int main() {    
    int k, x, y;
    if (cin >> k >> x >> y) {
        dfs(1, 1, x, y, k);
    }
    return 0;
}
```

---

### 例 7. 黑白棋子的移动

#### 问题描述
有 $2n$ 个棋子（$n \ge 4$）排成一排，开始时左边全部为白子（`o`），右边全部为黑子（`*`）。每次必须同时移动相邻的两个棋子到空位（`-`）上，不能改变两者的相对左右顺序。求如何通过最少的步数，将棋子移动为黑白相间（`o*o*...o*`）的状态。

#### 问题分析
通过手工推导可以发现，对于任意规模 $n$ 的问题，我们都可以通过两步特定的移动，将其转化为规模为 $n-1$ 的子问题：
1.  将中间相邻的白子和黑子移到末尾的空位。
2.  将右侧倒数第二、三个棋子移动到腾出的中间位置。
3.  如此，问题规模缩减为 $n-1$。
4.  当规模缩减到边界情况 $n=4$ 时，套用固定的 5 步基本移动方案。

#### 完整代码实现
```cpp
#include <iostream>
#include <cstdio>
using namespace std;

const int MAX = 205;
char c[MAX];
int n, step = 0;
int sp;  // 当前空位（'-'）的起始位置

void print() {
    printf("step%2d:", step++);
    for (int i = 1; i <= 2 * n + 2; i++) {
        cout << c[i];
    }
    cout << endl;
}

// 移动 k 和 k+1 处的棋子到空位 sp 处
void move(int k) {
    for (int j = 0; j <= 1; j++) {
        c[sp + j] = c[k + j];
        c[k + j] = '-';
    }
    sp = k;
    print();
}

void mv(int n) {
    if (n == 4) { // 边界情况：n = 4 时固定进行5步移动
        move(4);
        move(8);
        move(2);
        move(7);
        move(1);
    } else {
        move(n);
        move(2 * n - 1);
        mv(n - 1); // 递归解决子问题
    }
}

int main() {
    if (!(cin >> n)) return 0;
    step = 0;
    sp = 2 * n + 1;
    
    for (int i = 1; i <= n; i++) c[i] = 'o';
    for (int i = n + 1; i <= 2 * n; i++) c[i] = '*';
    c[2 * n + 1] = '-';
    c[2 * n + 2] = '-';
    
    print();
    mv(n);
    return 0;
}
```

---

### 例 8. 小车问题

#### 问题描述
甲、乙两人同时从 A 地出发前往 B 地。出发时 A 地有一辆限载 1 人的小车。两人步行速度均为 $a$，车速为 $b$（$a < b$）。如何利用这辆小车，使得两人能以最短的时间**同时**到达 B 地？

#### 问题分析
最优策略为：甲先乘车至某处 $K$ 下车，然后步行前往 $B$；车立即调头去接已步行到 $C$ 处的乙，在 $D$ 处接到乙后乘车赶往 $B$。最终，甲和乙应当同时到达终点 $B$。
由于各段路程存在确定的比例关系，我们可以通过**二分法**来搜索甲下车的位置 $K$（设为变量 $c$）：
1.  若甲到达终点的时间 $t\_1$ 大于乙到达终点的时间 $t\_2$，说明车带甲走得太远了，应该调小 $c$ 的上界。
2.  若 $t\_1 < t\_2$，说明车应该多带甲走一段，调大 $c$ 的下界。
3.  通过二分逼近，直到 $t\_1$ 与 $t\_2$ 之间的差值满足精度要求。

#### 完整代码实现
```cpp
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;

const double ZERO = 1e-6;

int main() {
    double s, a, b;
    if (!(cin >> s >> a >> b)) return 0;
    
    double c0 = 0, c1 = s, c;
    double t1, t2, t3, t4;
    
    do {
        c = (c0 + c1) / 2;
        t3 = c / b;                      // 车送甲到 K 的时间
        t1 = t3 + (s - c) / a;           // 甲的总时间
        
        t4 = (c - t3 * a) / (a + b);     // 车回头与乙相遇所需的时间
        t2 = t3 + t4 + (s - (t3 + t4) * a) / b;  // 乙的总时间
        
        if (t1 < t2) {
            c1 = c; // 说明 c 偏大，应减小
        } else {
            c0 = c; // 说明 c 偏小，应增大
        }
    } while (abs(t1 - t2) >= ZERO);
    
    printf("%.10f\n", t1);
    return 0;
}
```

---

### 例 9. 麦森数

#### 问题描述
形如 $2^P - 1$ 且为素数的数称为麦森数。求 $2^P - 1$ 的十进制位数，以及其最后 500 位数字（不足 500 位在高位补 0）。其中 $1000 < P < 3100000$。

#### 问题分析
1.  **求位数**：一个正整数 $X$ 的十进制位数为 $\lfloor \log\_{10}(X) \rfloor + 1$。
    对于 $2^P - 1$，由于其末位绝不为 0，故其位数等同于 $2^P$ 的位数，即：
    
    $$\text{位数} = \lfloor P \times \log\_{10}(2) \rfloor + 1$$
    
2.  **求最后 500 位**：
    利用快速幂（二分法）的思想，计算 $2^P$ 时，采用高精度乘法，且每次相乘只保留最后 500 位，从而避免多余的高位运算。最后将最低位减 1 即可。

#### 完整代码实现
```cpp
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;

int out[505];   // 存放最后 500 位
int sta[1005];  // 辅助高精度计算的临时数组

// 二分法求 2 的 n 次方并保留最后 500 位
void solve(int n) {
    if (n == 0) return;
    
    solve(n / 2);
    
    // 自乘计算平方
    memset(sta, 0, sizeof(sta));
    for (int i = 1; i <= 500; i++) {
        for (int j = 1; j <= 500; j++) {
            if (i + j - 1 <= 500) {
                if (n % 2 == 0) {
                    sta[i + j - 1] += out[i] * out[j];
                } else {
                    sta[i + j - 1] += out[i] * out[j] * 2;
                }
            }
        }
    }
    
    // 统一处理进位并更新
    for (int i = 1; i <= 500; i++) {
        out[i] = sta[i] % 10;
        sta[i + 1] += sta[i] / 10;
    }
}

int main() {
    int P;
    if (!(cin >> P)) return 0;
    
    int digits = (int)(P * log10(2)) + 1;
    cout << digits << endl;

memset(out, 0, sizeof(out));
    out[1] = 1;    
    solve(P);
    out[1]--; // 计算 2^P - 1
    
    // 逆序输出最后 500 位，每行 50 位
    for (int i = 500; i >= 1; i--) {
        cout << out[i];
        if ((i - 1) % 50 == 0) cout << "\n";
    }
    return 0;
}
```

---

### 例 10. 大整数乘法（Karatsuba 算法）

#### 问题描述
计算两个 $n$ 位大整数 $X$ 和 $Y$ 的乘积。若使用传统高精度乘法，时间复杂度为 $O(n^2)$。当 $n$ 极大时，需要设计更高效的算法。

#### 问题分析
假设将 $n$ 位的 $X$ 和 $Y$ 均分为两部分：
*   $X = A \times 10^{n/2} + B$ （$A$ 为高位，$B$ 为低位）
*   $Y = C \times 10^{n/2} + D$ （$C$ 为高位，$D$ 为低位）

传统的乘法展开：

$$X \times Y = A \times C \times 10^n + (A \times D + B \times C) \times 10^{n/2} + B \times D$$

这需要进行 4 次大小为 $n/2$ 位的乘法。根据主定理，时间复杂度依然是 $O(n^2)$。

**Karatsuba 优化**引入了恒等式：

$$A \times D + B \times C = (A + B) \times (C + D) - A \times C - B \times D$$

我们定义三个中间变量：
*   $P\_1 = A \times C$
*   $P\_2 = B \times D$
*   $P\_3 = (A + B) \times (C + D)$

从而，中间项 $A \times D + B \times C$ 可表示为 $P\_3 - P\_1 - P\_2$。
这样，我们只需递归计算 3 次乘法（$P\_1, P\_2, P\_3$）。
新的递归关系式为：

$$T(n) = 3T(n/2) + O(n)$$

根据主定理，其时间复杂度优化为 $O(n^{\log\_2 3}) \approx O(n^{1.585})$。

#### 完整代码实现
```cpp
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

// 清除字符串前导零
string trim(string s) {
    int i = 0;
    while (i < s.length() - 1 && s[i] == '0') i++;
    return s.substr(i);
}

// 高精度加法
string add(string a, string b) {
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    
    string res;
    int carry = 0;
    int len = max(a.length(), b.length());
    
    for (int i = 0; i < len || carry; i++) {
        int sum = carry;
        if (i < a.length()) sum += a[i] - '0';
        if (i < b.length()) sum += b[i] - '0';
        res.push_back(sum % 10 + '0');
        carry = sum / 10;
    }
    
    reverse(res.begin(), res.end());
    return res;
}

// 高精度减法（调用前提：a >= b）
string sub(string a, string b) {
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    
    string res;
    int borrow = 0;
    
    for (int i = 0; i < a.length(); i++) {
        int diff = (a[i] - '0') - borrow;
        if (i < b.length()) diff -= (b[i] - '0');
        
        if (diff < 0) {
            diff += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }
        res.push_back(diff + '0');
    }
    
    while (res.length() > 1 && res.back() == '0') {
        res.pop_back();
    }
    
    reverse(res.begin(), res.end());
    return res;
}

// 在末尾补 0（等价于乘以 10^n）
string appendZeros(string s, int n) {
    return s + string(n, '0');
}

// Karatsuba 乘法递归函数
string karatsuba(string x, string y) {
    x = trim(x);
    y = trim(y);
    
    // 递归边界：若数位较少，直接计算
    if (x.length() <= 2 || y.length() <= 2) {
        long long a = stoll(x);
        long long b = stoll(y);
        return to_string(a * b);
    }
    
    // 对齐长度为偶数
    int n = max(x.length(), y.length());
    if (n % 2) n++;  
    
    x = string(n - x.length(), '0') + x;
    y = string(n - y.length(), '0') + y;
    
    int m = n / 2;
    
    // 划分为高低位
    string A = x.substr(0, m);
    string B = x.substr(m);
    string C = y.substr(0, m);
    string D = y.substr(m);
    
    // 递归计算3次乘积
    string AC = karatsuba(A, C);
    string BD = karatsuba(B, D);
    string ABCD = karatsuba(add(A, B), add(C, D));
    
    // 求解中间项 mid = ABCD - AC - BD
    string mid = sub(sub(ABCD, AC), BD);
    
    // 结果合并：AC * 10^(2m) + mid * 10^m + BD
    string res = add(
        add(appendZeros(AC, 2 * m), appendZeros(mid, m)),
        BD
    );
    
    return res;
}

int main() {
    string a, b;
    if (cin >> a >> b) {
        cout << karatsuba(a, b) << endl;
    }
    return 0;
}
```

---

## 四、 总结与设计指南

分治算法的特征与设计要点如下：

1.  **子问题性质**：
    *   **相同性**：分解出的子问题必须与原问题具有相同的结构，以便能够使用相同的程序（或同一函数）进行递归求解。
    *   **独立性**：各子问题之间应当是相互独立的，即不包含重叠的子问题。*（注：若子问题间存在大量重叠，通常应改用**动态规划**）*。
2.  **递归与递推的选择**：
    *   **递归实现**：逻辑最符合“自顶向下”的分治思考方式，易于编写和维护（如归并排序、棋盘覆盖）。
    *   **递推实现**：有时为了追求运行效率并避免因系统栈调用带来的额外开销（如防止栈溢出），我们可以采用“自底向上”的递推方式编写程序（如循环赛日程表、快速幂的迭代版）。

分治算法专题讲义

一、引导案例：找假币问题

为了理解分治算法的思想，我们先来看一个经典的找假币问题：

问题描述：袋子中装有 16 个硬币，其中有一个是伪造的。已知伪造的硬币比真硬币稍轻。现有一台天平（无砝码），可以通过比较两组硬币的重量来判断其轻重。如何找出这个假币？

方法一（逐个比较）：先称量硬币 1 和硬币 2。如果重量不等，轻的那枚就是假币；如果相等，再称量硬币 3 和硬币 4……以此类推。这种方法在最坏情况下需要比较 8 次才能找到假币。
方法二（二分法）：将 16 个硬币均分为两组（每组 8 个）进行称量。较轻的那组必含有假币。接着将该组再均分为两组（每组 4 个）进行称量……如此循环，只需 4 次便能确定假币。
方法三（三分法）：将 16 个硬币分成三组：A 组 5 个、B 组 5 个、C 组 6 个。首先称量 A 组和 B 组：
- 如果 A 和 B 重量相等，说明假币在 C 组（6 个）。接下来把 C 组分成 2 个、2 个、2 个三组继续称量。
- 如果 A 和 B 重量不等，假币就在较轻的那一组。通过这种方法，最多只需 3 次称量即可找出假币。

核心结论：将一个规模较大的问题，分解为若干个规模较小的同类子问题，然后逐个击破，这就是分治（Divide and Conquer）的核心思想。

二、分治算法基本概念

1. 定义与基本策略

分治法是将一个难以直接解决的大问题，分割成 $k$ 个规模较小的子问题。这些子问题相互独立，且与原问题结构相同（或类似）。我们递归地解决这些子问题，然后将子问题的解合并，从而得到原问题的解。

为了使算法保持平衡，通常采用平衡子问题的设计思想，即将大问题均匀地分解为 $k$ 个规模几乎相等的子问题（最常见的是 $k=2$，即二分法）。

2. 分治法的三步曲

在每一层递归上，分治法都包含以下三个核心步骤： 1. 分解（Divide）：将原问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。 2. 解决（Conquer）：若子问题规模较小且易于解决，则直接求解；否则，递归地求解各个子问题。 3. 合并（Combine）：将各个子问题的解合并为原问题的解。

三、经典应用解析与程序实现

例 1. 循环比赛日程表

问题描述

设有 $n = 2^m$ 名选手进行循环比赛。要求： 1. 每名选手要与其他 $n-1$ 名选手各赛一次。 2. 每名选手每天只能比赛一次。 3. 循环赛共进行 $n-1$ 天，且每天没有选手轮空。

问题分析

以 8 名选手为例，其日程表是一个具有对称性的 $8 \times 8$ 方阵：

$$ \begin{array}{cccc|cccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 2 & 1 & 4 & 3 & 6 & 5 & 8 & 7 \\ 3 & 4 & 1 & 2 & 7 & 8 & 5 & 6 \\ 4 & 3 & 2 & 1 & 8 & 7 & 6 & 5 \\ \hline 5 & 6 & 7 & 8 & 1 & 2 & 3 & 4 \\ 6 & 5 & 8 & 7 & 2 & 1 & 4 & 3 \\ 7 & 8 & 5 & 6 & 3 & 4 & 1 & 2 \\ 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 \end{array} $$

将方阵一分为四： * 左上角的 $4 \times 4$ 方阵是前 4 位选手的日程表。 * 右上角的 $4 \times 4$ 方阵是后 4 位选手的日程表，它在本质上与左上角相同，只需将左上角的所有元素加上 $4$ 即可。 * 左下角和右下角则表示两组选手之间的交叉比赛情况。利用对称性： * 左下角方阵可以通过复制右上角方阵得到。 * 右下角方阵可以通过复制左上角方阵得到。

由此，我们可以通过递归或迭代，将大方阵分解为小方阵来构造。

完整代码实现

递归写法

#include <iostream>
using namespace std;

const int MAXN = 65;
int table[MAXN][MAXN];

// 填充矩形区域 [a1..a2] × [b1..b2]，填入数值范围 [x..y]
void make_table(int a1, int b1, int a2, int b2, int x, int y) {
    if (x == y) {
        table[a1][b1] = x;
    } else {
        // 计算区域的中点坐标
        int a3 = (a1 + a2) / 2;
        int b3 = (b1 + b2) / 2;
        // 计算数值的中点
        int xy = (x + y) / 2;

        make_table(a1, b1, a3, b3, x, xy);                 // 左上角
        make_table(a1, b3 + 1, a3, b2, xy + 1, y);         // 右上角
        make_table(a3 + 1, b1, a2, b3, xy + 1, y);         // 左下角
        make_table(a3 + 1, b3 + 1, a2, b2, x, xy);         // 右下角
    }
}

int main() {
    int m;
    if (!(cin >> m)) return 0;
    int n = 1 << m;  // n = 2^m

    make_table(1, 1, n, n, 1, n); // 填充整个 n×n 区域，数值范围 [1, n]

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << table[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

迭代写法

#include <iostream>
using namespace std;

const int MAXN = 1025;
int a[MAXN][MAXN];

int main() {
    int m;
    if (!(cin >> m)) return 0;

    int n = 1 << m;  // n = 2^m
    a[1][1] = 1;

    // 从 1x1 方阵开始，逐步向外扩展
    for (int size = 1; size < n; size *= 2) {
        // 构造右上角方阵 = 左上角 + size
        for (int i = 1; i <= size; i++) {
            for (int j = 1; j <= size; j++) {
                a[i][j + size] = a[i][j] + size;
            }
        }
        // 构造左下角方阵 = 右上角方阵
        for (int i = 1; i <= size; i++) {
            for (int j = 1; j <= size; j++) {
                a[i + size][j] = a[i][j + size];
            }
        }
        // 构造右下角方阵 = 左上角方阵
        for (int i = 1; i <= size; i++) {
            for (int j = 1; j <= size; j++) {
                a[i + size][j + size] = a[i][j];
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

例 2. 求方程的根

问题描述

输入整数 $m, n, p, a, b$（其中 $a < b$，$m, n, p \ge 1$），求方程 $f(x) = m^x + n^x - p^x = 0$ 在区间 $[a, b]$ 内的根。若有根则输出，精确到 $10^{-11}$；若无根则输出 NO。

问题分析

由于 $m, n, p \ge 1$，函数 $f(x) = m^x + n^x - p^x$ 在给定区间内通常表现出单调性。若满足 $f(a) \times f(b) \le 0$，根据零点存在定理，区间 $[a, b]$ 内必存在解。我们可以通过二分法来逼近这个解： 1. 令 $x = (a + b) / 2$ 为区间中点。 2. 若 $f(a) \times f(x) < 0$，说明根在 $[a, x]$ 区间，令 $b = x$。 3. 否则，根在 $[x, b]$ 区间，令 $a = x$。 4. 当区间长度 $|b - a|$ 小于给定的精度阈值时，停止迭代。

注意：在计算 $y^x$ 时，直接使用 pow(y, x) 或通过换底公式 exp(x * log(y)) 计算均可。

完整代码实现

#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;

const double ZERO = 1e-11;  // 精度控制

int m, n, p;
double a, b;

// 计算 f(x) = m^x + n^x - p^x
double f(double x) {
    return exp(x * log(m)) + exp(x * log(n)) - exp(x * log(p));
}

int main() {
    if (!(cin >> m >> n >> p >> a >> b)) return 0;

    // 判断区间内是否有解
    if (f(a) * f(b) > 0) {
        cout << "NO" << endl;
        return 0;
    }

    double x, fa, fx;
    do {
        x = (a + b) / 2;
        fa = f(a);
        fx = f(x);

        if (fa * fx < 0) {
            b = x;      // 解在 [a, x] 内
        } else {
            a = x;      // 解在 [x, b] 内
        }
    } while (abs(b - a) >= ZERO);

    // 输出结果，使用科学计数法
    printf("%.10E\n", (a + b) / 2);
    printf("%.10E\n", f((a + b) / 2));

    return 0;
}

例 3. 取余运算（快速幂）

问题描述

输入三个长整型数 $b, p, k$，求 $b^p \bmod k$ 的值。

问题分析

当 $p$ 很大时，直接计算 $b^p$ 会导致数据溢出且时间复杂度过高。我们可以利用同余定理：

$$(A \times B) \bmod K = ((A \bmod K) \times (B \bmod K)) \bmod K$$

为了降低复杂度，我们可以将指数 $p$ 进行二分分解： * 若 $p$ 为偶数：$b^p = (b^{p/2})^2$ * 若 $p$ 为奇数：$b^p = (b^{p/2})^2 \times b$

这样可以将计算 $b^p$ 的时间复杂度从 $O(p)$ 降到 $O(\log p)$。

完整代码实现（递归与迭代）

递归写法

#include <iostream>
using namespace std;

// 递归快速幂：计算 a^b % n
long long power_mod(long long a, long long b, long long n) {
    if (b == 0) return 1 % n;    

    long long ans = power_mod(a, b / 2, n);     // 递归计算一半
    ans = (ans * ans) % n;                      // 平方
    if (b & 1) ans = (ans * (a % n)) % n;       // 奇数时额外乘以底数

    return ans;
}

int main() {
    long long b, p, k;
    if (cin >> b >> p >> k) {
        long long result = power_mod(b, p, k);
        cout << b << "^" << p << " mod " << k << " = " << result << endl;
    }
    return 0;
}

迭代写法

long long power_mod(long long a, long long b, long long n) {
    long long res = 1 % n;          
    long long base = a % n;     

    while (b > 0) {
        if (b & 1) {               // 如果当前二进制位是 1
            res = (res * base) % n;  
        }
        base = (base * base) % n;    // 底数平方
        b >>= 1;                   // 指数右移一位（相当于除以 2）
    }

    return res;
}

例 4. 快速排序

问题描述

给定一个长度为 $n$ 的数组，将其按升序排序。

问题分析

快速排序（Quick Sort）采用分治思想，其核心在于划分（Partition）： 1. 分解：选择一个基准值（pivot）。通过双指针向中间扫描，将数组划分为两部分，使得左侧所有元素均小于等于基准，右侧所有元素均大于等于基准。 2. 解决：递归地对左、右两个子数组进行快速排序。 3. 合并：因为在分解的过程中元素已经就位，所以合并步骤不需要进行任何操作。

完整代码实现

#include <iostream>
#include <algorithm>
using namespace std;

void qsort(int* arr, int left, int right) { 
    int mid = (left + right) / 2;
    int flag = arr[mid]; // 基准值
    int i = left, j = right;

    while (i <= j) {
        // 注意：不取等号。如果取等号，当 flag 是最大值时，i 会溢出越界。
        while (arr[i] < flag) i++;        
        while (arr[j] > flag) j--;        
        if (i <= j) {
            swap(arr[i], arr[j]);
            i++;
            j--;
        }
    }

    if (left < j) qsort(arr, left, j);      // 递归处理左半部分
    if (right > i) qsort(arr, i, right);    // 递归处理右半部分
}

int main() {
    int n;
    if (!(cin >> n)) return 0;
    int* a = new int[n];
    for (int i = 0; i < n; i++) cin >> a[i];    

    qsort(a, 0, n - 1);

    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;

    delete[] a;
    return 0;
}

例 5. 归并排序

问题描述

给定一个长度为 $n$ 的数组，将其按升序排序。

问题分析

归并排序（Merge Sort）是标准的分治算法： 1. 分解：将数组从中间切成两半。 2. 解决：递归地对左半部分和右半部分进行归并排序。 3. 合并：使用双指针将两个已经排好序的子序列合并为一个完整的有序序列。

完整代码实现

#include <iostream>
using namespace std;

const int N = 100005;
int a[N], tmp[N];

// 合并两个有序区间 [l, mid] 和 [mid+1, r]
void merge(int l, int mid, int r) {
    int i = l;          // 左半部分指针
    int j = mid + 1;    // 右半部分指针
    int k = l;          // 临时数组指针

    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            tmp[k++] = a[i++];
        } else {
            tmp[k++] = a[j++];
        }
    }

    while (i <= mid) tmp[k++] = a[i++];    
    while (j <= r) tmp[k++] = a[j++];    

    // 写回原数组
    for (int p = l; p <= r; p++) {
        a[p] = tmp[p];
    }
}

void mergeSort(int l, int r) {
    if (l >= r) return;  

    int mid = (l + r) / 2;
    mergeSort(l, mid);      
    mergeSort(mid + 1, r);  
    merge(l, mid, r);       
}

int main() {
    int n;
    if (!(cin >> n)) return 0;
    for (int i = 1; i <= n; i++) cin >> a[i];    

    mergeSort(1, n);

    for (int i = 1; i <= n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}

例 6. 地毯填补问题（棋盘覆盖问题）

问题描述

在一个 $2^k \times 2^k$ 的正方形方格迷宫中，除一个特定的方格（“公主”站立的方格）不能覆盖外，其余方格都需要用 L 型地毯（由三个小方格组成，共四种旋转形态）覆盖。请给出铺满地毯的方案。

问题分析

采用分治策略，将 $2^k \times 2^k$ 的大棋盘划分为四个 $2^{k-1} \times 2^{k-1}$ 的子棋盘： 1. 确定“特殊方格”（公主）落在四个子棋盘中的哪一个。 2. 在中心连接处，放置一个 L 型地毯，使其拐角覆盖除含有公主外的另外三个子棋盘的角格。 3. 通过这种放置方式，另外三个原本没有特殊方格的子棋盘在角格被覆盖后，也转化为了含有“特殊方格”的子问题。 4. 递归处理这四个子棋盘，直至规模缩减为 $1 \times 1$。

完整代码实现

#include <iostream>
#include <cstdio>
using namespace std;

// (row, col)：当前子棋盘左上角坐标
// (px, py)：公主（特殊方格）坐标
// n：当前子棋盘大小的对数，即 2^n × 2^n
void dfs(int row, int col, int px, int py, int n) {
    if (n == 0) return;

    int k = 1 << (n - 1);  // 子棋盘大小的一半

    // 情况1：公主在左上角
    if (px <= row + k - 1 && py <= col + k - 1) {
        printf("%d %d %d\n", row + k, col + k, 3); // 放置3号毯子，拐角在右下
        dfs(row, col, px, py, n - 1);
        dfs(row, col + k, row + k - 1, col + k, n - 1);
        dfs(row + k, col, row + k, col + k - 1, n - 1);
        dfs(row + k, col + k, row + k, col + k, n - 1);
    }
    // 情况2：公主在右上角
    else if (px <= row + k - 1 && py > col + k - 1) {
        printf("%d %d %d\n", row + k, col + k - 1, 1); // 放置1号毯子
        dfs(row, col, row + k - 1, col + k - 1, n - 1);
        dfs(row, col + k, px, py, n - 1);
        dfs(row + k, col, row + k, col + k - 1, n - 1);
        dfs(row + k, col + k, row + k, col + k, n - 1);
    }
    // 情况3：公主在左下角
    else if (px > row + k - 1 && py <= col + k - 1) {
        printf("%d %d %d\n", row + k - 1, col + k, 2); // 放置2号毯子
        dfs(row, col, row + k - 1, col + k - 1, n - 1);
        dfs(row, col + k, row + k - 1, col + k, n - 1);
        dfs(row + k, col, px, py, n - 1);
        dfs(row + k, col + k, row + k, col + k, n - 1);
    }
    // 情况4：公主在右下角
    else {
        printf("%d %d %d\n", row + k - 1, col + k - 1, 4); // 放置4号毯子
        dfs(row, col, row + k - 1, col + k - 1, n - 1);
        dfs(row, col + k, row + k - 1, col + k, n - 1);
        dfs(row + k, col, row + k, col + k - 1, n - 1);
        dfs(row + k, col + k, px, py, n - 1);
    }
}

int main() {    
    int k, x, y;
    if (cin >> k >> x >> y) {
        dfs(1, 1, x, y, k);
    }
    return 0;
}

例 7. 黑白棋子的移动

问题描述

有 $2n$ 个棋子（$n \ge 4$）排成一排，开始时左边全部为白子（o），右边全部为黑子（*）。每次必须同时移动相邻的两个棋子到空位（-）上，不能改变两者的相对左右顺序。求如何通过最少的步数，将棋子移动为黑白相间（o*o*...o*）的状态。

问题分析

通过手工推导可以发现，对于任意规模 $n$ 的问题，我们都可以通过两步特定的移动，将其转化为规模为 $n-1$ 的子问题： 1. 将中间相邻的白子和黑子移到末尾的空位。 2. 将右侧倒数第二、三个棋子移动到腾出的中间位置。 3. 如此，问题规模缩减为 $n-1$。 4. 当规模缩减到边界情况 $n=4$ 时，套用固定的 5 步基本移动方案。

完整代码实现

#include <iostream>
#include <cstdio>
using namespace std;

const int MAX = 205;
char c[MAX];
int n, step = 0;
int sp;  // 当前空位（'-'）的起始位置

void print() {
    printf("step%2d:", step++);
    for (int i = 1; i <= 2 * n + 2; i++) {
        cout << c[i];
    }
    cout << endl;
}

// 移动 k 和 k+1 处的棋子到空位 sp 处
void move(int k) {
    for (int j = 0; j <= 1; j++) {
        c[sp + j] = c[k + j];
        c[k + j] = '-';
    }
    sp = k;
    print();
}

void mv(int n) {
    if (n == 4) { // 边界情况：n = 4 时固定进行5步移动
        move(4);
        move(8);
        move(2);
        move(7);
        move(1);
    } else {
        move(n);
        move(2 * n - 1);
        mv(n - 1); // 递归解决子问题
    }
}

int main() {
    if (!(cin >> n)) return 0;
    step = 0;
    sp = 2 * n + 1;

    for (int i = 1; i <= n; i++) c[i] = 'o';
    for (int i = n + 1; i <= 2 * n; i++) c[i] = '*';
    c[2 * n + 1] = '-';
    c[2 * n + 2] = '-';

    print();
    mv(n);
    return 0;
}

例 8. 小车问题

问题描述

甲、乙两人同时从 A 地出发前往 B 地。出发时 A 地有一辆限载 1 人的小车。两人步行速度均为 $a$，车速为 $b$（$a < b$）。如何利用这辆小车，使得两人能以最短的时间同时到达 B 地？

问题分析

最优策略为：甲先乘车至某处 $K$ 下车，然后步行前往 $B$；车立即调头去接已步行到 $C$ 处的乙，在 $D$ 处接到乙后乘车赶往 $B$。最终，甲和乙应当同时到达终点 $B$。由于各段路程存在确定的比例关系，我们可以通过二分法来搜索甲下车的位置 $K$（设为变量 $c$）： 1. 若甲到达终点的时间 $t_1$ 大于乙到达终点的时间 $t_2$，说明车带甲走得太远了，应该调小 $c$ 的上界。 2. 若 $t_1 < t_2$，说明车应该多带甲走一段，调大 $c$ 的下界。 3. 通过二分逼近，直到 $t_1$ 与 $t_2$ 之间的差值满足精度要求。

完整代码实现

#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;

const double ZERO = 1e-6;

int main() {
    double s, a, b;
    if (!(cin >> s >> a >> b)) return 0;

    double c0 = 0, c1 = s, c;
    double t1, t2, t3, t4;

    do {
        c = (c0 + c1) / 2;
        t3 = c / b;                      // 车送甲到 K 的时间
        t1 = t3 + (s - c) / a;           // 甲的总时间

        t4 = (c - t3 * a) / (a + b);     // 车回头与乙相遇所需的时间
        t2 = t3 + t4 + (s - (t3 + t4) * a) / b;  // 乙的总时间

        if (t1 < t2) {
            c1 = c; // 说明 c 偏大，应减小
        } else {
            c0 = c; // 说明 c 偏小，应增大
        }
    } while (abs(t1 - t2) >= ZERO);

    printf("%.10f\n", t1);
    return 0;
}

例 9. 麦森数

问题描述

形如 $2^P - 1$ 且为素数的数称为麦森数。求 $2^P - 1$ 的十进制位数，以及其最后 500 位数字（不足 500 位在高位补 0）。其中 $1000 < P < 3100000$。

问题分析

求位数：一个正整数 $X$ 的十进制位数为 $\lfloor \log_{10}(X) \rfloor + 1$。对于 $2^P - 1$，由于其末位绝不为 0，故其位数等同于 $2^P$ 的位数，即：

$$\text{位数} = \lfloor P \times \log_{10}(2) \rfloor + 1$$
求最后 500 位：利用快速幂（二分法）的思想，计算 $2^P$ 时，采用高精度乘法，且每次相乘只保留最后 500 位，从而避免多余的高位运算。最后将最低位减 1 即可。

完整代码实现

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;

int out[505];   // 存放最后 500 位
int sta[1005];  // 辅助高精度计算的临时数组

// 二分法求 2 的 n 次方并保留最后 500 位
void solve(int n) {
    if (n == 0) return;

    solve(n / 2);

    // 自乘计算平方
    memset(sta, 0, sizeof(sta));
    for (int i = 1; i <= 500; i++) {
        for (int j = 1; j <= 500; j++) {
            if (i + j - 1 <= 500) {
                if (n % 2 == 0) {
                    sta[i + j - 1] += out[i] * out[j];
                } else {
                    sta[i + j - 1] += out[i] * out[j] * 2;
                }
            }
        }
    }

    // 统一处理进位并更新
    for (int i = 1; i <= 500; i++) {
        out[i] = sta[i] % 10;
        sta[i + 1] += sta[i] / 10;
    }
}

int main() {
    int P;
    if (!(cin >> P)) return 0;

    int digits = (int)(P * log10(2)) + 1;
    cout << digits << endl;

    memset(out, 0, sizeof(out));
    out[1] = 1;    
    solve(P);
    out[1]--; // 计算 2^P - 1

    // 逆序输出最后 500 位，每行 50 位
    for (int i = 500; i >= 1; i--) {
        cout << out[i];
        if ((i - 1) % 50 == 0) cout << "\n";
    }
    return 0;
}

例 10. 大整数乘法（Karatsuba 算法）

问题描述

计算两个 $n$ 位大整数 $X$ 和 $Y$ 的乘积。若使用传统高精度乘法，时间复杂度为 $O(n^2)$。当 $n$ 极大时，需要设计更高效的算法。

问题分析

假设将 $n$ 位的 $X$ 和 $Y$ 均分为两部分： * $X = A \times 10^{n/2} + B$ （$A$ 为高位，$B$ 为低位） * $Y = C \times 10^{n/2} + D$ （$C$ 为高位，$D$ 为低位）

传统的乘法展开：

$$X \times Y = A \times C \times 10^n + (A \times D + B \times C) \times 10^{n/2} + B \times D$$

这需要进行 4 次大小为 $n/2$ 位的乘法。根据主定理，时间复杂度依然是 $O(n^2)$。

Karatsuba 优化引入了恒等式：

$$A \times D + B \times C = (A + B) \times (C + D) - A \times C - B \times D$$

我们定义三个中间变量： * $P_1 = A \times C$ * $P_2 = B \times D$ * $P_3 = (A + B) \times (C + D)$

从而，中间项 $A \times D + B \times C$ 可表示为 $P_3 - P_1 - P_2$。这样，我们只需递归计算 3 次乘法（$P_1, P_2, P_3$）。新的递归关系式为：

$$T(n) = 3T(n/2) + O(n)$$

根据主定理，其时间复杂度优化为 $O(n^{\log_2 3}) \approx O(n^{1.585})$。

完整代码实现

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

// 清除字符串前导零
string trim(string s) {
    int i = 0;
    while (i < s.length() - 1 && s[i] == '0') i++;
    return s.substr(i);
}

// 高精度加法
string add(string a, string b) {
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());

    string res;
    int carry = 0;
    int len = max(a.length(), b.length());

    for (int i = 0; i < len || carry; i++) {
        int sum = carry;
        if (i < a.length()) sum += a[i] - '0';
        if (i < b.length()) sum += b[i] - '0';
        res.push_back(sum % 10 + '0');
        carry = sum / 10;
    }

    reverse(res.begin(), res.end());
    return res;
}

// 高精度减法（调用前提：a >= b）
string sub(string a, string b) {
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());

    string res;
    int borrow = 0;

    for (int i = 0; i < a.length(); i++) {
        int diff = (a[i] - '0') - borrow;
        if (i < b.length()) diff -= (b[i] - '0');

        if (diff < 0) {
            diff += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }
        res.push_back(diff + '0');
    }

    while (res.length() > 1 && res.back() == '0') {
        res.pop_back();
    }

    reverse(res.begin(), res.end());
    return res;
}

// 在末尾补 0（等价于乘以 10^n）
string appendZeros(string s, int n) {
    return s + string(n, '0');
}

// Karatsuba 乘法递归函数
string karatsuba(string x, string y) {
    x = trim(x);
    y = trim(y);

    // 递归边界：若数位较少，直接计算
    if (x.length() <= 2 || y.length() <= 2) {
        long long a = stoll(x);
        long long b = stoll(y);
        return to_string(a * b);
    }

    // 对齐长度为偶数
    int n = max(x.length(), y.length());
    if (n % 2) n++;  

    x = string(n - x.length(), '0') + x;
    y = string(n - y.length(), '0') + y;

    int m = n / 2;

    // 划分为高低位
    string A = x.substr(0, m);
    string B = x.substr(m);
    string C = y.substr(0, m);
    string D = y.substr(m);

    // 递归计算3次乘积
    string AC = karatsuba(A, C);
    string BD = karatsuba(B, D);
    string ABCD = karatsuba(add(A, B), add(C, D));

    // 求解中间项 mid = ABCD - AC - BD
    string mid = sub(sub(ABCD, AC), BD);

    // 结果合并：AC * 10^(2m) + mid * 10^m + BD
    string res = add(
        add(appendZeros(AC, 2 * m), appendZeros(mid, m)),
        BD
    );

    return res;
}

int main() {
    string a, b;
    if (cin >> a >> b) {
        cout << karatsuba(a, b) << endl;
    }
    return 0;
}

四、总结与设计指南

分治算法的特征与设计要点如下：

子问题性质：
- 相同性：分解出的子问题必须与原问题具有相同的结构，以便能够使用相同的程序（或同一函数）进行递归求解。
- 独立性：各子问题之间应当是相互独立的，即不包含重叠的子问题。（注：若子问题间存在大量重叠，通常应改用动态规划）。
递归与递推的选择：
- 递归实现：逻辑最符合“自顶向下”的分治思考方式，易于编写和维护（如归并排序、棋盘覆盖）。
- 递推实现：有时为了追求运行效率并避免因系统栈调用带来的额外开销（如防止栈溢出），我们可以采用“自底向上”的递推方式编写程序（如循环赛日程表、快速幂的迭代版）。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com