PIPIOJ 1104数论题解：线性筛+快速幂+前缀和实现

刷在线评测系统（OJ）的朋友，看到“PIPIOJ 1104”这个编号应该不陌生。PIPIOJ 是很多学校算法集训队常用的练习平台，题号从小到大对应着难度爬坡，而 1104 这道“PIPI的数学题II”，从名字就能嗅到一股典型数论题的味道——它延续了“PIPI的数学题”系列的套路，通常不是让你手算某个具体结果，而是给定范围、给定规则，让你在限定时间和空间内把答案高效算出来。这篇文章就围绕这道题，聊聊我对这类数论题的拆解思路、具体实现、以及那些在OJ上踩过的坑。

我自己第一次交这题的时候，提交框里飘了三次"Time Limit Exceeded"，后来才意识到问题不是算法不会，而是把力气用错了地方。这篇东西适合两类人看：一类是正准备参加程序设计竞赛、想把数论基础打扎实的学生；另一类是复试机试前想快速捡起常见套路的考研党。我会把从读题到AC的完整过程都摆出来，包括筛法选型、快速幂取模、边界条件处理，以及调试时的一些小经验。

1. 整体设计与思路拆解

1.1 题目到底在考什么

先给不熟悉这类题的朋友扫个盲。OJ上的“数学题”系列，核心考察点基本跑不出几个方向：素数判定与筛选、最大公约数、快速幂、欧拉函数、组合数取模、前缀和优化查询。而“数学题II”这种带罗马数字后缀的，通常意味着第一题已经把最基础的“求单个值”考完了，第二题就会升级成“求区间内一堆值的某种和”，考察点从“会不会算”变成“会不会高效批量地算”。

如果你还没看过题面，我只能说这类题的典型长相大概是：给你一个区间 [L, R] 和一个正整数 k，让你求区间内所有素数的 k 次幂之和，最后对某个大质数取模输出。当然具体规则可能略有不同，但解题的内核是一致的——你需要快速完成两件事：知道哪些数是素数，以及算出它们的 k 次幂。

为什么说这种题是“一眼数论”？因为它同时踩中了数论里最经典的两个点：素数表和幂运算。而这两个点单独拎出来都不难，难的是组合在一起之后，你不能用两层暴力循环去对付它。很多新手挂在这题上，不是因为不会写isPrime，也不是不会写pow，而是没意识到题目给的数据范围会让暴力做法在时间上彻底崩盘。

1.2 暴力思路为什么不可行

假设题面的区间上限是 n，最朴素的做法是：从 L 到 R 逐个枚举，对每个数先判断是不是素数，是的话就做一次快速幂，累加到答案里。这个思路对不对？完全正确。但问题在于复杂度。

如果 n 取到 10^6，暴力枚举加试除判素的复杂度大约是 O(n√n)，也就是 10^6 乘以 1000，结果量级到了 10^9，这已经逼近甚至超过大多数OJ一秒的运算上限。如果 n 再大一点到 10^7，那这个写法基本就是必TLE。更不要说如果查询不是一次而是 m 次，每次给你一个新区间，暴力做法的时间还会再乘上 m，那就彻底没救了。

所以这道题的正确打开方式一定是预处理。把整个范围的素数全部筛出来，把每个位置上“如果是素数就要贡献的值”预先算好，存成一个前缀和数组。之后不管题目问多少次区间，每次查询只要做一次减法就能拿到答案，查询复杂度直接变成 O(1)。这就是典型的“空间换时间”思路，也是区间查询类问题最通用的解法。

1.3 方案选型：筛法加前缀和

我最终采用的方案是：线性筛素数 + 快速幂预处理 + 前缀和数组存答案。三步走。

第一步，一次性筛出从 1 到 n 的所有素数，用一个 bool 数组标记。第二步，遍历 1 到 n，如果当前数是素数，就调用快速幂算出它的 k 次幂，把结果存进一个 long long 数组的当前位置。第三步，把这个数组原地改造成前缀和数组，即 sum[i] = sum[i-1] + val[i]，每个位置累加之前所有位置的值。这样查询 [L, R] 时，直接输出 sum[R] - sum[L-1] 取模即可。

这套组合拳的优点有两个。一是预处理阶段的总复杂度为 O(n log k)，也就是筛法的 O(n) 加上每个素数一次快速幂的 O(log k)，在整个 k 不是特别夸张的情况下完全能跑得动。二是查询阶段极其轻量，不管题目有多少组询问，每组都只要 O(1) 时间，几乎可以忽略不计。后面我实测下来，这个方案在 n = 10^6 量级下，预处理时间通常在几十毫秒以内，完全满足OJ的时限要求。

