sdnu 1531 a*b III

Description

计算a乘b，多组输入（50组以内）。

Input

输入a b，数据范围0 <= a,b <= 10^100000。

Output

输出a与b的乘积。

Sample Input

2 2
4 4

Sample Output

4
16

Hint

FFT

高精度乘法

将其转化为两个多项式相乘。

设其中一个数共n位，将它 从个位开始到第n位 的 每一位的数值（这个数值只有一位） 类比成 多项式 从0次项到n-1次项 的系数

（即一个n位的数相当于一个n-1次的多项式）

所以在FFT之前要把这个数反过来，FFT之后从高位到低位输出。

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <complex>
#include <iostream>
using namespace std;

typedef complex<double> cd;     ///复数类的定义
const int maxx = 2094153;       ///nlongn的最大长度
const double pi = acos(-1.0);   ///圆周率

cd ar[maxx], br[maxx];          ///存储中间转换结果
int rev[maxx];                  ///存储二进制反转结果

///二进制转换位置，bit为最长的长度，必定是2的幂
void getrev (int bit)
{
    for (int i = 0; i < (1<<bit); i++)
    {
        rev[i] = (rev[i>>1]>>1)|((i&1)<<(bit-1));
    }
}

///a为转换后的数组，n是数组长度，dft是控制dft和idft
void fft (cd *a, int n, int dft)
{
    ///按照二进制翻转
    for (int i = 0; i < n; i++)
    {
        if (i < rev[i])
        {
            swap(a[i], a[rev[i]]);
        }
    }
    ///蝴蝶操作模拟合并过程
    for (int step = 1; step < n; step <<= 1)        ///模拟合并的次数
    {
        cd wn = exp(cd(0, dft*pi/step));            ///计算单位复根
        for (int j = 0; j < n; j += (step<<1))      ///模拟合并一次的组数
        {
            cd wnk(1, 0);                           ///每个独立序列都是从0开始的
            for (int k = j; k < j+step; k++)        ///模拟合并的每一组
            {
                cd x = a[k];
                cd y = wnk*a[k+step];
                a[k] = x+y;
                a[k+step] = x-y;
                wnk *= wn;                          ///计算下一次复根
            }
        }
    }
    ///idft的情况
    if (dft == -1)
    {
        for (int i = 0; i < n; i++)
        {
            a[i] /= 1.0*n;
        }
    }
}

int output[maxx];           ///输出
char s1[maxx], s2[maxx];    ///输入

int main ()
{
    while(scanf("%s %s", s1, s2)!=EOF)///一个字符串代表一个多项式 字符串从右向左的每一位分别对应多项式0次项的系数、1次项的系数……n次项的系数（所以说如果输出俩多项式相乘后的每一位要逆序输出）
    {
        memset(ar,0,sizeof(ar));
        memset(br,0,sizeof(br));
        memset(output,0,sizeof(output));
        int l1 = strlen(s1), l2 = strlen(s2);
        int bit = 1, s = 2;     ///bit表示数组的二进制位数，s表示分割的长度
        for (bit = 1; (1<<bit) < l1+l2-1; bit++)
        {
            s <<= 1;            ///找到一个2的整数次幂可以容纳这两个串的乘积
        }
        ///存入ar,br中(输入是按照次数从高到低进行的)，从低到高次幂开始从0开始存入
        for (int i = 0; i < l1; i++)///一个n位的数 相当于一个(n-1)次的多项式
        {
            ar[i] = (double)(s1[l1-i-1]-'0');
        }
        for (int i = 0; i < l2; i++)
        {
            br[i] = (double)(s2[l2-i-1]-'0');
        }
        ///转换数组模拟
        getrev(bit);
        ///分别DFT
        fft(ar, s, 1);
        fft(br, s, 1);
        ///对应相乘
        for (int i = 0; i < s; i++)
        {
            ar[i] *= br[i];
        }
        ///进行IDFT
        fft(ar, s, -1);
        ///存入输出数组
        for (int i = 0; i < s; i++)
        {
            output[i] += (int)(ar[i].real()+0.5);
            ///每项对应的系数乘以位权后相加得到最终乘积
            ///如果没有这一步输出的直接是多项式各项系数 （从0次至n次）
            output[i+1]+=output[i]/10;
            output[i]%=10;
        }
        ///首项为0的全都去掉
        int i;
        for (i = l1+l2; !output[i] && i >= 0; i--) ;
        ///输出
        if(i==-1)///相乘为0
            cout<<'0';
        for (i; i >= 0; i--)///因为高位在后，低位在前 所以逆序输出
        {
            printf("%d", output[i]);
        }
        cout << '\n';
    }
    return 0;
}