这是一份计算两个n次的整系数多项式在模m意义下的乘积的代码。典型的一次运算用到4次n点的double类型的FFT（其中2次DFT，2次IDFT）。
这份代码在我的MacBook Pro 13'上（2.6 GHz Intel Core i5），n=10w的一次乘法耗时110ms，在另一台机器（E5-2650 v3 @ 2.30GHz）上耗时60ms。
对于32位整型范围内的模数m，本机测试至少可以保证n=400w无错（主要受限于Xcode的连接器，它似乎不让我开更大的数组了），如果使用long double，保守估计32位的n不会出错（当然估计得算上一天了）
个人估计对于n=10w，m可以取到1e12这个等级。欢迎测试。（拍正确性需要一个在int64内不溢出的乘法，懒得写了）
详细的一些说明可以移步http://async.icpc-camp.org/d/408-fft。注意里面的一些数学公式parse的不太对，但是我已经没有权限去编辑了。
大致用到两个Trick，一是如果选取合适的整数t，将0..m-1的每个整数都写成at+b的形式，我们可以把送进DFT的实数序列中元素的两个分量都控制在Ω(m^0.5)以及O(m^0.75)以内。
另一个Trick是说，如果待相乘的系数满足某些程度的随机性，那么不论是DFT的结果，还是卷积之后（还没有被模m）的结果，都可以有更好的界。
也欢迎来帮助更好地Bound计算main.cpp中参数M的那个函数的渐进（见magic_number_gen.cpp）。