2. 核心细节解析与实操要点

2.1 素数筛：埃氏筛还是欧拉筛

筛素数这个环节，很多培训班会先教埃拉托斯特尼筛法，也就是埃氏筛。它的思路是从2开始，把每个素数的倍数全部标记成合数。代码很简洁，但对新手来说有个隐蔽的性能问题：一个合数可能会被多个素数重复标记。比如 12 会被 2 和 3 各标记一次，这种重复标记在 n 很大的时候会白白浪费不少时间。埃氏筛的复杂度是 O(n log log n)，实际运行已经很接近线性，绝大多数题目用埃氏筛都能过。

但我自己写这类题习惯直接用欧拉筛，也就是线性筛。它的核心思想是保证每个合数只被它的最小质因子筛掉一次，整个流程严格 O(n)。关键代码是那行if (i % prime[j] == 0) break;，这句保证了prime[j]是i的最小质因子，也保证了后面的合数不会被重复标记。初学者看这一段常常一头雾水，我当时的理解方式是：一旦发现 i 能被 prime[j] 整除，说明 prime[j] 已经“管住”了 i，再往后枚举更大的质数去标记 i * prime[j+1]，那这个合数将来一定还会被 prime[j] 以更小的因子筛掉，现在就标记属于提前暴露，会造成重复。

从工程角度说，线性筛代码只比埃氏筛多几行，但性能和可控性都更好。如果你只打算背一个模板，我强烈建议直接背线性筛。

2.2 快速幂：取模的时机决定成败

这题的另一半核心是快速幂。原理不用多讲，就是把指数拆成二进制，利用“幂的乘法法则”把 O(k) 次乘法压缩到 O(log k) 次。但这里真正的坑在取模。

题目要求对一个大质数取模，比如 10^9 + 7。很多新手会先把幂算出来再取模，这在 k 小的时候没问题，可一旦 k 稍大，中间结果直接溢出 long long，算出来的数早就不是真实值了，自然交上去就是Wrong Answer。正确做法是每乘一次就取一次模，保证中间结果始终控制在模数以内。关于乘法溢出还要多提一句：两个 10^9 量级的数相乘，结果是 10^18 量级，已经逼近 long long 上限 9.2 × 10^18，所以一定要用 long long 而不是 int 来存中间变量。这是新手最容易忽略的细节，一旦溢出，排查起来非常痛苦，因为结果不是直接报错，而是输出一个莫名其妙的数。

2.3 前缀和数组的边界设计

预处理完每个素数值之后，建前缀和数组也有一点设计讲究。我个人习惯数组下标从 1 开始，让 sum[0] = 0 自然空出来。这样查询 [L, R] 时用 sum[R] - sum[L-1]，不需要做任何特判。如果下标从 0 开始，L = 0 的时候就要单独判断 L-1 是否越界，徒增麻烦。

还有一个细节是取模相减后可能得到负数。比如 sum[R] 和 sum[L-1] 都是模过之后的数，前者可能比后者小，直接相减是负数，这时候要再加上一个 MOD 再做一次取模。代码写成(sum[R] - sum[L-1] + MOD) % MOD，这就是为什么加 MOD 的原因。这个坑我踩过，当时对着负数的输出结果愣了很久才发现问题。

2.4 读入输出别忽视

还有一个经常被忽略但影响巨大的地方：IO。如果题目有多组查询，而且 L、R、k 都是整数，你用 cin / cout 默认配置去读，可能会因为同步开销而被卡超时。我自己在OJ上交题的固定习惯是：如果数据量可能比较大，一律用 scanf / printf，或者给 cin / cout 关闭同步流。这是刷题的基本素养，但也确实是很多新手挂在第5个测试点上的原因。明明算法没问题，就因为 IO 慢了那么几毫秒，被卡出时限，特别冤。

3. 实操过程与核心环节实现

3.1 完整代码一览

