高精度乘法(II)

GitHub跳转原题关系图返回列表

把十进制大数看成以 10 为底的多项式,用 FFT 在 O(n log n) 内求系数卷积,再从低位到高位统一进位得到乘积。

OJ: roj

题目 ID: 2128

难度:提高

标签:高精度FFT多项式python

创建: 2026-10-08 07:50

更新: 2026-10-08 07:50

形式化题目

给定两个十进制正整数 aa 与 bb,位数均小于 200000200000,求 c=a×bc = a \times b 的十进制表示。

把 aa、bb 写成数位序列

a=∑i=0La−1ai10i,b=∑j=0Lb−1bj10j,ai,bj∈{0,1,…,9},a = \sum_{i=0}^{L_a-1} a_i 10^i, \qquad b = \sum_{j=0}^{L_b-1} b_j 10^j, \qquad a_i, b_j \in \{0, 1, \dots, 9\},

其中 aia_i 是 aa 的从低位数第 ii 位(即 aa 的十进制串逆序后的第 ii 个字符)。 要求输出的 cc 满足

c=∑p≥0cp10p,sk=∑i+j=kaibj,cp=⌊sp+⌊(sp−1+⌊⋯ ⌋)/10⌋10⌋ mod 10.c = \sum_{p \ge 0} c_p 10^p, \qquad s_k = \sum_{i+j=k} a_i b_j, \qquad c_p = \left\lfloor \frac{s_p + \lfloor (s_{p-1} + \lfloor \cdots \rfloor)/10 \rfloor}{10} \right\rfloor \bmod 10 .

换句话说,先求两个数位序列的卷积 ss,再做一次从低位到高位的十进制进位整理, 最后剥掉前导零输出。输出不要求固定宽度,c=0c = 0 时输出一个 0。

正解

思路

朴素做法及其瓶颈。 直接按竖式模拟:

s[i+j]+=ai⋅bj(0⩽i<La,  0⩽j<Lb),s[i+j] \mathrel{+}= a_i \cdot b_j \qquad (0 \leqslant i < L_a,\; 0 \leqslant j < L_b),

再统一进位。循环体只有一次乘法一次加法,常数极小,但次数是 LaLbL_a L_b。 当 La=Lb=200000L_a = L_b = 200000 时是 4×10104 \times 10^{10} 次乘加,限时 1000 ms 内无望。

瓶颈非常明确:付出的代价是「位数 × 位数」,而这个乘积里绝大部分是重复的相位组合。 把视角从"数字"换成"多项式",就会看到 ss 正是多项式乘积的系数:

A(x)=∑iaixi,B(x)=∑jbjxj,C(x)=A(x)B(x)=∑kskxk.A(x) = \sum_{i} a_i x^i, \qquad B(x) = \sum_{j} b_j x^j, \qquad C(x) = A(x) B(x) = \sum_k s_k x^k .

两个多项式相乘需要 O(LaLb)O(L_a L_b),这没有变。但多项式有两种等价表示:系数表示和点值表示。 在点值表示下,两个多项式相乘只是 nn 个点逐点相乘:

C(ωk)=A(ωk)⋅B(ωk)(k=0,1,…,n−1),C(\omega^k) = A(\omega^k) \cdot B(\omega^k) \qquad (k = 0, 1, \dots, n-1),

这一步只要 O(n)O(n)。所以只要能廉价地在两种表示之间来回转换,乘法就变快了—— 而单位复根的对称性与周期性让这一步的代价是 O(nlog⁡n)O(n \log n),这就是快速傅里叶变换(FFT)。

为什么用 FFT 而不是别的。 Karatsuba 是 O(n1.58)O(n^{1.58}),200000200000 位上常数不小、时限吃紧; NTT 需要挑质数与原根、还要处理模数溢出,代码更长。而 FFT 只需保证精度:

max⁡ksk⩽min⁡(La,Lb)⋅9⋅9<200000×81≈1.62×107,\max_k s_k \leqslant \min(L_a, L_b) \cdot 9 \cdot 9 < 200000 \times 81 \approx 1.62 \times 10^{7},

远小于 double 的 53 位尾数能精确表示的连续整数上界(此时仍在 253≈9×10152^{53} \approx 9 \times 10^{15} 以内), 所以变换过程中的舍入误差最终一定被 round 抹平,不会出现错位。

长度取多少。 卷积长度是 La+Lb−1L_a + L_b - 1。为了用迭代式 FFT 必须补到 2 的幂, 取不小于 La+LbL_a + L_b 的最小 2 的幂 lim=2klim = 2^k。La+Lb<400000L_a + L_b < 400000,故 lim⩽219=524288lim \leqslant 2^{19} = 524288。

算法流程(5 步)。

  1. 逆序读入两个数位串,把 aia_i、bjb_j 填进复数数组 fafa、fbfb 的实部,虚部置 0。
  2. 计算 lim=2⌈log⁡2(La+Lb)⌉lim = 2^{\lceil \log_2 (L_a+L_b) \rceil},预处理 limlim 长的位反转置换表 rev。
  3. 对 fafa、fbfb 各做一次正向 FFT,得到两组点值。
  4. 逐点相乘 fa[k]←fa[k]⋅fb[k]fa[k] \leftarrow fa[k] \cdot fb[k],再对 fafa 做一次逆变换(IFFT), 逆变换里顺带除以 limlim,得到的就是卷积系数 sks_k。
  5. 从 k=0k = 0 起做十进制进位:cur = round(fa[k]) + carry,写下 cur % 10, carry = cur / 10;进位链走完后剥掉高位多余的零,逆序输出。

为什么迭代式 FFT 而不是递归。 递归版每层要复制数组,lim≈5×105lim \approx 5 \times 10^5 时 内存与常数都更差。迭代版先按位反转换序,然后 len 从 2 倍增到 limlim 逐层做蝶形合并: 每层用单位根 ωlen=e2πi/len\omega_{len} = e^{2\pi i/len}(逆变换取共轭角), 块内维护一个滚动变量 ww 从 11 开始乘 ωlen\omega_{len},就能省掉每个蝶形的幂次计算。

一个实现细节:本题的卷积结果(La+LbL_a + L_b 项)与 limlim 的长度关系是 La+Lb−1⩽limL_a + L_b - 1 \leqslant lim 且 lim<2(La+Lb)lim < 2(L_a+L_b),所以按 i<La+Lbi < L_a + L_b 遍历 结果数组是安全的,最末尾几项 sk=0s_k = 0 不影响正确性(进位阶段它们只会产生 0)。

