首页 > > 程序设计 > C/C++ >

大整数乘法（分治法）

2018-06-17 23:44:56来源：未知阅读 ()

题目：输入两个大整数，用数组保存每一位数，然后用分治法计算；

思路：输入X Y，X高位用A数组保存，低位用B数组保存，Y高位用C数组保存，低位用D数组保存，则：X=A*10^(n/2)+B Y=C*10^(n/2)+D

分治方法：X*Y=A*C*10^n+((A-B)*(D-C)+A*C+B*D)*10^(n/2)+B*D;

代码如下：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
#include <vector>
using namespace std;

void add(int a[],int b[],int c[])
{
    int tot=0;
    int maxn=max(a[0],b[0]);
    for(int i=2; i<=maxn+2; i++)
    {
        c[i]=(a[i]+b[i]+tot)%10;
        tot=(a[i]+b[i]+tot)/10;
    }
    c[0]=maxn+(c[maxn+2]>0);
    c[1]=a[1];
}
void sub(int a[],int b[],int c[])
{
    int tot=0;
    int maxn=max(a[0],b[0]);
    c[1]=1;
    for(int i=maxn+1; i>=2; i--)
    {
        if(a[i]>b[i])  break;
        if(a[i]<b[i])
        {
            swap(a,b);
            c[1]=-1;
            break;
        }
    }
    for(int i=2; i<=maxn+1; i++)
    {
        c[i]=a[i]+tot-b[i];
        if(c[i]<0)
        {
            c[i]=c[i]+10;
            tot=-1;
        }
        else tot=0;
    }
    c[0]=a[0];
}
void process(int a[],int b[],int c[],int g)
{
    if(a[1]>0)
    {
        if(b[1]*g>0)  add(a,b,c);
        else      sub(a,b,c);
    }
    else
    {
        if(b[1]*g>0)  sub(b,a,c);
        else      add(a,b,c);
    }
}
void Move(int a[],int n)
{
    for(int i=a[0]+1; i>=2; i--)
        a[i+n]=a[i];
    for(int i=2; i<=n+1; i++)
        a[i]=0;
    a[0]+=n;
}
void print(int c[])
{
    int i;
    if(c[1]<0) cout<<"-";
    for(i=c[0]+1; i>=2; i--)
        if(c[i]) break;
    for(; i>=2; i--)
        cout<<c[i];
    cout<<endl;
}
void duiqi(int a[],int b[])
{
    int maxn=max(a[0],b[0]);
    int tmp=1;
    for(int i=0;i<=10;i++)
    {
        if(tmp>=maxn) break;
        tmp<<=1;
    }
    a[0]=tmp;
    b[0]=tmp;
}
void calc(int a[],int b[],int c[])
{
    if(a[0]==1)
    {
        int tmp=a[2]*b[2];
        c[0]=1;
        c[2]=tmp%10;
        if(tmp>=10)
        {
            c[3]=tmp/10;
            c[0]++;
        }
        c[1]=a[1]*b[1];
        return;
    }

    int A[1000],B[1000],C[1000],D[1000],E[1000],F[1000];
    int m1[1000],m2[1000],m3[1000];
    memset(A,0,sizeof(A));
    memset(B,0,sizeof(B));
    memset(C,0,sizeof(C));
    memset(D,0,sizeof(D));
    memset(E,0,sizeof(E));
    memset(F,0,sizeof(F));
    memset(m1,0,sizeof(m1));
    memset(m2,0,sizeof(m2));
    memset(m3,0,sizeof(m3));
    for(int i=1; i<=a[0]/2+1; i++)
        B[i]=a[i];
    B[0]=a[0]/2;
    for(int i=a[0]/2+2; i<=a[0]+1; i++)
        A[i-a[0]/2]=a[i];
    A[0]=a[0]/2;
    A[1]=a[1];

    for(int i=1; i<=b[0]/2+1; i++)
        D[i]=b[i];
    D[0]=b[0]/2;
    for(int i=b[0]/2+2; i<=b[0]+1; i++)
        C[i-b[0]/2]=b[i];
    C[0]=b[0]/2;
    C[1]=b[1];
    process(A,B,E,-1);
    process(D,C,F,-1);
    calc(A,C,m1);
    calc(E,F,m2);
    calc(B,D,m3);
    process(m2,m1,E,1);
    process(E,m3,F,1);
    Move(m1,a[0]);
    Move(F,a[0]/2);
    process(m1,F,E,1);
    process(E,m3,c,1);
}
int main()
{
    int a[1000],b[1000],c[2000];
    char s1[1000],s2[1000];
    cin>>s1>>s2;
    a[0]=strlen(s1)-1;
    if(s1[0]=='-') a[1]=0;
    else       a[1]=1;
    a[0]+=a[1];
    for(int i=2; i<=a[0]+1; i++)
        a[i]=s1[a[0]-a[1]-i+2]-'0';

    b[0]=strlen(s2)-1;
    if(s2[0]=='-') b[1]=0;
    else       b[1]=1;
    b[0]+=b[1];
    for(int i=2; i<=b[0]+1; i++)
        b[i]=s2[b[0]-b[1]-i+2]-'0';
    a[1]+=a[1]-1;
    b[1]+=b[1]-1;
    duiqi(a,b);
    calc(a,b,c);
    print(c);
    return 0;
}