当前位置：首页 > C++ > 正文

快速数论变换（NTT）详解：C++语言实现高效多项式乘法

主机测评网
C++
2025-12-16
207

在算法竞赛和密码学中，NTT算法（Number Theoretic Transform，数论变换）是一种用于高效计算两个整系数多项式乘积的重要工具。它是FFT（快速傅里叶变换）在模意义下的替代方案，特别适用于需要结果对某个质数取模的场景。

本教程将从零开始，用通俗易懂的方式讲解C++实现 NTT 的全过程，即使你是编程小白，也能轻松理解并掌握这一强大算法。

什么是NTT？

NTT 是 FFT 在有限域（模素数）中的类比。它利用模意义下的“单位根”来实现类似于复数域中 FFT 的分治策略，从而将多项式乘法的时间复杂度从 O(n²) 降低到 O(n log n)。

使用 快速数论变换 的前提是模数 p 必须满足：p = k × 2ⁿ + 1（即 p-1 能被足够大的 2 的幂整除），这样才能保证存在足够多的“原根”作为单位根。

快速数论变换（NTT）详解：C++语言实现高效多项式乘法 NTT算法 C++实现快速数论变换多项式乘法第1张

前置知识

模运算（取余）
快速幂（用于求逆元和原根的幂）
位运算（用于蝴蝶操作中的反转）

常用模数与原根

常见的 NTT 模数包括：

p = 998244353，原根 g = 3（最常用）
p = 1004535809，原根 g = 3

以 998244353 为例，它满足 998244353 = 119 × 2²³ + 1，因此最多可处理长度为 2²³ 的多项式。

C++ 实现步骤

我们将逐步实现以下功能：

快速幂函数
NTT 变换函数（支持正向和逆向）
多项式乘法主函数

1. 快速幂函数

long long qpow(long long a, long long b, long long mod) {    long long res = 1;    while (b) {        if (b & 1) res = res * a % mod;        a = a * a % mod;        b >>= 1;    }    return res;}

2. NTT 核心函数

const long long MOD = 998244353;const long long G = 3; // 原根void ntt(vector<long long> &a, bool invert) {    int n = a.size();    // 位逆序重排    for (int i = 1, j = 0; i < n; i++) {        int bit = n >> 1;        for (; j & bit; bit >>= 1)            j ^= bit;        j ^= bit;        if (i < j) swap(a[i], a[j]);    }    for (int len = 2; len <= n; len <<= 1) {        long long wlen = qpow(G, (MOD - 1) / len, MOD);        if (invert) wlen = qpow(wlen, MOD - 2, MOD); // 逆元        for (int i = 0; i < n; i += len) {            long long w = 1;            for (int j = 0; j < len / 2; j++) {                long long u = a[i + j];                long long v = a[i + j + len / 2] * w % MOD;                a[i + j] = (u + v) % MOD;                a[i + j + len / 2] = (u - v + MOD) % MOD;                w = w * wlen % MOD;            }        }    }    if (invert) {        long long inv_n = qpow(n, MOD - 2, MOD);        for (long long &x : a)            x = x * inv_n % MOD;    }}

3. 多项式乘法主函数

vector<long long> multiply(vector<long long> const& a, vector<long long> const& b) {    vector<long long> fa(a.begin(), a.end()), fb(b.begin(), b.end());    int n = 1;    // 找到大于等于 a.size() + b.size() - 1 的最小 2 的幂    while (n < (int)(a.size() + b.size()))        n <<= 1;    fa.resize(n);    fb.resize(n);    ntt(fa, false);    ntt(fb, false);    for (int i = 0; i < n; i++)        fa[i] = fa[i] * fb[i] % MOD;    ntt(fa, true);    // 截断多余项    fa.resize(a.size() + b.size() - 1);    return fa;}

完整示例

下面是一个完整的 C++ 程序，演示如何使用上述函数计算两个多项式的乘积：

#include <iostream>#include <vector>#include <algorithm>using namespace std;// 此处插入 qpow、ntt、multiply 函数int main() {    vector<long long> a = {1, 2, 3}; // 表示 1 + 2x + 3x²    vector<long long> b = {2, 1};     // 表示 2 + x    vector<long long> c = multiply(a, b);    // 结果应为 2 + 5x + 7x² + 3x³    for (long long x : c)        cout << x << " ";    cout << endl;    return 0;}