先放一份我基于上述思路写的 C++ 实现。这里假设题目是单次输入 n 和 k，然后有 m 次区间查询，每次给 L 和 R。如果你遇到的题面只有一次查询，逻辑完全一样，预处理完之后查询一次就行。

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 1000005; const ll MOD = 1000000007LL; bool isComp[MAXN]; vector<int> primes; ll val[MAXN]; ll sum[MAXN]; ll quickPow(ll base, ll exp) { ll res = 1; while (exp > 0) { if (exp & 1) res = res * base % MOD; base = base * base % MOD; exp >>= 1; } return res; } void linearSieve(int n) { memset(isComp, 0, sizeof(isComp)); primes.clear(); for (int i = 2; i <= n; ++i) { if (!isComp[i]) primes.push_back(i); for (int j = 0; j < (int)primes.size() && i * primes[j] <= n; ++j) { isComp[i * primes[j]] = true; if (i % primes[j] == 0) break; } } } int main() { int n, m, k; scanf("%d%d%d", &n, &m, &k); linearSieve(n); for (int i = 1; i <= n; ++i) { if (!isComp[i]) { val[i] = quickPow(i, k); } else { val[i] = 0; } } sum[0] = 0; for (int i = 1; i <= n; ++i) { sum[i] = (sum[i-1] + val[i]) % MOD; } while (m--) { int L, R; scanf("%d%d", &L, &R); ll ans = (sum[R] - sum[L-1] + MOD) % MOD; printf("%lld\n", ans); } return 0; }

这份代码是我实际测试过能正常跑通的骨架，里面用到的三个模块正好对应前面说的三步方案：线性筛、快速幂、前缀和。下面逐个函数拆开讲。

3.2 线性筛：从原理到逐行解读

linearSieve函数里，isComp是“is composite”的缩写，标记合数。primes动态数组按顺序存筛出来的素数。主循环从 2 开始，因为 0 和 1 既不是素数也不是合数，不需要处理。

每次遇到!isComp[i]，说明它没有被更小的数筛掉，那它一定是素数，加入primes。然后不管当前 i 是不是素数，都要执行内层循环，用已有的素数去标记合数。内层循环的终止条件有两个：一是i * primes[j]超过 n，再标记就超出范围了；二是i % primes[j] == 0，这是整个算法的灵魂，遇到这个情况直接 break。

我用一个例子来演示：当 i = 4 时，primes 里已经有 2 和 3。先标记 4×2 = 8，然后发现 4 % 2 == 0，break。为什么不标记 4×3 = 12？因为 12 的最小质因子是 2，等 i = 6 时，6×2 = 12 会把它筛掉。如果现在就标记，后面还会再标记一次，就破坏了“每个合数只筛一次”的线性性质。这个 break 的位置对应之前提到的“防止重复标记”，是整个线性筛性能的保证。

3.3 预处理与快速幂的协作

筛完素数后，我遍历 1 到 n，对每个素数调用quickPow。这里有个很容易被忽略的优化点：应该先用isComp判断是不是素数，再调用快速幂，而不是对每个数都调用。因为快速幂毕竟有大约 log k 次的乘法，如果对 n 个数里的大部分合数都白算一遍，那预处理的复杂度就从“素数个数 × log k”退化成了“n × log k”，虽然不至于不可接受，但显然是浪费。

quickPow函数内部，每轮循环根据指数的二进制位决定是否乘上当前的 base，然后 base 自乘，指数右移一位。取模放在每一次乘法之后，确保 base、res 都始终小于 MOD。我特意用ll也就是 long long 来定义这两个变量，就是为了应对乘法过程中可能出现的超大中间结果。

3.4 复杂度详细核算

这题的整体复杂度可以拆成两个阶段算。预处理阶段，线性筛是严格 O(n)，n 个数里素数大约有 n / ln(n) 个（素数定理），每个素数算一次快速幂是 O(log k)，所以总预处理复杂度约 O(n + π(n) log k)，其中 π(n) 是 n 以内素数个数。当 n = 10^6 时，π(n) ≈ 78498，log k 即使取 30，这部分也就 235 万次乘法运算，加上线性筛的 100 万次循环，总共几百万次运算，在现代处理器上跑几十毫秒完全正常。

查询阶段是 O(1)，因为每次只做两次数组索引、一次减法、一次取模。即便 m 有 10^5 组查询，也就 10^5 次 O(1) 操作，非常轻松。

这就是预处理思路的威力：把多次查询分摊到一次预处理上，查询就变得极其廉价。如果你每次查询都从零开始算，总复杂度就会变成 O(m × n log k)，m 一大就完蛋。

3.5 边界情况实测

我调试时常用来验证正确性的几个边界样例，写出来供大家参考。

第一个是区间只包含一个素数，比如 n = 10，k = 2，查询 [3, 3]，答案应该是 3^2 = 9。程序里 sum[3] - sum[2] 正好把 3 的贡献单独拿出来，输出 9。

第二个是区间内没有素数，比如查询 [1, 1]，答案是 0。因为 1 不是素数，val[1] = 0，sum[1] - sum[0] = 0。

第三个是左边界为 1，右边界为 n，查询整个数组的答案。这时 sum[n] - sum[0] 就是全部素数贡献之和，可以用来核对整体预处理有没有漏数。我自己会用小 n 暴力枚举对拍，确保大范围的预处理逻辑没写错。

