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 位整数。）

Answer 2

检查这一点（前提是您将两个数字输入为整数而不是字符串）！

#include<stdio.h>
int main()
{
    int n,m,j,temp,i,c;
    int a[2000000];
    a[0]=1;j=0;
    printf("Enter the first number: ");
    scanf("%d",&m);
    printf("Enter the second number: ");
    scanf("%d",&n);
    for(i=0;i<=j;i++)
    {
        temp=(a[i]*m)+temp;
        a[i]=temp%10;
        temp=temp/10;
    }
    while(temp>0)
    {
        a[++j]=temp%10;
        temp=temp/10;
    }
    for(i=0;i<=j;i++)
    {
        temp=(a[i]*n)+temp;
        a[i]=temp%10;
        temp=temp/10;
    }
    while(temp>0)
    {
        a[++j]=temp%10;
        temp=temp/10;
    }
    for(i=j;i>=0;i--)
        printf("%d",a[i]);
    return 0;
}

Answer 3

这是一个结合了 2 种有效技术的解决方案：

• 它一次处理 6 位数字组，而不是单个数字。
• 它在不检查溢出的情况下对中间产品求和，节省了大量的测试和除法1000000。

这是代码：

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

#define NDIGITS 6

int main() {
    char A[10002], B[10002];
    int aa[10000 / NDIGITS + 1];
    int bb[10000 / NDIGITS + 1];
    int cc[10000 / NDIGITS + 1 + 10000 / NDIGITS + 1];
    int n, na, nb, nc, i, j, c;

    if (scanf("%d", &n) != 1)  // no of test cases
        return 1;

    static int const m10[10] = {
        1, 10, 100, 1000, 10000, 100000, 1000000,
        10000000, 100000000, 1000000000 };

    while (n-- > 0 && scanf("%10000s %10000s", A, B) == 2) {
        for (na = 0, c = j = 0, i = strlen(A); i-- > 0;) {
            c += (A[i] - '0') * m10[j];
            if (++j == NDIGITS || i == 0) {
                aa[na++] = c;
                c = j = 0;
            }
        }
        for (nb = 0, c = j = 0, i = strlen(B); i-- > 0;) {
            c += (B[i] - '0') * m10[j];
            if (++j == NDIGITS || i == 0) {
                bb[nb++] = c;
                c = j = 0;
            }
        }
        nc = na + nb;   // max length of A*B
        // initialize result array
        for (i = 0; i < nc; i++)
            cc[i] = 0;
        for (i = 0; i < na; i++) {
            long long m = 0;
            for (j = 0; j < nb; j++) {
                m += cc[i + j] + (long long)aa[i] * bb[j];
                cc[i + j] = m % m10[NDIGITS];
                m /= m10[NDIGITS];
            }
            cc[i + j] += m;
        }
        for (i = nc; i-- > 0 && cc[i] == 0;)
            continue;
        printf("%d", cc[i]);
        while (i-- > 0)
            printf("%0*d", NDIGITS, cc[i]);
        printf("\n");
    }
    return 0;
}

Answer 4

可以使用break;退出最外层的 for 循环。