大数相乘 （模板）

输入两个不超过200位的大数，输出它们的积

输入样例
12345678900
98765432100

输出样例
1219326311126352690000

 

 在下面的例子程序中，用 a[220]和b[220]分别存放两个乘数，用
z[440]来存放积。计算的中间结果也都存在z中，长度取400 是因为两个
200 位的数相乘，积最多会有400 位。a[0], b[0], z[0]都表示个位。
计算的过程基本上和小学生列竖式做乘法相同。为编程方便，并不急于处理进位，而将
进位问题留待最后统一处理。
现以 835×49 为例来说明程序的计算过程。

先算835×9。5×9 得到45 个1，3×9 得到27 个10，8×9 得到72 个100。由于不急
于处理进位，所以835×9 算完后，z 如下：

下标                         5        4          3          2          1            0

z                      ......              0         0          72      27         45

接下来算4×5。此处4×5 的结果代表20 个10，因此要 z[1]+=20，变为：
下标                         5        4          3           2          1           0

z                     .......              0        0         72         47         45

再下来算4×3。此处4×3 的结果代表12 个100，因此要 z[2]+= 12，变为：
下标                         5         4           3         2            1            0

z                     ..........            0           0        84           47         45
最后算 4×8。此处4×8 的结果代表 32 个1000，因此要 z[3]+= 32，变为：

下标                        5           4         3         2            1             0

z                     .......                0        32       84        47            45
乘法过程完毕。接下来从z[0]开始向高位逐位处理进位问题。z[0]留下5，
把4 加到z[1]上,z[1]变为51 后，应留下1，把5 加到z[2]上……最终使
得z 里的每个元素都是1 位数，结果就算出来了：

下标                          5           4            3           2          1          0

z                       ......     0           4          0            9          1          5

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stdlib.h>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#include<math.h>
using namespace std;
typedef long long ll;
typedef double ld;

int a[220]={0},b[220]={0},z[440]={0};
char x[220],y[220];
int main()
{
    gets(x);
    int lenx=strlen(x);
    gets(y);
    int leny=strlen(y);
    int i,j;
    for(j=0,i=lenx-1; i>=0; i--)
        a[j++]=x[i]-'0';
    for(j=0,i=leny-1; i>=0; i--)
        b[j++]=y[i]-'0';
    for(i=0; i<lenx; i++)
        for(j=0; j<leny; j++)
            z[i+j]+=a[i]*b[j];
    for(i=0; i<420; i++)
    {
        z[i+1]+=z[i]/10;
        z[i]%=10;
    }
    for(i=420;!z[i];i--);//去掉前导零
    for(j=i; j>=0; j--)
        printf("%d",z[j]);
    printf("\n");
    return 0;
}

快速乘：

inline ll mul(ll x, ll y, ll mod)
{
  return (x * y - (ll)((long double)x / mod * y) * mod + mod) % mod;
}