ACM学习历程—51NOD1028 大数乘法V2（FFT）

题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1028

题目大意就是求两个大数的乘法。

但是用普通的大数乘法，这个长度的大数肯定不行。

大数可以表示点值表示法，然后卷积乘法就能用FFT加速运算了。

这道题是来存模板的。

代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <string>
#define LL long longusing namespace std;//多项式乘法运算
//快速傅里叶变换
//FFT
//用于求两个多项式的卷积,但有精度损失
//时间复杂度nlogn
const int maxN = 400005;
const double PI = acos(-1.0);struct Complex
{double r, i;Complex(double rr = 0.0, double ii = 0.0){r = rr;i = ii;}Complex operator+(const Complex &x){return Complex(r+x.r, i+x.i);}Complex operator-(const Complex &x){return Complex(r-x.r, i-x.i);}Complex operator*(const Complex &x){return Complex(r*x.r-i*x.i, i*x.r+r*x.i);}
};//雷德算法--倒位序
//Rader算法
//进行FFT和IFFT前的反转变换。
//位置i和 （i二进制反转后位置）互换
void Rader(Complex y[], int len)
{int j = len>>1;for(int i = 1; i < len-1; i++){if (i < j) swap(y[i], y[j]);int k = len >> 1;while (j >= k){j -= k;k >>= 1;}if (j < k) j += k;}
}//FFT实现
//len必须为2^k形式，
//on==1时是DFT，on==-1时是IDFT
void FFT(Complex y[], int len, int on)
{Rader(y, len);for (int h = 2; h <= len; h<<=1)//分治后计算长度为h的DFT
    {Complex wn(cos(-on*2*PI/h), sin(-on*2*PI/h)); //单位复根e^(2*PI/m)用欧拉公式展开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;
}//求卷积
void Conv(Complex a[], Complex b[], int ans[], int len)
{FFT(a, len, 1);FFT(b, len, 1);for (int i = 0; i < len; i++)a[i] = a[i]*b[i];FFT(a, len, -1);//精度复原for(int i = 0; i < len; i++)ans[i] = a[i].r+0.5;
}//进制恢复
//用于大数乘法
void turn(int ans[], int len, int unit)
{for(int i = 0; i < len; i++){ans[i+1] += ans[i]/unit;ans[i] %= unit;}
}char str1[maxN], str2[maxN];
Complex za[maxN],zb[maxN];
int ans[maxN];
int len;void init(char str1[], char str2[])
{int len1 = strlen(str1);int len2 = strlen(str2);len = 1;while (len < 2*len1 || len < 2*len2) len <<= 1;int i;for (i = 0; i < len1; i++){za[i].r = str1[len1-i-1]-'0';za[i].i = 0.0;}while (i < len){za[i].r = za[i].i = 0.0;i++;}for (i = 0; i < len2; i++){zb[i].r = str2[len2-i-1]-'0';zb[i].i = 0.0;}while (i < len){zb[i].r = zb[i].i = 0.0;i++;}
}void work()
{Conv(za, zb, ans, len);turn(ans, len, 10);while (ans[len-1] == 0) len--;for (int i = len-1; i >= 0; i--)printf("%d", ans[i]);printf("\n");
}int main()
{//freopen("test.in", "r", stdin);while (scanf("%s%s", str1, str2) != EOF){init(str1, str2);work();}return 0;
}