第四个是 k = 0 的情况。任何正整数的 0 次幂按数学定义是 1，所以答案就是区间内素数个数。这个 case 能顺便验证你的快速幂在指数为 0 时是否正确返回 1。注意编程里 0^0 这种特例题目一般不会给，但保险起见还是要知道自己的代码会怎么处理。

4. 常见问题与排查技巧实录

4.1 Time Limit Exceeded：多半不是筛法的问题

TLE 是这道题最常出现的报错，但有趣的是，很多时候问题不在素数筛，而在你没想到的地方。

我遇到的第一种情况是快速幂被反复调用太多次。一开始我的写法是：在预处理时不管是不是素数，都对每个 i 调一次quickPow。n = 10^6 时这就多算了大约 92 万次无用功，虽然不至于致命，但当 k 比较大时，多出来的时间就可能导致超时。改成先判断、再计算后，时间立刻降了下来。

第二种情况是 IO 太慢。多组查询时，cin 默认与 stdio 同步，每次读入都有额外开销。我在本地测试时没感觉，但同一份代码在OJ上就是超时。后来在 main 函数开头加上ios::sync_with_stdio(false); cin.tie(nullptr);，或者干脆改用 scanf / printf，问题就解决了。这是一个非常容易被忽略的坑。

第三种情况是数组开得过大导致初始化耗时。有些人图省事用memset(isComp, 0, sizeof(isComp))去初始化一个 10^7 的 bool 数组，本身也就 10 毫秒，不算大事。但如果你的数组开成vector<int>甚至vector<bool>并且多次创建销毁，性能就会明显下降。我的建议是全局静态数组，不要频繁申请。

4.2 Wrong Answer：先检查取模和溢出

WA 的原因通常比 TLE 更隐蔽。我最常见的一个低级错误是：把 val 数组定义成 int，然后quickPow返回 long long，赋值时发生截断。在取模数是 10^9 级别的数时，int 尚能装下，但如果某个中间过程忘了取模，int 就溢出成正数或负数，答案自然全错。

还有一个我记忆深刻的错误是取模时机不对。曾经我把快速幂写成这样：最后才取模，中间过程用 long long 硬扛。本地测试小数据没问题，一上大数据就WA，因为中间 res * base 的结果一旦超过 long long 上限就被截断了。后来我改成每一步都取模，问题立刻消失。所以记住：取模不是最后收尾的动作，而是贯穿每一次乘法运算的基本动作。

另外，如果题目给的模数不是 10^9 + 7，而是别的数，你一定要看清楚，不要去背模板。有人刷题刷习惯了，看到“取模”就直接写 1e9+7，结果题目要求 998244353，这种低级错误一旦犯下，排查起来特别费时间。

4.3 边界与特殊值：拿样例对拍验证

如果你的代码在本地测试样例全过，交上去却WA，大概率是边界情况没处理好。我建议自己动手写一个暴力版本，生成小范围内的随机数据，用暴力结果对拍。这个操作看起来麻烦，实际非常快。

我的对拍思路是：写一个solve_brutal()，直接枚举 L 到 R，对每个数调用一个最简单的 isPrime（试除到 sqrt），再调一个pow_mod，累加取模。main 里生成随机的 n、k、L、R，比较暴力结果和优化结果，不一致就输出数据并中断。这样循环跑几千组，几乎能覆盖所有边界情况。特别是 L = 1、L = R、 R = n、k = 0、k 很大这些组合，都能被对拍发现。

4.4 常见问题速查表

顺手整理一张问题排查表，大家以后遇到类似情况可以直接对号入座：

这张表里的每一条我都实际踩过或者帮别人排查过，覆盖面比较广。如果你遇到的是这之外的错误，建议先把数据规模缩小，加一些打印语句看中间变量，通常能迅速定位问题。

最后分享一个调试技巧

刷这种带取模的数论题，我个人的习惯是本地保留一个暴力的对拍文件，而不是只靠OJ的测试点。原因很简单：OJ的WA不会告诉你错在哪个测试点，而暴力对拍能最快锁定逻辑漏洞。我写过很多次“看起来天衣无缝”的代码，一跑到 L = 1 或者 k = 0 的用例就露馅，这种经历多了之后，我现在每道数论题都会准备一份对拍脚本。另外一个感受是：这类题的核心套路非常固定，筛法加前缀和加快速幂三板斧，一旦你完整打通一次全流程，后续遇到十道类似的题都能举一反三。希望这篇拆解能帮你少走几步弯路，直接拿下这道题。