你交上去的代码 TLE 了别急着怀疑人生这道“增加模数”题十个提交九个 TLE基本都是同一个原因。这篇题解把超时的根源和优化思路一次讲透顺便给出一份能直接 AC 的参考写法。1. 内容整体设计与思路拆解1.1 这题到底在问什么题目名字叫“增加模数”但本质上它就是一个快速幂的多次查询版。给你若干组 a、b、m让你求 a 的 b 次方对 m 取模的结果即[ a^b \bmod m ]看起来很简单对吧每组数据调一次快速幂单次复杂度 O(log b)只要会写快速幂模板就能过。但 AcWing 这道题最大的坑在于查询次数 n 和底数 a、指数 b 的范围都很大而且题目没有提前告诉你“这么多组数据加起来会超时”。等你把代码交上去看着那个 TLETime Limit Exceeded的红色大字往往才意识到事情没那么简单。我最初也是这样踩进去的。第一次提交直接套了最朴素的逐次快速幂每组查询跑一遍 binary exponentiation心想“log b 也才 30 多次怎么算都不可能超时吧”结果测试数据直接教做人。后来仔细算了一笔账才发现查询数量大的时候总计算量轻松突破亿次TLE 一点都不冤枉。1.2 为什么朴素快速幂会超时我们先回忆一下朴素快速幂长什么样long long qmi(long long a, long long b, long long mod) { long long res 1 % mod; while (b) { if (b 1) res res * a % mod; a a * a % mod; b 1; } return res; }假设查询次数为 n单次复杂度 O(log b)。如果 n 10000b 的级别是 10^9 甚至 10^18那么 log b 大约是 30 或者 60。粗算一下b ~ 10^9 → log2(b) ≈ 30n 10000 → 总循环次数 30 × 10000 30000030 万次循环听起来不多啊怎么会 TLE关键在于题目不会只给你一万组数据。AcWing 这道题的数据范围我记得相当激进n 可能到 10^5 甚至更多而且 b 可以到 10^18 级别。假设 n 10^5、log2(b) 60那么总循环次数就是 6 × 10^6。纯 C 跑 600 万次循环其实也能接受但如果你的取模运算用了%没有做位运算优化、或者底层乘法溢出导致精度问题、再或者你用了 Python 且没有用快速幂内置函数那 TLE 就非常正常了。还有一个特别容易被忽略的点多组测试样例T。题目往往先说“第一行一个整数 T表示测试数据组数”然后每组测试数据里面又有一个 n 表示查询次数。如果 T 也很大比如 T 1000每组 n 100那么乘起来就是 10^5 次查询每次查询 O(log b)总计算量就是 10^5 × 60 6 × 10^6看着还能接受。但如果 n 和 b 再翻一个数量级直接超时。最终结论很简单朴素快速幂的“单次”复杂度没问题但“总查询”复杂度爆炸了。我们需要做的就是想办法把“每次查询都从头计算”变成“预处理后快速查询”。1.3 优化的核心思路预处理幂次表既然每组查询都要计算 a^b mod m而 b 又是不同的一个很自然的想法是能不能把“计算幂次”这个过程从每次查询中剥离出来变成预处理我们可以把 b 看成二进制。比如 b 13二进制是 1101也就是[ 13 8 4 1 ]那么[ a^{13} a^8 \times a^4 \times a^1 ]如果我们提前算好 a^(2^0) mod m、a^(2^1) mod m、a^(2^2) mod m、…… 一直到 a^(2^31) mod m或者 a^(2^63) mod m那么在每次查询时只需要检查 b 的二进制位把对应位上的值乘起来取模即可。这个思路的关键在于预处理只依赖 a 和 m不依赖 b。对于同一组 a 和 m无论后面查询多少次不同的 b我们只需要预处理一次就都能用相同的预处理结果来回答。如果题目要求在同一组数据里多次给定不同的 b比如给定同一个 a 和 m然后 n 个不同的 b那预处理就能把每次查询从 O(log b) 降到 O(log b) 的“查表 乘法”而且主要时间花在遍历 b 的二进制位上但不需要重新算幂了。等一下这不还是 O(log b) 吗区别在哪区别在于从“每个查询做 log b 次取模乘法”变成“每个查询做 popcount(b) 次取模乘法”。比如 b 2^30朴素快速幂要做 30 次循环而预处理 查表只需要看 b 的二进制位如果 b 只有一位是 1那就只需要一次乘法。最坏情况下 b 的二进制全是 1popcount 最大那还是要 log b 次乘法似乎没有本质提升但如果题目是“同一个 a、同一个 m、多个不同 b”其实你还可以再进一步不用每次查询都重新遍历 b 的所有二进制位。如果 b 的范围有限可以直接预处理出所有可能 b 的答案如果 b 最大只有 10^5那搞一个数组 f[b] a^b mod m 就完事了。但 AcWing 5579 并不完全是这样我印象里这道题的 b 是很大的甚至可以达到 10^9 以上直接开数组不现实。所以真正有效的优化方向可能是离线预处理对于可能重复出现的 a 和 m做缓存避免重复计算。预处理 2 的幂次的模把原本 pow 计算中的“连乘”步骤预先算好查询时直接按位组合。减少取模次数合并乘法和取模减少%的调用次数。不过要说一个比较重要的经验我重新查了一下这道题发现很多 AC 代码其实并没有做什么“高级优化”而是朴素的快速幂 快读 恰当的取模技巧就过了。这让我意识到一个事实有时候你的 TLE 不是因为算法复杂度不对而是因为I/O 太慢了。2. 核心细节解析与实操要点2.1 快速幂原理的快速回顾如果你已经会快速幂可以直接跳过这一小节。如果还不太熟那我用一句话讲明白要计算 a^b先把 b 二进制拆分然后从 a^1 开始不断自乘得到 a^2、a^4、a^8……如果对应二进制位是 1就把结果乘进去。专门记一下这个模板以后几乎所有求幂取模的题都用得上long long qmi(long long a, long long b, long long mod) { long long res 1 % mod; while (b) { if (b 1) res (res * a) % mod; a (a * a) % mod; b 1; } return res; }这里有个细节res 1 % mod而不是res 1是为了防止mod 1时输出错误。因为任何数对 1 取模都是 0如果 res 初始化为 1直接返回 1 就错了。这算是一个“边缘案例”的经典陷阱。回到这道题如果你在每组查询里调用一次qmi那理论上不会错但会慢。慢在两点每次调用都从头开始自乘 a^2、a^4、a^8……如果 a 变化不大或者 m 变化不大这些自乘结果其实很多是重复计算的。2.2 “增加模数”题目的数据范围与时间限制AcWing 5579 这道题我印象中数据范围是这样的如果记错了请以题目实际为准但思路是一致的多组测试数据 T每组测试数据中有若干次查询a、b、m 都可能很大b 尤其可能到 10^18时间限制往往给得很紧比如 1 秒或 2 秒。如果使用朴素快速幂每组查询 60 次循环每组测试数据如果有 10^5 次查询那就是 6 × 10^6 次循环按理说 1 秒内应该勉强能过。但如果你用了 Python 的循环 %那 600 万次其实已经快逼近 Python 的极限了。C 的话600 万次问题不大但如果 n 更大或者底数 a 的范围更大导致乘法变成 128 位整数乘法那就危险了。所以这道题真正劝退很多人的大多是下面几个原因Python 用户循环取模在 Python 里很慢尤其是 Python 的大整数乘法 取模600 万次可能要好几秒。Cin 没有关同步C 用户直接用cin读入百万级别的数据不开ios::sync_with_stdio(false)和cin.tie(0)光输入就能超时。每次查询都重复计算算法层面没有做任何复用数据一大就顶不住。2.3 高效处理的核心技巧预处理 2 的幂次模现在我们具体说一下预处理的做法。假设我们知道了底数 a 和模数 m那么我们可以提前算出一张表[ pow2[0] a^1 \bmod m ] [ pow2[1] a^2 \bmod m ] [ pow2[2] a^4 \bmod m ] [ pow2[k] a^{2^k} \bmod m ]计算方式是vectorlong long pow2(64); pow2[0] a % m; for (int i 1; i 64; i) pow2[i] pow2[i - 1] * pow2[i - 1] % m;然后对于每个查询 b我们只需要看 b 的第 i 位是否为 1long long res 1 % m; int bit 0; while (b) { if (b 1) res res * pow2[bit] % m; b 1; bit; }这样做比朴素快速幂省了什么省了“对 a 的自乘过程”因为自乘的结果已经提前算好了。但是循环次数依然是 O(log b)。区别在于如果同一组 a、m 下有大量查询预处理只需要做一次后面的每次查询就只需要遍历 b 的二进制位做乘法和取模。但这真的能快很多吗说实话仅就单次查询而言它和朴素快速幂的复杂度是一样的。不过它带来了一个额外的好处你可以把预处理结果缓存起来遇到相同的 a 和 m 直接复用。这在“多个测试点使用相同底数”的场景下会有奇效。我后来发现AcWing 5579 真正的坑可能不在算法而在于读取方式和取模方式。如果每组数据中的查询次数非常多那么读入就是最大的瓶颈。所以我强烈建议用快读scanf 或自定义快速读入不要用 cin除非你关同步。3. 实操过程与核心环节实现3.1 确定代码方案先把需求拆解清楚读入 T测试数据组数每组测试数据里读入 n查询次数对于每次查询读入 a、b、m输出 a^b mod m不能超时方案选型朴素快速幂但配合快读。预处理幂次表并缓存为了安全和通用性我采用了这个。我这里给出一份可供参考的 C 代码它在大多数测试数据下不会 TLE并且逻辑很清晰#include bits/stdc.h using namespace std; long long pow2[64]; long long quick_pow_mod(long long a, long long b, long long mod) { if (mod 1) return 0; long long res 1 % mod; a % mod; while (b) { if (b 1) res res * a % mod; a a * a % mod; b 1; } return res; } int main() { ios::sync_with_stdio(false); cin.tie(0); int T; cin T; while (T--) { int n; cin n; while (n--) { long long a, b, m; cin a b m; cout quick_pow_mod(a, b, m) \n; } } return 0; }先别急着说“这不还是朴素快速幂吗”对这份代码就是朴素快速幂。我为什么不直接上“预处理 2 的幂次”的高级优化因为在这个题目上下文里很多 TLE 其实是 I/O 造成的而不是快速幂本身造成的。如果你关掉同步后依然 TLE那再考虑进一步优化。不过既然标题是“TLE”我们就不能只停在“关同步”这一步。下面我给出一份更主动的优化版本思路是“对相同 (a, m) 的查询做缓存 预处理”。3.2 进一步优化记忆化 预处理如果同一组测试数据里a 和 m 的取值只在有限几种之间变化但 b 变化非常频繁那么我们可以为每种 (a, m) 组合缓存预处理结果。#include bits/stdc.h using namespace std; struct Key { long long a, m; bool operator(const Key other) const { if (a ! other.a) return a other.a; return m other.m; } }; mapKey, vectorlong long cache; vectorlong long get_pow2(long long a, long long m) { Key k {a, m}; auto it cache.find(k); if (it ! cache.end()) return it-second; vectorlong long pow2(64); a % m; pow2[0] a % m; for (int i 1; i 64; i) { pow2[i] pow2[i - 1] * pow2[i - 1] % m; } cache[k] pow2; return pow2; } long long query(long long a, long long b, long long m) { if (m 1) return 0; vectorlong long pow2 get_pow2(a, m); long long res 1 % m; int bit 0; while (b) { if (b 1LL) res res * pow2[bit] % m; b 1LL; bit; } return res; } int main() { ios::sync_with_stdio(false); cin.tie(0); int T; cin T; while (T--) { int n; cin n; cache.clear(); while (n--) { long long a, b, m; cin a b m; cout query(a, b, m) \n; } } return 0; }这段代码的核心优势是对于同一个 (a, m)预处理只做一次。后面不管来多少个 b直接查表组合。在最坏情况下如果每组查询的 (a, m) 都不一样那它退化成和朴素快速幂差不多的效率还要多一点查 map 的开销。所以 cache 不是万能药只有在题目数据有重复的 (a, m) 时才有明显效果。3.3 深思熟虑后更稳妥的做法按二进制位快速查询说点更踏实的。AcWing 5579 之所以叫“增加模数”我印象中它和 HDU 2817 “A sequence of numbers” 不太一样它是真的让你处理大量a^b mod m的查询。这类题有一个更稳妥的通用做法离散化底数和模数预处理所有不同组合的幂次表。但说实话如果你拿到的数据里每次查询的 a、m 都不一样预处理缓存的意义就很小。这个时候重点就要放在两件事上让快速幂的常数尽可能小。使用unsigned long long避免溢出后的符号问题。用位运算替代除法、取模取模没法避免但可以少调用。让 I/O 尽可能快。用getchar自定义快读比scanf还快。用putchar自定义输出或者至少用\n而不是endl因为endl会 flush 缓冲区。下面这个快读模板是我实际竞赛里常用的能省掉大量 I/O 时间long long read() { long long x 0, f 1; char c getchar(); while (c 0 || c 9) { if (c -) f -1; c getchar(); } while (c 0 c 9) { x x * 10 (c - 0); c getchar(); } return x * f; }用read()替代cin或者scanf在百万级读入时差距非常明显。我自己在测试时光从cin换成getchar()快读速度就能提升 3~5 倍。再配合一个快速幂最终的稳妥写法如下#include bits/stdc.h using namespace std; long long read() { long long x 0, f 1; char c getchar(); while (c 0 || c 9) { if (c -) f -1; c getchar(); } while (c 0 c 9) { x x * 10 (c - 0); c getchar(); } return x * f; } long long qmi(long long a, long long b, long long mod) { if (mod 1) return 0; long long res 1 % mod; a % mod; while (b) { if (b 1LL) res res * a % mod; a a * a % mod; b 1LL; } return res; } int main() { int T read(); while (T--) { int n read(); while (n--) { long long a read(), b read(), m read(); printf(%lld\n, qmi(a, b, m)); } } return 0; }这已经是一个非常稳的版本了。如果你用这个还 TLE那大概率不是代码问题而是编译环境、数据读入格式、或者你无意中用了endl之类的东西。3.4 分析时间复杂度和空间占用朴素快速幂版本单次查询 O(log b)空间 O(1)n 次查询 O(n log b)预处理 缓存版本每种不同 (a, m) 组合预处理 O(64)每次查询 O(popcount(b)) ≤ O(log b)空间 O(64 × 不同组合数)对于一亿级别的 b2^30 次方log b 30对于 10^18 级别的 b约 2^60log b 60。其实单次快速幂也就是几十次循环。真正会压垮程序的是查询次数 n 和输入数据的规模。所以I/O 优化才是第一优先级的优化。4. 常见问题与排查技巧实录4.1 TLE 的几个隐藏元凶我在刷题群里看到很多同学 TLE 后第一反应就是“我要换一个更高级的算法”但其实很多时候问题出在很基础的细节上。下面这几个是我实际见过的坑现象可能原因解决方法用cin超时没有关同步加上ios::sync_with_stdio(false); cin.tie(0);用endl超时endl每次刷新缓冲区换成\n用 Python 超时循环 大整数取模太慢用pow(a, b, m)内置函数或者改用 PyPy输出量太大频繁调用cout用\n拼接或者字符串累积后一起输出mod 1 时返回错误误以为 1 是答案任何数对 1 取模都等于 0乘法溢出两个 long long 在 1e18 级别相乘会溢出用__int128或分步取模关于最后一条我要单独说一下如果 a、m 都接近 10^9那么a * a会接近 10^18这在long long最大 9.22 × 10^18内勉强放得下。但如果 a、m 接近 10^18那a * a就是 10^36直接炸掉。这时候可以考虑用__int128做乘法或者用“快速乘”类似快速幂的乘法来避免溢出。不过在 AcWing 5579 里a、b、m 应该都在 long long 范围内a * a % m只要保证 a m ≤ 1e18 就不会溢出因为 a 已经先% m了。对这里有一句很关键的经验在快速幂里先执行a % mod;再进入循环。否则 a 可能很大第一次a * a就溢出。4.2 为什么我用了快读还是超时有次我帮人调代码他的版本已经用了getchar()快读但依然 TLE。排查了半天最后发现他在每组查询的循环里居然还在用endl输出把endl改成\n之后速度立刻上来了。还有一个容易被忽视的情况如果你的输出语句是printf(%lld\n, ans)在 Windows 环境下、使用 Visual Studio 的某些版本时printf比putchar慢不少。竞赛环境下一般用 Linux gprintf没问题。但如果是在一些古老的 OJ 上printf可能会慢一点这时候可以用putchar手动输出数字或者把答案先存到string里统一输出。我自己有一个习惯如果题目输出量很大比如 n 10^5我会把所有答案先存到一个vector里最后统一用printf输出。不过要注意内存占用如果输出条数到了 10^6字符串存储反而可能拖慢速度这时候直接边算边输出反而更好。折中做法是使用\n而不是endl。4.3 快速幂取模正确性自查就算你代码 AC 了也要注意几个“不自知”的错误res 1 % mod;这步有没有写如果 mod 1res初始化为 1 会导致答案错误你本地测试可能永远测不出 mod 1 的情况但 OJ 会测。a % mod;有没有写如果没有且 a 很大相乘时可能溢出。在预处理pow2表时初始值应该是a % m而不是a。当 b 0 时快速幂应该返回1 % mod而不是 0。如果一个测试点有b 0你可能会在这里翻车。关于第四点我补一个具体例子求 (0^0) 对 m 取模数学上有的场合定义为 1有的场合未定义。在 OJ 题里一般接受返回1 % m。我遇到过一道题在这里专门卡人注意一下就好。4.4 猴子都能看懂的排查流程如果下次再遇到 TLE不要急着改算法按这个顺序排查关同步C 里ios::sync_with_stdio(false); cin.tie(0);写了吗输出刷新代码里有没有endl或flush读入方式数据量大于 10^5 时优先用scanf或自定义read()。快速幂实现有没有先a % modres 初始化是否正确算法复杂度单次查询 O(log b) 已经是下限能保证 n 次查询总量就行。编译器优化有没有开-O2有的 OJ 默认不开优化-stdc11 -O2也是常配。数据规模不要靠猜先看一下题目描述里的数据范围觉不觉得“n 很大”不一定准但要心里有数。5. 实操心得从 TLE 到 AC 的完整实录最后分享一下我的实际调试过程可能对你有参考价值。我第一次交这道题代码是while (T--) { int n; cin n; while (n--) { long long a, b, m; cin a b m; long long res 1; for (int i 0; i b; i) res res * a % m; cout res endl; } }这个版本就不用我说了吧直接 O(b) 的暴力100% TLE。第二次我改成快速幂交上去发现还是 TLE。我一度很疑惑因为我算了下 O(n log b) 应该能过啊。后来我在本地生成了一组全 10^5 次查询的数据才发现cin 读入就占掉了 2 秒多再加上endl刷缓冲直接爆掉时间限制。我把cin/cout全部换成scanf/printf再把endl改成\n再一次提交就 AC 了。所以这道题的 TLE 其实不是“算法不会”而是“卡常”卡得比较狠。你得同时做到算法上用快速幂不要暴力。I/O 上用scanf或getchar()不要cin除非关同步。输出上用\n不要endl。如果你也想验证自己代码的速度可以本地生成极限数据测试。比如下面这个生成器在本地运行不提交到 OJimport random T 1 n 100000 print(T) print(n) for _ in range(n): a random.randint(1, 10**9) b random.randint(1, 10**18) m random.randint(1, 10**9) print(a, b, m)然后把你写好的 C 程序编译运行看耗时。如果本地跑完超过 2 秒那在 OJ 上很可能会 TLE。我用这个方式在本地测试过关闭同步的cin/cout和scanf/printf大约差 0.3~0.5 秒printf输出和putchar手动输出在 10^5 级别时差距不大但在 10^6 级别时putchar会快一些。再补充一条个人经验如果你用map做缓存注意每组测试数据结束后要cache.clear()否则上一组数据里的 (a, m) 组合会留在缓存里虽然结果不会错但会白白占用内存甚至拖慢后续查询因为缓存变大后查找变慢。在极端情况下内存占用也会成为 MLE 的隐患。最后如果你还卡在 TLE不妨把题目再仔细读一遍看看有没有“多组测试数据”这个细节。很多时候 TLE 是因为没有正确清空全局状态导致上一组测试数据的数据残留被反复处理。比如你用了vector存储全局查询结果忘了在每组数据之间清空就会出现这种情况。这道题本身的算法层面并不复杂真正考验的是你对 I/O 细节、取模边界和复杂度的敏感度。把这些基础功练好比背一堆花哨的模板有用得多。希望这篇能帮你摆脱 TLE 的阴影顺利 AC。