大数相乘FFT

一直都想与我的一个好朋友XJF童鞋分（装）享（逼）一下本帅在学校里所学习滴本帅觉得很牛逼滴知识，今天晚上在吃柚子的时候，突然想通了，为什么这个大整数相乘阔以用到这个哪里都会不小心遇到的傅里叶了，today，就来qioyiqio：

1.为什么阔以用傅里叶喃？

其实这里是用的离散傅里叶变换（DFT）
离散傅里叶有个性质（算不算性质我也不晓得ヽ(￣▽￣)ﾉ），反正就是他在空域上卷积特别简单，叫做不进位乘法,

我们小学学乘法就这样子的噶，只不过要进哈位画红线的是什么喃？比如这里的123就是f(0)的值，所以左边就是f(-1)的值为1，右边是f(1)的值为3；
456同理。

得到这个然后再进位不就是答案了么。

关于傅里叶变换啥的 就有一个性质，叫做空域卷积，频域乘积；频域卷积，空域乘积，所以上一步那个不进位乘法，其实是空域里的卷积，而卷积的计算比较麻烦，所以把他变到频域直接乘积多简单。

没写完，先放着