c - 查找 2 个大号(每个 10000 位)的乘积的程序

Question

我需要一个高效的算法来计算 2 个大数(每个数最多 10000 位)相乘的结果。我已经写了一个代码，但它给出了超过时间限制的判断。我已经使用字符串扫描了数字，然后使用基本的乘法方法将结果存储在一个整数数组中:

#include <stdio.h>

int main() {
    int n, i, j, k, c, m, r, x, t, h, y;

    scanf("%d", &n);  // no of test cases
    for (i = 0; i < n; i++) {
        char A[10002], B[10002];
        int c1 = 0, c2 = 0, l;

        scanf("%s %s", A, B); //scanning the no.s
        for (j = 0; A[j] != '\0'; j++)
            c1++;
        for (j = 0; B[j] != '\0'; j++)
            c2++;
        l = 29999;

        int a[30002] = { 0 };
        for (j = c2 - 1; j >= 0; j--) {
            c = 0;
            x = l - 1;

            for (k = c1 - 1; k >= 0; k--) {
                h = (int)B[j] - 48;
                y = (int)A[k] - 48;
                r = (h * y) + c;  //multiply the last digit of B with all the digits of A.
                m = r % 10;
                r = r / 10; c = r;  //c is the carry 
                a[x] = m + a[x];
                if (a[x] > 9) {
                    a[x] = a[x] % 10;
                    a[x - 1] = a[x - 1] + 1; //adding 1 to previous posn of result in case of overflow.since only maximum 1 can be the 1st digit.
                }
                x--;
            }
            l--;
            a[x] = a[x] + c;
        }

        int flag = 0;
        for (k = 0; k <= 29998; k++) { 
            if (a[k] != 0) {
                printf("%d", a[k]);
                flag = 1;
            } else if (a[k] == 0 && flag == 1)
                printf("0");
        }
        if (flag == 0)
            printf("0");
        printf("\n");
    }
    return 0;
}

Answer 1

不要逐位操纵数字!如果你只是将它们分成每组 9 位数字，而不是 10000x10000，你将把它减少到 1111x1111，这应该快大约 80 倍。 (这假设您的平台有 32 位整数。)