洛谷P1919 【模板】A*B Problem升级版（FFT快速傅里叶）

刚学完FFT，拿来连练手
题目链接：https://www.luogu.com.cn/problem/solution/P1919
解题思路：
FFT是解决多项式乘法的，想办法把数给变成多项式
比如：
有了这个处理以后，我们可以直接看出来数的乘法不就是多项式乘法吗？！
代码中有些细节问题已做出注释
代码：

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <complex>
using namespace std;
#define cp complex<double>
const int N = 4e6+7;        //虽然题目数据是1e6，但是下面的n可能会是4e6
const double pi = acos(-1.0);
char sa[N], sb[N];
int n = 1, lena, lenb, res[N], rev[N];
cp  aa[N], bb[N];
void fft(cp *a,int inv)
{
    int bit = 0;
    while((1<<bit)<n)bit++;
    for(int i = 0; i <= n-1; i++)
    {
        rev[i]=(rev[i>>1]>>1|((i&1)<<(bit-1)));
        if(i < rev[i]) swap(a[i],a[rev[i]]);
    }
    for(int mid = 1; mid < n; mid*=2)
    {
        cp temp(cos(pi/mid),inv*sin(pi/mid));
        for(int i = 0; i < n; i+=mid*2)
        {
            cp omega(1,0);
            for(int j = 0; j < mid; j++,omega*=temp)
            {
                cp x = a[i+j], y = omega*a[i+j+mid];
                a[i+j] = x+y, a[i+j+mid]=x-y;
            }
        }
    }
}
int main()
{
    scanf("%s",sa);
    scanf("%s",sb);
    int lena = strlen(sa), lenb = strlen(sb);
    while(n < lena + lenb) n*=2;    //n是2的整数次幂
    for(int i = 0; i < lena; i++)
        aa[i].real(sa[lena - 1 - i] - '0');
    for(int i = 0; i < lenb; i++)
        bb[i].real(sb[lenb - 1 - i] - '0');
    fft(aa, 1);
    fft(bb, 1);
    for(int i = 0; i < n; i++)
        aa[i] *= bb[i];
    fft(aa, -1);
    for(int i = 0; i < n; i++) {
        res[i] += (int)(aa[i].real() / n + 0.5);    //注意精度
        res[i + 1] += res[i] / 10;
        res[i] %= 10;
    }
    for(int i = res[lena + lenb - 1] ? lena + lenb - 1: lena + lenb - 2; i >= 0; i--)    //两个数的乘积的长度要不然是lena+lenb,要不然是lena+lenb-1
        printf("%c",(char)res[i]+'0');
    printf("\n");
}