在信息学竞赛中，有一类题目让无数选手又爱又恨——高精度运算。
爱的是它思路清晰、逻辑简单；恨的是它代码冗长、效率低下、容易出错。当别人用int几行代码解决问题时，你却要为几百位的数字写上百行代码，还要小心翼翼处理进位借位。更让人崩溃的是，辛辛苦苦写完的高精度，往往因为效率问题被卡掉几个测试点，眼睁睁看着分数溜走。
然而，高精度运算并非只有”硬算”这一条路。从基础的压位优化，到进阶的快速傅里叶变换，再到针对特殊场景的定制优化，高精度的优化空间远超你的想象。本文将系统梳理高精度运算的几种优化写法，帮助你在信奥赛场上，让高精度代码真正”起飞”。
一、为什么需要优化高精度？
在深入优化技巧之前，我们先要理解：高精度运算的瓶颈在哪里？
传统的高精度实现，通常是用数组的每一位存储一个十进制数字（0-9）。这种实现方式直观易懂，但效率极低：
- 空间浪费：每个十进制位只存储0-9的数字，而一个
int类型可以存储0-4294967295，利用率极低 - 时间浪费：对于1000位的数字，加法需要循环1000次，乘法需要循环100万次，当位数达到10^5时，O(n²)的复杂度完全不可接受
在NOIP、CSP等竞赛中，高精度题目的数据范围往往设计得恰好让朴素高精度”刚好过不了”——你需要一定的优化才能拿到满分。因此，掌握高精度的优化技巧，是从”会做”到”能过”的关键一步。
二、压位高精度：最简单的质变
压位高精度是高精度优化的入门必修课，也是性价比最高的优化——修改几行代码，效率提升数倍。
2.1 压位的核心思想
传统高精度用1个数组元素存1位十进制数，而压位高精度用1个数组元素存多位十进制数。例如，压4位就是每个数组元素存0-9999的数字，压8位就是每个数组元素存0-99999999的数字。
这样做的好处显而易见：
- 空间减少：位数直接除以压位数，内存占用大幅降低
- 时间减少：循环次数相应减少，加减乘除的速度成倍提升
- 进位处理：进位不再是逢10进1，而是逢
base进1
2.2 压位的实现
压位高精度的实现并不复杂，只需在传统高精度的基础上稍作修改。核心是定义两个常量：
cpp
const int power = 4; // 每次运算的位数，即压几位 const int base = 10000; // 10的power次方，用于进位
cpp
num operator + (const num &p, const num &q) {
num c;
c.a[0] = max(p.a[0], q.a[0]);
for (int i = 1; i <= c.a[0]; ++i) {
c.a[i] += p.a[i] + q.a[i];
c.a[i+1] += c.a[i] / base; // 进位到高位
c.a[i] %= base;
}
if (c.a[ c.a[0]+1 ]) ++c.a[0];
return c;
}
乘法的实现也是类似，只是注意乘积可能较大，需要用long long暂存：
cpp
num operator * (const num &p, const num &q) {
num c;
c.a[0] = p.a[0] + q.a[0] - 1;
for (int i = 1; i <= p.a[0]; ++i)
for (int j = 1; j <= q.a[0]; ++j) {
c.a[i+j-1] += p.a[i] * q.a[j];
c.a[i+j] += c.a[i+j-1] / base;
c.a[i+j-1] %= base;
}
if (c.a[ c.a[0]+1 ]) ++c.a[0];
return c;
}
2.3 压几位最合适？
压位的位数选择需要权衡：压得越多，速度越快，但需要处理更大的进位值，可能溢出。
- 压4位（base=10000）：最保守的选择，加减乘除均可直接用int处理
- 压8位（base=100000000）：乘法中间结果需要用long long，但效率更高
- 压9位（base=10^9）：接近int上限，需要谨慎处理溢出
- 压18位（base=10^18）：用unsigned long long存储，乘法需特殊处理
一般推荐压8位或压9位，用long long存储数组元素，这样在64位环境下既能保证效率，又能避免溢出风险。
三、从O(n²)到O(n log n)：FFT加速乘法
如果说压位优化是”线性提升”，那么快速傅里叶变换（FFT）带来的就是”降维打击”。它将高精度乘法的复杂度从O(n²)降低到O(n log n)，让百万位级别的大数乘法成为可能。
3.1 什么时候需要FFT？
压位优化虽然快，但当数字位数达到10^5以上时，O(n²)的复杂度依然会超时。这时就需要FFT出场了。
- 大整数乘法的位数超过10^4
- 需要多次乘法运算的复杂题目
- 结合二分或快速幂的高精度计算
3.2 FFT的原理简述
FFT加速乘法的核心思想是：将大数乘法转化为多项式乘法，而多项式乘法可以通过FFT在O(n log n)时间内完成。
具体来说：
- 将两个大数看作多项式系数
- 用FFT将多项式从系数表示转换为点值表示
- 在点值表示下直接相乘
- 用逆FFT将结果转回系数表示
- 处理进位
3.3 压位+FFT的组合拳
在实际实现中，FFT通常与压位结合使用，发挥1+1>2的效果。例如在CF464E这道题中，选手采用二进制压位+主席树+FFT的组合，实现了对超大数的高效处理，跑到了全谷最优解。
cpp
// 伪代码示意：压位+FFT的组合 const int B = 50; // 压50位二进制 // 用线段树/主席树维护压位后的大数 // 用FFT加速乘法
需要注意的是，FFT的实现较为复杂，对精度也有一定要求。在竞赛中，如果位数在10^5以内，压8位+优化后的O(n²)算法往往已经足够；只有当位数达到10^6级别，才需要考虑FFT。
四、特殊场景的定制优化
除了通用的压位和FFT，针对特定场景还可以进行定制优化，往往能取得意想不到的效果。
4.1 预处理与分块
以经典的”麦森数”（求2^p-1）为例，朴素高精度每次乘2，循环p次，当p达到几百万时显然不可行。一种巧妙的优化是：
cpp
int x = pow(2, 60); // 每次乘2的60次方
for (int i = 1; i <= n; i += 60) {
for (int j = 500; j >= 1; j--) {
if (n - i + 1 < 60)
a[j] *= pow(2, n - i + 1);
else
a[j] *= x;
}
// 统一处理进位
}
这种批量处理的思路，将p次循环减少到p/60次，效率提升60倍，直接从60分跃升到AC。
4.2 特殊进制的选择
- 二进制压位：当涉及大量2的幂次运算时，二进制压位可以让进位处理变得异常简单
- 10^k进制：最通用，便于输入输出
- 2^k进制：在需要位运算的场景下有奇效
例如在CF464E中，由于边权是2的幂次，采用二进制压位后，每次加法最多产生一次进位，大大简化了处理逻辑。
4.3 高精度除法的优化
- 二分法：用二分查找确定商的每一位，复杂度O(n² log n)
- 牛顿迭代：利用牛顿法加速，但实现复杂
- 结合gcd：在需要约分时，用高精度gcd减少计算量
对于时限较紧的题目，可以结合预估范围来优化二分边界，减少二分次数。
五、实战建议：如何选择优化策略
面对一道高精度题目，如何选择合适的优化策略？这里给出一个决策流程：
第一步：分析数据范围
- 位数≤10^4：压8位足以
- 位数≤10^5：压8位+优化算法（如分块、预处理）
- 位数≥10^6：考虑FFT
第二步：分析运算类型
- 仅有加减：压8位即可，复杂度O(n)
- 有乘法：根据位数选择压位或FFT
- 有除法：考虑二分法+压位
- 有大量幂运算：批量处理+特殊进制
第三步：分析特殊性质
第四步：实现与测试
- 先实现压位版本作为baseline
- 如果不够快，再考虑分块优化
- 最后才考虑FFT等复杂优化
六、代码模板：压8位高精度
最后，给出一个实用的压8位高精度模板，可作为日常训练的起点：
cpp
namespace BigInteger {
typedef long long ll;
const int N = 3005; // 最大位数
const int base = 1e8; // 压8位
const int base_digits = 8; // 8位十进制
struct BigInt {
int a[N], len;
int sign; // 符号位，0正1负
BigInt() { len = 1; sign = 0; memset(a, 0, sizeof(a)); }
// 从字符串构造
BigInt(const char *s) {
memset(a, 0, sizeof(a));
int slen = strlen(s);
int start = 0;
if (s[0] == '-') { sign = 1; start = 1; }
else sign = 0;
len = 1;
int k = 1;
for (int i = slen - 1; i >= start; --i) {
a[len] += k * (s[i] - '0');
k *= 10;
if (k == base) { ++len; k = 1; }
}
}
// 输出
void print() {
if (sign) putchar('-');
printf("%d", a[len]);
for (int i = len - 1; i >= 1; --i)
printf("%08d", a[i]); // 补0到8位
}
// 加法
BigInt operator + (const BigInt &b) const {
if (sign != b.sign) {
// 异号转化为减法
if (sign == 1) return b - (-*this);
else return *this - (-b);
}
BigInt c;
c.len = max(len, b.len);
ll carry = 0;
for (int i = 1; i <= c.len || carry; ++i) {
ll sum = carry;
if (i <= len) sum += a[i];
if (i <= b.len) sum += b.a[i];
c.a[i] = sum % base;
carry = sum / base;
if (i > c.len) c.len = i;
}
c.sign = sign;
return c;
}
// 乘法
BigInt operator * (const BigInt &b) const {
BigInt c;
c.len = len + b.len;
c.sign = sign ^ b.sign;
for (int i = 1; i <= len; ++i) {
ll carry = 0;
for (int j = 1; j <= b.len || carry; ++j) {
ll sum = c.a[i+j-1] + 1LL * a[i] * (j <= b.len ? b.a[j] : 0) + carry;
c.a[i+j-1] = sum % base;
carry = sum / base;
}
}
while (c.len > 1 && !c.a[c.len]) --c.len;
return c;
}
// 负号
BigInt operator - () const {
BigInt c = *this;
if (len > 1 || a[1] != 0) c.sign ^= 1;
return c;
}
};
}
结语
高精度运算，是信息学竞赛中一道绕不过去的坎。它考验的不仅是你对基础算法的理解，更是在有限资源下追求极致效率的工程能力。
从最朴素的逐位计算，到压位优化的”四两拨千斤”，再到FFT的”降维打击”，每一步优化背后，都是对计算机底层原理和算法复杂度的深刻理解。当你能够在不同场景下选择最合适的优化策略，让曾经卡死你的高精度代码飞驰而过时，那种成就感正是信息学竞赛的魅力所在。
希望本文介绍的几种优化写法，能帮助你在信奥之路上，走得更远、飞得更高。记住：高精度不可怕，可怕的是只会一种写法。掌握多种优化手段，你就能在任何高精度题目面前游刃有余。