hdu1402 FFT 大数乘法

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<vector>
#include<map>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
const int N = 1e6+10;
int n;
struct Com{
    double r,i;
    Com(double r,double i):r(r),i(i){}
    Com(){}
    Com operator + (const Com& o){
        return Com(r+o.r,i+o.i);
    }
    Com operator - (const Com& o){
        return Com(r-o.r,i-o.i);
    }
    Com operator * (const Com& o){
        return Com(r*o.r-i*o.i,r*o.i+i*o.r);
    }
};
const double pi = acos(-1.0);
int rev(int id,int len){
    int ret = 0;
    for(int i=0;(1<<i)<len;i++){
        ret<<=1;
        if(id&(1<<i)) ret|=1;
    }
    return ret;
}
void FFT(Com* a,int len,int DFT){
    Com* A = new Com[len];
    for(int i=0;i<len;i++)
        A[rev(i,len)] = a[i];
    for(int s=1;(1<<s)<=len;s++){
        int m = (1<<s);
        Com wm = Com(cos(DFT*2*pi/m),sin(DFT*2*pi/m));
        for(int k=0;k<len;k+=m){
            Com w = Com(1,0);
            for(int j=0;j<(m>>1);j++){
                Com t = w*A[k+j+(m>>1)];
                Com u = A[k+j];
                A[k+j] = u+t;
                A[k+j+(m>>1)] = u-t;
                w = w*wm;
            }
        }
    }
    if(DFT==-1) for(int i=0;i<len;i++) A[i].r/=len,A[i].i/=len;
    for(int i=0;i<len;i++) a[i] = A[i];
}
char numA[N],numB[N];
Com a[N],b[N];
int ans[N];
int main(){
    while(scanf("%s",numA)==1){
        int sa = 0;
        int lenA = strlen(numA);
        while((1<<sa)<lenA) sa++;
        int sb = 0;
        scanf("%s",numB);
        int lenB = strlen(numB);
        while((1<<sb)<lenB) sb++;
        int len = (1<<(max(sa,sb)+1));

        for(int i=0;i<len;i++){
            if(i<lenA) a[i] = Com(numA[lenA-1-i]-'0',0);
            else a[i] = Com(0,0);
            if(i<lenB) b[i] = Com(numB[lenB-1-i]-'0',0);
            else b[i] = Com(0,0);
        }

        FFT(a,len,1);
        FFT(b,1);
        for(int i=0;i<len;i++)
            a[i] = a[i]*b[i];
        FFT(a,-1);

        for(int i=0;i<len;i++)
            ans[i] = (int)(a[i].r+0.5);
        for(int i=0;i<len-1;i++){
            ans[i+1]+=ans[i]/10;
            ans[i]%=10;
        }
        int flag = 0;
        for(int i=len-1;i>=0;i--){
            if(ans[i]) printf("%d",ans[i]),flag=1;
            else if(flag || i==0) printf("0");
        }
        puts("");
    }

    return 0;
}

（编辑：辽源站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!