大数乘法用FFT而非竖式因FFT将复杂度从O(n²)降至O(n log n)，但需双精度FFT+拆系数+进位校正或改用NTT避免浮点精度误差。
为什么大数乘法要用FFT而不是直接模拟竖式
因为竖式乘法时间复杂度是 O(n²)，两个百万位整数相乘可能要几秒甚至超时；而FFT能把卷积转成点值乘法，把乘法复杂度压到 O(n log n)。但注意：FFT本身是浮点运算，有精度误差，直接用于大数会错——必须用**双精度FFT + 拆系数 + 进位校正**，或者改用NTT（数论变换）。实际工程中，std::vector<int></int> 手写高精度配 FFT 是可行的，但别指望 std::complex<double></double> 直接扔进去就对。
FFT实现大数乘法的关键三步
核心不是调库，而是把大数转成系数向量、做长度足够的FFT、再IDFT还原并处理进位：
- 把两个大数按低位在前拆成数组，比如
"12345"→{5,4,3,2,1}，每个元素是 0–9 的 digit - 确定 FFT 长度：
len = 1 （即不小于 <code>2n-1的最小 2 的幂） - 用
std::vector<:complex>></:complex>存系数，调用自实现或fftw的fft()和ifft()；IDFT 后每个位置取round(real())，再从低位开始逐位进位（注意进位可能大于 10，要 while 循环）
精度崩了怎么办：常见错误和绕过方法
典型现象是结果末几位错，比如 123456789 * 987654321 算出 121932631112635268（少 1）。原因：double 只有约 15–16 位有效数字，当系数乘积超过 1e15 就开始丢精度。解决办法：
- 拆系数：把每位 digit 拆成高/低两部分，例如用 base=1000，让单个数组元素存 0–999，降低最大值
- 用 long double（如果平台支持），或改用
__float128（GCC 扩展，但慢） - 更稳的选择：换 NTT，模一个大质数如
998244353，用int运算无精度问题；但需保证结果 - 别用
std::complex<float></float>—— float 根本撑不住，连 10⁵ 位都容易挂
有没有现成能跑的 minimal 示例
下面这段是可直接编译运行的简化版（省略复数 FFT 实现，只列主干逻辑）：
立即学习“C++免费学习笔记（深入）”；
std::vector<int> multiply(const std::vector<int>& a, const std::vector<int>& b) {
int n = a.size(), m = b.size();
int len = 1; while (len < n + m) len <<= 1;
std::vector<std::complex<double>> fa(len), fb(len);
for (int i = 0; i < n; ++i) fa[i] = a[i];
for (int i = 0; i < m; ++i) fb[i] = b[i];
fft(fa); fft(fb);
for (int i = 0; i < len; ++i) fa[i] *= fb[i];
ifft(fa);
std::vector<int> res(len);
for (int i = 0; i < len; ++i) res[i] = (int)round(fa[i].real());
// 进位
for (int i = 0; i + 1 < len; ++i) {
res[i + 1] += res[i] / 10;
res[i] %= 10;
}
while (res.size() > 1 && res.back() == 0) res.pop_back();
return res;
}
真正上线前必须加精度防护：比如对每个 res[i] 做 std::abs(res[i] - round(res[i])) 校验，否则某个位置四舍五入错一点，后面全进位链就崩了。
