[算法学习]模板-基本数论

---

底层数学与算力降维系统复盘：从暴力死循环到 O(1) 极速查表

在系统学习底层数学 API 之前，我对它的理解只是：

“数学题就是背公式，找素数就是写个 for 循环一直除。”

但真正深入后发现，它其实是一种极限压榨 CPU 吞吐量的降维思想。

这些数学模板的本质是：

用极小的时间复杂度代价（预处理/二进制拆分），
利用数学定理或物理内存，
把 $O(N)$ 甚至 $O(N^2)$ 的死循环压缩成 $O(\log N)$ 乃至 $O(1)$。

理解它的关键，不是背诵干瘪的代码，而是理解：

• 我们在消灭什么重复计算？
• 为什么巨大的指数可以拆分成二进制？
• 为什么应对几十万次的查询不会 TLE（超时）？

---

一、为什么底层数学能优化算力？

我们先看一个找素数的典型暴力结构：

for (int i = 1; i <= n; i++) {
    for (int j = 2; j * j <= a[i]; j++) {
        // 判断 a[i] 能不能被 j 整除
    }
}

这个结构做了什么？

• 每次查询都重新从头算一遍
• 遇到多次重复的数字，依然傻傻地再算一次

但很多数学题中：

• 数据的状态是固定的（比如 7 永远是素数）
• 或者乘法的步骤存在极其严重的冗余

一旦计算步骤具有“高度重复性”和“可拆解性”，我们就可以：

将“计算”转化为“查表”或“位运算”。

---

二、算力降维武器分类

底层数学与防爆破技巧主要分为三个核心模块：

1. 埃氏筛与前缀和（空间换时间，极致查表）
2. 快速幂（二进制切割，指数降维）
3. 游标跳跃（$K+1$ 抽屉原理，斩断冗余遍历）

---

第一部分：埃氏筛与前缀和

---

1️⃣ 思想核心

不要等询问来了再去算，而是在系统启动时：

一次性把所有状态标好，以后永远只查表。

---

2️⃣ 从暴力到优化：完整推理过程

暴力试除法：

每个数字都去循环除以 $2$ 到 $\sqrt{N}$。如果有 $M$ 次查询，时间复杂度直接原地爆炸。

为什么可以优化？

因为合数一定是由较小的素数乘出来的。

只要我们从 2 开始，把每一个素数的所有倍数全部提前标记为合数，那么剩下的，绝对就全是素数。

搭配上前缀和数组，我们可以将区间 $[L, R]$ 之间的素数个数统计压缩到真正的 $O(1)$ 极速查询。

---

3️⃣ 标准模板 (防爆破版)

const int N = 1e6 + 10;
bool st[N];       // st[i]=true 表示是合数
int pre_sum[N];   // 记录素数个数的前缀和

void init_primes(int m) {
    // 1. 系统加电，预处理埃氏筛
    st[0] = st[1] = true; 
    for (long long i = 2; i <= m; ++i) {
        if (st[i]) continue; 
        for (long long j = i + i; j <= m; j += i) {
            st[j] = true;
        }
    }
    
    // 2. 构建前缀和数组 (利用 bool 值直接转化为 1 和 0)
    pre_sum[0] = 0;
    for (int i = 1; i <= m; ++i) {
        pre_sum[i] = pre_sum[i - 1] + (!st[i]); 
    }
}

// 极速查询：O(1) 获取 [L, R] 之间的素数个数
// int cnt = pre_sum[R] - pre_sum[L - 1];

---

第二部分：快速幂魔法

---

1️⃣ 思想核心

求 $A^B \pmod P$。

把十进制的巨大指数 $B$，拆解成计算机底层的二进制。

B = 11 (十进制) -> 1011 (二进制)

---

2️⃣ 从暴力到优化推理

暴力相乘：乘 $B$ 次。时间复杂度 $O(N)$。

但我们可以利用拼图思想：

$$A^{11} = A^8 \times A^2 \times A^1$$

我们只需要让 base 不断自乘（平方升级），然后利用位运算 B & 1 检查当前二进制位是否为 1。如果是，就把这块拼图乘进答案里。

这把几亿次的循环，瞬间降维到了几十次。

---

3️⃣ 标准模板 (全员 long long 防护)

