分治法求大整数乘法，给出c语言代码实现

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

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

// 将大整数字符串转换为整数数组，存储每一位的数字
void str2num(char *str, int *num, int len) {
    int i;
    for (i = 0; i < len; i++) {
        num[i] = str[len - i - 1] - '0';
    }
}

// 将整数数组转换为大整数字符串
void num2str(int *num, int len, char *str) {
    int i;
    for (i = len - 1; i >= 0; i--) {
        str[len - i - 1] = num[i] + '0';
    }
    str[len] = '\0';
}

// 大整数加法
void add(int *a, int *b, int *c, int len) {
    int i;
    int carry = 0;
    for (i = 0; i < len; i++) {
        c[i] = a[i] + b[i] + carry;
        if (c[i] >= 10) {
            c[i] -= 10;
            carry = 1;
        } else {
            carry = 0;
        }
    }
    if (carry == 1) {
        c[len] = 1;
    }
}

// 大整数减法
void sub(int *a, int *b, int *c, int len) {
    int i;
    int borrow = 0;
    for (i = 0; i < len; i++) {
        c[i] = a[i] - b[i] - borrow;
        if (c[i] < 0) {
            c[i] += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }
    }
}

// 大整数乘法，采用分治法
void multiply(int *a, int *b, int *c, int len) {
    if (len == 1) {
        c[0] = a[0] * b[0];
        return;
    }
    int i;
    int *a1, *a2, *b1, *b2, *c1, *c2, *c3;
    int len1 = len / 2;
    int len2 = len - len1;
    a1 = (int*) malloc(sizeof(int) * len1);
    a2 = (int*) malloc(sizeof(int) * len2);
    b1 = (int*) malloc(sizeof(int) * len1);
    b2 = (int*) malloc(sizeof(int) * len2);
    c1 = (int*) malloc(sizeof(int) * (len1 + len2));
    c2 = (int*) malloc(sizeof(int) * (len1 + len2));
    c3 = (int*) malloc(sizeof(int) * (len1 + len2));
    memset(c1, 0, sizeof(int) * (len1 + len2));
    memset(c2, 0, sizeof(int) * (len1 + len2));
    memset(c3, 0, sizeof(int) * (len1 + len2));
    // 将a、b分为两部分
    for (i = 0; i < len1; i++) {
        a1[i] = a[i];
        b1[i] = b[i];
    }
    for (i = 0; i < len2; i++) {
        a2[i] = a[i + len1];
        b2[i] = b[i + len1];
    }
    // 递归求解c1 = a1 * b1
    multiply(a1, b1, c1, len1);
    // 递归求解c3 = a2 * b2
    multiply(a2, b2, c3, len2);
    // 递归求解c2 = (a1 + a2) * (b1 + b2) - c1 - c3
    int *tmp1, *tmp2;
    tmp1 = (int*) malloc(sizeof(int) * len1 * 2);
    tmp2 = (int*) malloc(sizeof(int) * len2 * 2);
    memset(tmp1, 0, sizeof(int) * len1 * 2);
    memset(tmp2, 0, sizeof(int) * len2 * 2);
    add(a1, a2, tmp1, len1);
    add(b1, b2, tmp2, len1);
    multiply(tmp1, tmp2, c2, len1 * 2);
    sub(c2, c1, tmp1, len1 * 2);
    sub(tmp1, c3, c2, len1 * 2);
    // 合并结果
    for (i = 0; i < len1 + len2; i++) {
        c[i] += c1[i];
        c[i + len1] += c3[i];
        c[i + len1 / 2] += c2[i];
    }
    free(a1);
    free(a2);
    free(b1);
    free(b2);
    free(c1);
    free(c2);
    free(c3);
    free(tmp1);
    free(tmp2);
}

int main() {
    char str1[1000], str2[1000];
    int num1[1000], num2[1000], result[2000];
    memset(num1, 0, sizeof(num1));
    memset(num2, 0, sizeof(num2));
    memset(result, 0, sizeof(result));
    scanf("%s %s", str1, str2);
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    str2num(str1, num1, len1);
    str2num(str2, num2, len2);
    multiply(num1, num2, result, len1 + len2);
    char str[2001];
    num2str(result, len1 + len2, str);
    printf("%s\n", str);
    return 0;
}

在以上代码中，`str2num`函数将大整数字符串转换为整数数组，`num2str`函数将整数数组转换为大整数字符串；`add`函数实现大整数加法，`sub`函数实现大整数减法；`multiply`函数使用分治法实现大整数乘法，递归求解三个子问题，然后将其合并得到结果。在合并过程中，需要将`c1`和`c3`分别放在结果数组的前面和后面，将`c2`放在结果数组的中间。最后，将结果数组转换为大整数字符串输出。