程序找到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位整数.)