long long fast_power(long long a, long long b, long long p) {
    long long res = 1 % p; 
    long long base = a % p; 
    
    while (b > 0) {   
        if (b & 1) { // 检查最后一位是不是 1
            res = (res * base) % p; 
        }
        base = (base * base) % p; // base 持续自我升级
        b >>= 1; // 抛弃最后一位
    }
    return res;
}

---

第三部分：GCD 与 LCM (公约数/公倍数)

---

1️⃣ 思想核心与数学本质

极其优美的一行递归与一个绝对真理定理。

绝对真理：

$$A \times B = GCD \times LCM$$

只要有了 GCD，LCM 直接通过移项公式 $O(1)$ 得出。

2️⃣ 标准模板

// 极限压缩的三目运算符辗转相除法
long long gcd(long long a, long long b) {
    return b ? gcd(b, a % b) : a;
}

// 防爆破 LCM：永远先除后乘，防止溢出！
long long lcm(long long a, long long b) {
    return (a / gcd(a, b)) * b;
}

---

第四部分：降维打击实战 —— K+1 游标跳跃

（注：源自 AtCoder 真实 TLE 血泪史）

---

1️⃣ 从暴力到优化的极限跨越

要在 30 万个数字里，经历 20 万次“拿走 $K$ 个数字，求剩下数字的最小值”的查询。

暴力遍历：

每次查询都要刷一遍数组（memset）并重新遍历 30 万个球，总运算量 $600$ 亿次 -> 必死 TLE。

$K+1$ 抽屉原理优化：

因为每次最多拿走 $K$ 个球，只要我们事先对全局排好一次序。

每次查询，我们搞一个“游标”从前往后看。就算排在最前面的 $K$ 个最小球全被拿走了，游标最多只需要往后跳 $K$ 步，第 $K+1$ 个球绝对还在袋子里，且绝对是全局最小值！

---

2️⃣ 标准模板结构

// 1. 系统加电：一次性排好序
sort(balls + 1, balls + n + 1);

while (q--) {
    // 2. 局部破坏：拿走 K 个球，打上标记 outball
    
    // 3. 核心降维：游标每次必须从 1 开始！
    int cur_min_idx = 1; 
    while (outball[balls[cur_min_idx].id] == true) {
        cur_min_idx++; // 被拿走了，游标往后跳
    }
    
    // 此时的 balls[cur_min_idx].val 就是最小值！
    
    // 4. 微创复原：千万别用 memset，只把拿走的那 K 个球的标记擦除
}

---

三、暴力 vs 降维 本质区别

业务场景	暴力流 (The Stupid Way)	降维流 (The Hacker Way)	核心工具
素数查询	$O(N \sqrt{N})$ 循环试除	$O(1)$ 极速查表	埃氏筛 + 前缀和
巨大指数	$O(N)$ 乘到内存爆破	$O(\log N)$ 二进制拼图	&1 与 >>=1
动态最小值	每次 memset + $O(N)$ 遍历	全局排序 + 游标跳跃 $K$ 步	结构体排序 + 状态重置

---

四、如何判断是否能用这些降维魔法？

问自己三件事：

1️⃣ 题目是否有大量的重复区间查询？

→ 是，优先考虑预处理建表（前缀和/素数筛）。

2️⃣ 指数是否大到离谱（比如 $10^9$）？

→ 是，无脑套快速幂。

3️⃣ 题目中的动态修改，是否有总量的微小限制（如总操作数 $K$ 很小）？

→ 是，优先考虑全局排序 + 游标局部跳跃，千万别从头暴力遍历。

---

五、底层算力优化的真正的本质

降维打击不是背诵复杂的代码结构。

本质是：

不做任何多余的运算。

暴力是：

无论刚才有没有算过，全当没看见，从头再算一遍。

算力优化是：

• 算过的结果，存在数组里直接查。
• 无关的数字，利用单调性直接跳过。
• 物理的极限，用数学定理直接绕开。

这是一场：

对 CPU 资源的极致榨取。

---

六、我对算力降维的阶段性理解

最开始：

• 觉得只要代码能出正确答案就行。

后来发现：

• 在 10 万级别的数据面前，跑不进 1 秒的正确代码等于废代码。

真正理解后：

• 算法的瓶颈从来不是代码写得多长，而是时间复杂度这堵绝对的物理高墙。

---

七、总结

数学 API（素数/快速幂/GCD）：

用底层规律打破 $O(N)$ 的壁垒。

$K+1$ 游标跳跃：

用提前排序消灭冗余遍历。

两者共同核心：

永远在思考如何“降维”。

---