用分治法写一个大数相乘的C语言代码

以下是使用分治法实现大数相乘的C语言代码：

#include <stdio.h>
#include <string.h>

#define MAXN 10010

void multiply(char *a, char *b, char *res, int len_a, int len_b) {
    if (len_a == 1 && len_b == 1) {
        int num_a = a[0] - '0';
        int num_b = b[0] - '0';
        int num_res = num_a * num_b;
        res[0] = num_res % 10 + '0';
        res[1] = '\0';
        if (num_res >= 10) {
            res[1] = num_res / 10 + '0';
            res[2] = '\0';
        }
        return;
    }

    int mid_a = len_a / 2;
    int mid_b = len_b / 2;
    int len = len_a + len_b;

    char a1[mid_a + 1], a2[len_a - mid_a + 1];
    char b1[mid_b + 1], b2[len_b - mid_b + 1];
    char res1[mid_a + mid_b + 3], res2[mid_a + mid_b + 3], res3[mid_a + mid_b + 3];
    memset(a1, 0, sizeof(a1));
    memset(a2, 0, sizeof(a2));
    memset(b1, 0, sizeof(b1));
    memset(b2, 0, sizeof(b2));
    memset(res1, 0, sizeof(res1));
    memset(res2, 0, sizeof(res2));
    memset(res3, 0, sizeof(res3));

    for (int i = 0; i < mid_a; i++) {
        a1[i] = a[i];
    }
    a1[mid_a] = '\0';
    for (int i = mid_a; i < len_a; i++) {
        a2[i - mid_a] = a[i];
    }
    a2[len_a - mid_a] = '\0';
    for (int i = 0; i < mid_b; i++) {
        b1[i] = b[i];
    }
    b1[mid_b] = '\0';
    for (int i = mid_b; i < len_b; i++) {
        b2[i - mid_b] = b[i];
    }
    b2[len_b - mid_b] = '\0';

    multiply(a1, b1, res1, mid_a, mid_b);
    multiply(a2, b2, res2, len_a - mid_a, len_b - mid_b);
    multiply(a1, b2, res3, mid_a, len_b - mid_b);

    for (int i = 0; i < len; i++) {
        res[i] = '0';
    }
    res[len] = '\0';

    for (int i = 0; i < mid_a + mid_b + 2; i++) {
        res[i] += res1[i] - '0';
        res[i + mid_a + mid_b + 1] -= res1[i] - '0';
    }
    for (int i = 0; i < len_a - mid_a + len_b - mid_b + 1; i++) {
        res[i + mid_a] += res2[i] - '0';
        res[i + mid_a + mid_b + 1] -= res2[i] - '0';
    }
    for (int i = 0; i < mid_a + len_b - mid_b + 1; i++) {
        res[i + mid_a] += res3[i] - '0';
        res[i + mid_a + mid_b + 1] -= res3[i] - '0';
    }

    for (int i = len - 1; i > 0; i--) {
        if (res[i] < '0') {
            res[i] += 10;
            res[i - 1]--;
        }
        if (res[i] > '9') {
            res[i] -= 10;
            res[i - 1]++;
        }
    }

    while (res[0] == '0' && res[1] != '\0') {
        for (int i = 0; i < len; i++) {
            res[i] = res[i + 1];
        }
    }
}

int main() {
    char a[MAXN], b[MAXN], res[MAXN * 2];
    scanf("%s%s", a, b);
    int len_a = strlen(a);
    int len_b = strlen(b);
    multiply(a, b, res, len_a, len_b);
    printf("%s\n", res);
    return 0;
}

在该代码中，`multiply()`函数用于实现大数相乘的分治计算。首先判断两个数的位数是否都为1，如果是，则直接相乘并返回。否则，将两个数分别分成左右两部分，分别递归调用`multiply()`函数。然后将三部分的乘积进行组合，最终得到结果。

在组合三部分乘积的过程中，需要使用一个数组`res`来存储结果。首先将`res`数组初始化为全0，然后分别将三部分的乘积加入到`res`数组中。具体地，对于第一部分的乘积，将其加到`res`数组的前一半；对于第二部分的乘积，将其加到`res`数组的后一半；对于第三部分的乘积，将其加到`res`数组的中间。最后将`res`数组中的数字进行进位和消位操作，得到最终结果。

该代码的时间复杂度为$O(n^{\log_2 3})$，其中$n$为两个数中位数较大的那个数的位数。