存一波 FFT 大数乘法 模板 ：

#include<math.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

const double PI = acos(-1.0);
//复数结构体
struct Complex
{
    double r,i;
    Complex(double _r=0.0,double _i=0.0)
    {
        r = _r; i = _i;
    }
    Complex operator +(const Complex &b)
    {
        return Complex(r+b.r,i+b.i);
    }
    Complex operator -(const Complex &b)
    {
        return Complex(r-b.r,i-b.i);
    }
    Complex operator *(const Complex &b)
    {
        return Complex(r*b.r-i*b.i,r*b.i+i*b.r);
    }
};
/*
 * 进行FFT和IFFT前的反转变换。
 * 位置i和 （i二进制反转后位置）互换
 * len必须去2的幂
 */
void change(Complex y[],int len)
{
    int i=1,j=len/2,k;
    for(;i<len-1;i++){
        if(i<j)
            swap(y[i],y[j]);

        k=len/2;
        while(j>=k){
            j-=k;
            k/=2;
        }
        if(j<k)
            j+=k;
    }
}
/*
 * 做FFT
 * len必须为2^k形式，
 * on==1时是DFT，on==-1时是IDFT
 */
void fft(Complex y[],int len,int on)
{
    change(y,len);
    for(int h=2;h<=len;h<<= 1)
    {
        Complex wn(cos(-on*2*PI/h),sin(-on*2*PI/h));
        for(int j=0;j<len;j+=h)
        {
            Complex w(1,0);
            for(int k=j;k<j+h/2;k++){
                Complex u=y[k];
                Complex t=w*y[k+h/2];
                y[k]=u+t;
                y[k+h/2]=u-t;
                w=w*wn;
            }
        }
    }

    if(on==-1)
        for(int i=0;i<len;i++)
            y[i].r/=len;
}

const int MAXN=100010<<2;
Complex x1[MAXN],x2[MAXN];
char str1[MAXN/2],str2[MAXN/2];
int sum[MAXN];

int main()
{
    //freopen("in.txt","r",stdin);
    while(scanf("%s%s",str1,str2)==2)
    {
        int len1=strlen(str1);
        int len2=strlen(str2);
        int len=1;
        while(len<len1*2 || len<len2*2)
            len<<=1;
        for(int i=0;i<len1;i++)
            x1[i]=Complex(str1[len1-1-i]-''0'',0);
        for(int i=len1;i<len;i++)
            x1[i]=Complex(0,0);
        for(int i=0;i<len2;i++)
            x2[i]=Complex(str2[len2-1-i]-''0'',0);
        for(int i=len2;i<len;i++)
            x2[i]=Complex(0,0);
        //求DFT
        fft(x1,len,1);
        fft(x2,1);
        for(int i=0;i<len;i++)
            x1[i]=x1[i]*x2[i];
        fft(x1,-1);
        for(int i=0;i<len;i++)
            sum[i]=(int)(x1[i].r+0.5);///注意精度
        ///-----------结束-----------//
        for(int i=0;i<len;i++){
            sum[i+1]+=sum[i]/10;
            sum[i]%=10;
        }
        len=len1+len2-1;
        while(sum[len]<=0&&len>0)
            len--;
        for(int i=len;i>=0;i--)
            printf("%c",sum[i]+''0'');
        printf("\n");
    }
    return 0;
}

大数乘法

对于32位字长的机器，大约超过20亿，用int类型就无法表示了，我们可以选择int64类型，但无论怎样扩展，固定的整数类型总是有表达的极限！如果对超级大整数进行精确运算呢？一个简单的办法是：仅仅使用现有类型，但是把大整数的运算化解为若干小整数的运算，即所谓：“分块法”。

如图【1.jpg】表示了分块乘法的原理。可以把大数分成多段（此处为2段）小数，然后用小数的多次运算组合表示一个大数。可以根据int的承载能力规定小块的大小，比如要把int分成2段，则小块可取10000为上限值。注意，小块在进行纵向累加后，需要进行进位校正。

以下代码示意了分块乘法的原理（乘数、被乘数都分为2段）。

 

#include <stdio.h>

#include <iostream>

using namespace std;

 

void bigmul(int x,int y,int r[])

{

    int base = 10000;

    int x2 = x / base;

    int x1 = x % base;

    int y2 = y / base;

    int y1 = y % base;

 

    int n1 = x1 * y1;

    int n2 = x1 * y2;

    int n3 = x2 * y1;

    int n4 = x2 * y2;

 

    r[3] = n1 % base;

    r[2] = n1 / base + n2 % base + n3 % base;

    --------------- // 填空

    r[0] = n4 / base;

 

     ---------------  //填空

    r[2] = r[2] % base;

    r[0] += r[1] / base;

    r[1] = r[1] % base;

}

int main(int argc,char* argv[])

{

    int x[] = {0,0};

    bigmul(87654321,12345678,x);

    printf("%d%d%d%d\n",x[0],x[1],x[2],x[3]);

    system("pause");

    return 0;

}

 

 

 

解题思路：

不算难，就是类似平时乘法运算中的进位

按照它的算法，99*99应该是这个样子

 

99*99正常方法：

 99

x99

---------

  891

891

---------

9801

 

99*99用题中叙述的方法：

 99

x99

---------

       81

    81

    81

 81

---------

 9  8  0 1

 

假设9为r[0],8、0、1分别是r[1]、r[2]、r[3]，四个81分别是n1，n2、n3、n4。

则r[3]=n1%10；

r[2]=n1/10+n2%10+n3%10；

r[1]=n4%10+n2/10+n3/10；

r[0]=n4/10；

得到了上面的一组结果，很容易就推出了空格1，空格二就是简单的进位加减了，嘿嘿，分值到手！

 

#include <stdio.h>
#include <iostream>
using namespace std;

void bigmul(int x,int r[])
{
    int base = 10000;
    int x2 = x / base;
    int x1 = x % base;
    int y2 = y / base;
    int y1 = y % base;

    int n1 = x1 * y1;
    int n2 = x1 * y2;
    int n3 = x2 * y1;
    int n4 = x2 * y2;

    r[3] = n1 % base;//取最后一位 
    r[2] = n1 / base + n2 % base + n3 % base;//取倒数第二位（n1的首和n2、n3的尾相加） 
    r[1] = n2 / base + n3 / base + n4 % base; //取倒数第三位（n2、n3的首与n4的尾相加） 
    r[0] = n4 / base;//取n4的首 

    r[1] += r[2] / base;  // r[1]要加上后面进位的数 
    r[2] = r[2] % base;//只取进位后的余数 
    r[0] += r[1] / base;//r[0]要加上后面进位的数 
    r[1] = r[1] % base;//只取进位后的余数 
    //r[3]没有做任何加减，所以不需要进位也不需要加任何一位进的位数 
}
int main(int argc,char* argv[])
{
    int x[] = {0,0};
    bigmul(87654321,x);
    printf("%d%d%d%d\n",x[3]);
    system("pause");
    return 0;
}

A * B Problem Plus

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 12315    Accepted Submission(s): 2157


Problem Description

Calculate A * B.