算法提高 P1001【大数乘法】

当两个比较大的整数相乘时，可能会出现数据溢出的情形。为避免溢出，可以采用字符串的方法来实现两个大数之间的乘法。具体来说，首先以字符串的形式输入两个整数，每个整数的长度不会超过8位，然后把它们相乘的结果存储在另一个字符串当中（长度不会超过16位），最后把这个字符串打印出来。例如，假设用户输入为：62773417和12345678，则输出结果为：774980393241726.

输入：
　　62773417 12345678

输出：
　　774980393241726

题目分析

用一个整数数组，来装每一次两个一位数的乘法结果，大数乘法结束后，再解决进位问题，最终倒序输出即可。

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cstring>

#include <vector>

#include <stdlib.h>

#include <cstdlib>

#include <string.h>

#include <cmath>

using namespace std;

char a[], b[];

int len_a, len_b;

int c[];

void calculate() {

    for (int i = ;i < len_a; i++) {

        for (int j = ; j < len_b; j++) {

            c[i + j] += (a[i]- '') * (b[j] - '');

        }

    }

    int t = ;

    for (int i = ; i < ; i++) {

        c[i] += t;

        t = c[i] / ;

        c[i] %= ;

    }

}

void pri() {

    int i = len_a + len_b - ;

    for (; i >= ; i--)

        if (c[i] != )

            break;//找到第一位非零数字

    if (i < )

        cout << "";//没有一位是非零数字

    for (; i >= ; i--) {

        cout << c[i];

    }

}

int main() {

    scanf("%s", a);

    strrev(a);//逆置字符串

    len_a = strlen(a);

    scanf("%s", b);

    strrev(b);//逆置字符串

    len_b = strlen(b);

    calculate();

    pri();

    return ;

}