刷在线评测系统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[j1]那这个合数将来一定还会被 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]; vectorint 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 0break。为什么不标记 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) ≈ 78498log k 即使取 30这部分也就 235 万次乘法运算加上线性筛的 100 万次循环总共几百万次运算在现代处理器上跑几十毫秒完全正常。查询阶段是 O(1)因为每次只做两次数组索引、一次减法、一次取模。即便 m 有 10^5 组查询也就 10^5 次 O(1) 操作非常轻松。这就是预处理思路的威力把多次查询分摊到一次预处理上查询就变得极其廉价。如果你每次查询都从零开始算总复杂度就会变成 O(m × n log k)m 一大就完蛋。3.5 边界情况实测我调试时常用来验证正确性的几个边界样例写出来供大家参考。第一个是区间只包含一个素数比如 n 10k 2查询 [3, 3]答案应该是 3^2 9。程序里 sum[3] - sum[2] 正好把 3 的贡献单独拿出来输出 9。第二个是区间内没有素数比如查询 [1, 1]答案是 0。因为 1 不是素数val[1] 0sum[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 毫秒不算大事。但如果你的数组开成vectorint甚至vectorbool并且多次创建销毁性能就会明显下降。我的建议是全局静态数组不要频繁申请。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而是别的数你一定要看清楚不要去背模板。有人刷题刷习惯了看到“取模”就直接写 1e97结果题目要求 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 常见问题速查表顺手整理一张问题排查表大家以后遇到类似情况可以直接对号入座症状可能原因处理方式TLE对合数也调了快速幂增加素数判断后再计算TLEcin/cout 同步开销关同步流或改用 scanf/printfTLE每次查询现算没做前缀和改成预处理前缀和WA中间变量用 int 导致溢出全部换成 long longWA最后才取模中间结果溢出乘法后立即取模WA前缀和相减出负数加 MOD 后再取模WA模数写错检查题面要求的模数WAL1 时 left-1 越界保证 sum[0]0这张表里的每一条我都实际踩过或者帮别人排查过覆盖面比较广。如果你遇到的是这之外的错误建议先把数据规模缩小加一些打印语句看中间变量通常能迅速定位问题。最后分享一个调试技巧刷这种带取模的数论题我个人的习惯是本地保留一个暴力的对拍文件而不是只靠OJ的测试点。原因很简单OJ的WA不会告诉你错在哪个测试点而暴力对拍能最快锁定逻辑漏洞。我写过很多次“看起来天衣无缝”的代码一跑到 L 1 或者 k 0 的用例就露馅这种经历多了之后我现在每道数论题都会准备一份对拍脚本。另外一个感受是这类题的核心套路非常固定筛法加前缀和加快速幂三板斧一旦你完整打通一次全流程后续遇到十道类似的题都能举一反三。希望这篇拆解能帮你少走几步弯路直接拿下这道题。