大数乘法用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 实现，只列主干逻辑）：
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 > fa(len), fb(len);
for (int i = 0; i res(len);
for (int i = 0; i 1 && res.back() == 0) res.pop_back();
return res;
}
</int></int></int>
真正上线前必须加精度防护：比如对每个 res[i] 做 std::abs(res[i] - round(res[i])) 校验，否则某个位置四舍五入错一点，后面全进位链就崩了。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
