ntt无浮点误差因其全程在整数模p域运算，用原根幂替代复数单位根，避免cos/sin与double计算；要求模数p为形如k·2^m+1的质数，如998244353，否则数学前提失效。
NTT 从根本上不使用浮点数，所以它不是“消除”FFT的精度误差，而是绕开浮点运算体系——所有加减乘模都在整数域 mod p 内完成，自然没有 double 累积误差这回事。
为什么NTT没有浮点误差
FFT 依赖 cos/sin 计算复数单位根 ω_n，每次乘法都涉及四次 double 运算，且中间结果无法精确表示（比如 cos(2π/7) 是无理数）。NTT 则用模素数 p 下的整数原根幂次替代 ω_n，例如在 mod 998244353 下，g = 3 是原根，取 g_n = pow(3, (p-1)/n) 作为 n 次单位根的等价物。所有运算都是 a * b % p、(a + b) % p 这类确定性整数操作。
- 没有
sqrt、cos、sin调用 - 没有
std::complex<double></double>类型参与计算 - 逆变换时除法通过模逆元
pow(M, p-2, p)实现，仍是整数模运算
常见模数选择直接影响是否能避免精度问题
NTT 要求模数 p 满足：是质数，且 p = k * 2^m + 1（即 p ≡ 1 (mod 2^m)），这样才能保证对长度为 2^m 的序列存在 2^m 次单位根。若强行用不满足条件的模数（如 10^9+7），则无法定义完整的蝶形结构，要么报错，要么结果错误——这不是精度问题，而是数学前提崩塌。
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 推荐模数：
998244353（7 * 17 * 2^23 + 1，支持最大长度2^23） - 次选：
1004535809（479 * 2^21 + 1）、167772161（5 * 2^25 + 1） - 禁用：
10^9+7（不满足p ≡ 1 mod 2^m形式，无法直接用于标准NTT）
NTT代码里最容易引入隐式浮点误差的地方
表面上全是整数运算，但几个地方可能悄悄引入 double 或溢出导致结果错乱：
-
log2(M)：如果用std::log2计算位宽，传入大整数时可能因double精度丢失返回错误值（如log2(2^20) == 19.9999999导致向下取整出错）。应改用位运算：31 - __builtin_clz(M)或循环左移计数 -
int l = log2(M)后用于蝴蝶数组r[i]构造：若l错了，r[i]位逆序就全错，后续所有swap都失效 - 乘法未及时取模：
a * b可能爆long long（如998244353 * 998244353 > 2^63），必须写成1LL * a * b % mod或用__int128中转
真正难处理的不是“精度”，而是模数适配性和整数溢出控制——一旦选错模或漏写 % mod，结果就完全不可逆，连调试都找不到浮点痕迹。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