这个文档的思路可信度说明。 本题素材源自带数据生成脚本(data.py), 说明测试数据是自造的、题面按《信息学奥赛一本通》第一章重建,与官方原题页可能略有差异; 其中第 2 组数据含 00、第 4 组含前导零,都超出了"正整数"的字面描述, 所以上面的实现按数值语义解析输入(0 \times$ 大数 $= 0$,00000001` 当作 11)。

代码

Python 版:

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 07:50
# update_at: 2026-10-08 07:50

import sys

DIGITS_LIMIT = 500000  # 200000 位的乘数、400000 位的积,都要超过 CPython 默认的 4300


def solve() -> None:
    """读入两个大整数并输出乘积:十进制串 → int → 相乘,交给 CPython 的 C 层大整数乘法。"""
    # CPython 3.11+ 默认禁止超过 4300 位的十进制串与 int 互转,这里按数据上界放宽
    sys.set_int_max_str_digits(DIGITS_LIMIT)

    # 输入恰好两个数:直接解包,不用手算偏移,也不用 iter/next 的求值顺序陷阱
    a, b = map(int, sys.stdin.buffer.read().split())
    # 前导零、单独的 "0" 都由 int() 按数值语义吸收,结果直接输出十进制即可
    sys.stdout.write(str(a * b) + "\n")


if __name__ == "__main__":
    solve()

C++ 版(FFT 正解):

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-08 07:50
 * update_at: 2026-10-08 07:50
 */

// 2128 高精度乘法(II)
// 输入两个小于 200000 位的十进制正整数 a、b,输出 a*b。
//
// 做法:把两个数看成以 10 为底的多项式,两数相乘就是多项式乘积(系数卷积),
//       用 FFT 在 O((La+Lb) log(La+Lb)) 内算出卷积,最后从低位到高位统一进位。
// 精度:单个系数最大为 min(La,Lb)*9*9 < 200000*81 ≈ 1.62e7,
//       远小于 double 尾数能精确表示的整数上限 9e15,不会有取整误差。
// 边界:输入可能出现 "0" 或前导零(如 "00000001"),按数值语义解析。
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const double PI = acos(-1.0);
const int MAXN = 1 << 19;  // 524288:不小于 (200000+200000) 的最小 2 的幂

// 手写复数:只用到加、减、乘,避免引入额外头文件依赖
struct Complex {
    double r, i;
    Complex() : r(0.0), i(0.0) {}
    Complex(double _r, double _i) : r(_r), i(_i) {}
    Complex operator+(const Complex &o) const { return Complex(r + o.r, i + o.i); }
    Complex operator-(const Complex &o) const { return Complex(r - o.r, i - o.i); }
    Complex operator*(const Complex &o) const {
        return Complex(r * o.r - i * o.i, r * o.i + i * o.r);
    }
};

Complex fa[MAXN], fb[MAXN];  // 两个多项式的系数(实部存数字,虚部为 0)
int rev[MAXN];               // 位反转置换,三次变换共用同一张表

// 迭代式 FFT:先按 rev 重排,再自底向上做蝶形合并。
// inv = 0 正变换,inv = 1 逆变换(最后除以 n)。
void fft(Complex *a, int n, int inv) {
    for (int i = 0; i < n; ++i) {
        if (i < rev[i]) swap(a[i], a[rev[i]]);
    }
    for (int len = 2; len <= n; len <<= 1) {
        double ang = 2.0 * PI / len * (inv ? -1.0 : 1.0);
        Complex wn(cos(ang), sin(ang));  // 本层的单位根
        for (int i = 0; i < n; i += len) {
            Complex w(1.0, 0.0);
            for (int j = 0; j < len / 2; ++j) {
                Complex u = a[i + j];
                Complex v = a[i + j + len / 2] * w;
                a[i + j] = u + v;
                a[i + j + len / 2] = u - v;
                w = w * wn;
            }
        }
    }
    if (inv) {
        for (int i = 0; i < n; ++i) {
            a[i].r /= n;
            a[i].i /= n;
        }
    }
}

// 去掉前导零;全是零时保留一个 '0',方便统一判断零值
string stripLeadingZeros(const string &s) {
    ll p = 0;
    while (p + 1 < (ll)s.size() && s[p] == '0') ++p;
    return s.substr(p);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string a, b;
    if (!(cin >> a >> b)) return 0;
    a = stripLeadingZeros(a);
    b = stripLeadingZeros(b);

    // 有一边为 0,乘积必为 0(题面说正整数,但数据里有 0 与前导零)
    if (a == "0" || b == "0") {
        printf("0\n");
        return 0;
    }

    ll la = a.size(), lb = b.size();
    int lim = 1;
    while (lim < la + lb) lim <<= 1;  // 不小于结果位数的 2 的幂

    // 倒序填入:下标 i 对应 10^i 位
    for (ll i = 0; i < la; ++i) fa[i] = Complex(a[la - 1 - i] - '0', 0.0);
    for (ll i = 0; i < lb; ++i) fb[i] = Complex(b[lb - 1 - i] - '0', 0.0);

    // 位反转表:rev[i] = rev[i>>1]>>1 再补上最高位
    rev[0] = 0;
    for (int i = 1; i < lim; ++i) {
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? (lim >> 1) : 0);
    }

    fft(fa, lim, 0);
    fft(fb, lim, 0);
    for (int i = 0; i < lim; ++i) fa[i] = fa[i] * fb[i];  // 频域逐点相乘
    fft(fa, lim, 1);                                      // 逆变换回系数

    // 浮点结果带微小误差,必须四舍五入而不是截断
    ll carry = 0;
    string out;
    for (ll i = 0; i < la + lb; ++i) {
        ll cur = (ll)(fa[i].r + 0.5) + carry;
        out.push_back(char('0' + cur % 10));
        carry = cur / 10;
    }
    while (carry > 0) {
        out.push_back(char('0' + carry % 10));
        carry /= 10;
    }
    while (out.size() > 1 && out.back() == '0') out.pop_back();  // 去掉高位多余零

    reverse(out.begin(), out.end());
    printf("%s\n", out.c_str());
    return 0;
}

复杂度

  • 时间:一次长度为 limlim 的 FFT 是 O(limlog⁡lim)O(lim \log lim)。本题共做 3 次变换 (两次正向 + 一次逆向), 3×limlog⁡2lim=3×524288×19≈3.0×1073 \times lim \log_2 lim = 3 \times 524288 \times 19 \approx 3.0 \times 10^7 个蝶形运算;进位与输出是 O(La+Lb)O(L_a + L_b)。总体 O(nlog⁡n)O(n \log n),n=La+Lbn = L_a + L_b。 实测 199999 位 × 199999 位(第 9、10 组数据)在 g++ -O2 下约 60 ms,限时 1000 ms 余量充足。
  • 空间:两个复数数组与 rev 表,各 lim⩽524288lim \leqslant 524288 项, 复数按 16 字节算约 8 MB,加上输出串,总峰值约 20 MB,限 128 MB 内安全。
  • 与 C++ 解法的关系:Python 版不复刻 FFT,而是把乘法直接交给 CPython 的 int ——它内部对超大整数用的是同阶的子二次乘法(Karatsuba 及以上), 并被 sys.set_int_max_str_digits 解除了十进制串转换位数上限。 这是"同阶但常数不同"的落地方式,按本题库规范允许 Python TLE; 若要在 Python 里也做到 O(nlog⁡n)O(n \log n) 且常数可控,需要手写 FFT/NTT, 但以 CPython 的循环开销计,300 万次蝶形运算反而比 C 层大整数乘法更慢, 故短解法选择后者。

总结

  • 换表示换复杂度:sk=∑i+j=kaibjs_k = \sum_{i+j=k} a_i b_j 是卷积,而卷积在频域就是逐点乘法; 系数表示与点值表示之间用单位复根做的变换(FFT)代价是 O(nlog⁡n)O(n \log n)。
  • 精度是 FFT 能用的前提:本题单个卷积和上界只有 1.62×1071.62 \times 10^7, 远在 double 精确整数范围内,这是敢用浮点 FFT 而不上 NTT 的唯一理由; 反过来,如果值域接近 101510^{15},就必须换 NTT。
  • 进位统一在最后做:FFT 求出的是无进位的系数,先放着不进位、最后从低到高扫一遍, 既省掉了每步的同步,也避免了误差在中间步骤被放大。取整必须 round 而非截断。
  • 长度补到 2 的幂:迭代式 FFT 的位反转与层数都要求 limlim 是 2 的幂, 取不小于 La+LbL_a + L_b 的最小幂就够(最坏 2192^{19}),比取 2(La+Lb)2(L_a+L_b) 省一半。
  • 数据是自造的:素材源含 data.py,题面为重建版,且数据里有 00 与前导零, 实现应按数值语义解析而不是按字面的"正整数"假设。