HDU#1402. A×B

---

A * B Problem Plus

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

Problem Description

Calculate A * B.

 

Input

Each line will contain two integers A and B. Process to end of file.

Note: the length of each integer will not exceed 50000.

 

Output

For each case, output A * B in one line.

 

Sample Input

1 2 1000 2

 

Sample Output

2 2000

 

Author

DOOM III

---

FFT入门题

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=2e5+12;
const double pi=acos(-1);
struct complex
{
    double x,i;
    complex(){}
    complex(double a,double b) {x=a;i=b;}
}A[maxn],B[maxn];
complex operator + (complex a,complex b) {return complex(a.x+b.x,a.i+b.i);}
complex operator - (complex a,complex b) {return complex(a.x-b.x,a.i-b.i);}
complex operator * (complex a,complex b) {return complex(a.x*b.x-a.i*b.i,a.x*b.i+a.i*b.x);}
int n;
int rev[maxn];
void FFT(complex *a,int t)
{
    for(int i=0;i<n;i++) if(rev[i]>i) swap(a[i],a[rev[i]]);//交换 
    for(int i=1;i<n;i<<=1)//当前块的长度 
    {
        complex wn(cos(2*pi/(i<<1)),t*sin(2*pi/(i<<1)));//wn 
        for(int j=0;j<n;j+=(i<<1))//处于哪一块 
        {
            complex w(1,0),t0,t1;
            for(int k=0;k<i;k++) //块上的位置 
            {
                t0=a[j+k];t1=w*a[j+k+i];//蝴蝶交换 
                a[j+k]=t0+t1;
                a[j+k+i]=t0-t1;
                w=w*wn;
            }
        }
    }
}
int sum[maxn];
int main()
{
    freopen("a.in","r",stdin);
    char s1[maxn],s2[maxn];
    while(scanf("%s%s",s1,s2)!=EOF)
    {
        int len1=strlen(s1),len2=strlen(s2);
        int len=1;
        while(len<len1*2||len<len2*2) len<<=1;//两数之积不超过最大数次数的2倍 
        for(int i=0;i<len1;i++) A[i]=complex(s1[len1-i-1]-'0',0);
        for(int i=len1;i<len;i++) A[i]=complex(0,0);
        for(int i=0;i<len2;i++) B[i]=complex(s2[len2-i-1]-'0',0);
        for(int i=len2;i<len;i++) B[i]=complex(0,0);
        n=len;
        rev[0]=0;
        int L=0;// 
        for(int i=1;i<len;i<<=1) L++;
         for(int i=0;i<n;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(L-1));//交换对象 
        
        FFT(A,1);FFT(B,1);//DFT
        for(int i=0;i<len;i++) A[i]=A[i]*B[i];//点积相乘 
        FFT(A,-1);//逆DFT 
        for(int i=0;i<len;i++) sum[i]=(int)(A[i].x/len+0.5);//减少误差 逆DFT需要多除以个len 
        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) len--;
        for(int i=len;i>=0;i--) printf("%d",sum[i]);
        printf("
");
    }
    return 0;
}

---