某年区域赛上有道题名字就叫 Easy Problem。开题五分钟内队伍里至少三个人觉得这题是签到题半个小时后才发现它把莫比乌斯函数、欧拉降幂和一堆边界细节叠在一起签到不了硬刚反而伤士气。后来我复盘时发现这题的价值恰恰在于它把两个看起来很理论的板子放在一个很实际的幂和场景里。这篇文章就围绕这道题把题面怎么拆、莫比乌斯反演怎么落地、欧拉降幂怎么避开坑以及完整 C 实现一起交代清楚。1. 把“Easy Problem”翻译成人话题面、约束与目标1.1 一个典型的原题形式这类题不会把难度写在脸上它只会给你一个看起来人畜无害的式子。按我当时做题的经验题面大概率可以归纳成下面的模型给定正整数 (n)、超大指数 (k) 和模数 (MOD)求[ \sum_{i1}^{n} [\gcd(i,n)1] \cdot i^k \pmod {MOD} ]其中 (MOD) 不保证是质数(k) 可以大到 (10^{18}) 甚至更高(n) 通常控制在 (10^5 \sim 10^6) 量级。这个形式不是原题的完整官方表述但数论题只要出现“互质”“幂和”“大指数”三个关键词最后几乎都会被化简成这个骨架。理解了骨架不管官方题面怎么换皮你都能认出它是同一道题。1.2 为什么第一眼看起来反常第一次看到这种题很多人直接想上费马小定理(i^k \bmod p) 不是可以用 (k \bmod (p-1)) 降幂吗问题在于费马小定理有个严格前提模数必须是质数而且底数不能是模数的倍数。官方题面不会那么好心给你一个质数模数它可能给你 (MOD 20250101) 这种随便拼出来的数。这个时候你需要的是欧拉定理的推广版也就是广义欧拉降幂。另一件反常的事是题目名字叫 Easy Problem。真正比赛里题目名带 Easy 的往往不是签到题而是“想清楚就简单想不清楚就卡死”的题。它考的其实是谁能在五到十分钟内把莫比乌斯反演公式写对、把欧拉降幂的边界处理好然后直接套线性筛和快速幂。1.3 这套东西的影响范围有多广说句实话这个题目模型在数论题里的出镜率非常高。把 (\gcd(i,n)1) 换成 (\gcd(i,j)1)把 (i^k) 换成 (\mu(i)\cdot i^k)甚至把求和上界 (n) 换成 (\lfloor n/d\rfloor) 的整除分块核心套路完全不变。弄懂这道 Easy Problem等于一次性打通了“互质幂和”这一类问题的通用解法。2. 莫比乌斯函数在这里干了什么2.1 gcd 判定标准套路反演我们要处理的第一个难点是条件 ([\gcd(i,n)1])。方括号在这类题里是艾弗森约定里面成立记 1不成立记 0。直接用 gcd 跑一遍复杂度是 (O(n\log n))n 到 (10^6) 也许还能接受但 k 到 (10^{18}) 后你会发现还要求 (n) 次快速幂常数直接爆炸。更关键的是官方想要你学会的东西不是暴力而是用莫比乌斯函数把 gcd 条件拆掉。核心公式只有一个[ [\gcd(i,n)1] \sum_{d \mid \gcd(i,n)} \mu(d) ]理解起来也不难莫比乌斯函数 (\mu(d)) 是“平方因子检测器”。当 (\gcd(i,n)) 等于 1 时唯一整除它的 d 只有 1右边只剩 (\mu(1)1)当 (\gcd(i,n)1) 时这个和式会利用莫比乌斯函数的正交性自动变成 0。2.2 推导过程一步一步来把上面的恒等式代进原式[ \sum_{i1}^{n} [\gcd(i,n)1] i^k \sum_{i1}^{n} i^k \sum_{d\mid \gcd(i,n)} \mu(d) ]然后交换求和顺序。(d \mid \gcd(i,n)) 等价于 (d \mid i) 且 (d \mid n)。所以先枚举 (n) 的约数 (d)再枚举 (d) 的倍数 (i)[ \sum_{d\mid n} \mu(d) \sum_{i1}^{n/d} (i d)^k ]把 ((id)^k) 拆成 (d^k \cdot i^k)[ \sum_{d\mid n} \mu(d)\cdot d^k \cdot \sum_{i1}^{n/d} i^k ]如果记[ S(x)\sum_{i1}^{x} i^k ]那么答案就是[ \sum_{d\mid n} \mu(d)\cdot d^k \cdot S(\lfloor n/d\rfloor) ]到这里“互质”这个条件已经彻底消失了。剩下的工作非常机械筛出 (\mu(d))预处理 (S(x))然后枚举 (n) 的约数。2.3 从公式到代码筛 (\mu) 的工程细节(\mu(1)1)这是很多人写线性筛时漏掉的一行。漏掉以后 (d1) 这一项直接算错后面的整体答案也会错而且样例可能还看不出问题。线性筛莫比乌斯函数的标准写法是质数 (p) 的 (\mu(p)-1)如果 (i) 被质数 (p) 整除那么 (i\cdot p) 含有平方因子(\mu(i\cdot p)0)否则 (\mu(i\cdot p)-\mu(i))。我在实现时习惯把素数列表和 vis 数组都放在全局避免递归传递带来的麻烦。MAXN 要根据 (n) 的上限调如果题目说 (n \le 10^6)数组就开 (10^65)不要因为这个细节在赛场上 RE。3. 欧拉降幂在哪儿用、怎么用3.1 朴素快速幂的问题假设 (k10^{18})你不可能真的连续乘 (10^{18}) 次。最简单的优化是快速幂(O(\log k)) 完成一次 (i^k)。但这里有个陷阱直接快速幂虽然时间能接受数学上却不严谨因为你是在拿一个巨大的指数直接参与乘法取模中间结果虽然不会溢出但实际上做了太多无意义的乘法。我们需要先把 (k) 降下来让快速幂里的指数变小这样常数小代码也更稳。3.2 广义欧拉降幂公式的正确打开方式对于模数 (MOD)设 (\varphi(MOD)) 是它的欧拉函数。当指数 (b \ge \varphi(MOD)) 时有[ a^b \equiv a^{b \bmod \varphi(MOD) \varphi(MOD)} \pmod {MOD} ]注意这个版本对任意整数 (a) 都成立不要求 (a) 与 (MOD) 互质。如果只取 (b \bmod \varphi(MOD)) 而不加 (\varphi(MOD))在底数与模数不互质的时候会出错。举个例子(MOD4)(\varphi(4)2)计算 (2^2 \bmod 4)。正确结果是 0。如果按费马小定理的思维写成 (2^{2 \bmod 2}2^01)结果就错了。正确写法是[ 2^{2 \bmod 2 2} 2^{2} 0 ]所以降幂时不要嫌加一个 (\varphi(MOD)) 麻烦这个加号是保命的。3.3 预计算 (i^k) 时的降幂版本在原题中我们要计算所有 (i^k) 的模 (MOD) 值。这里可以统一先把指数降一次[ ek k \ge \varphi(MOD) \ ?\ k \bmod \varphi(MOD) \varphi(MOD) : k ]然后对每个 i 计算mod_pow(i, ek, MOD)。为什么可以统一降因为降幂公式只依赖指数 (k) 和 (\varphi(MOD))不依赖底数 i。这个结论很多人不敢用总觉得底数不互质会出事。放心用上面带加号的版本就是处理这种情况的。另外枚举约数 d 时还要计算 (d^k)。因为用的是同一个 (k) 和同一个模数所以直接用同一个ek再快速幂一次即可不需要每个约数重新判断一次边界。4. 完整实现与复杂度分析4.1 C17 参考代码下面这段代码就是按 (n \le 10^6)、(k \le 10^{18})、(MOD \le 10^9) 的常见约束写的。乘法部分用了__int128避免两个 long long 相乘溢出。#include bits/stdc.h using namespace std; using int64 long long; int64 mod_pow(int64 a, int64 e, int64 mod) { int64 r 1 % mod; while (e 0) { if (e 1) r (int64)((__int128)r * a % mod); a (int64)((__int128)a * a % mod); e 1; } return r; } int64 get_phi(int64 x) { int64 ans x; for (int64 p 2; 1LL * p * p x; p) { if (x % p 0) { while (x % p 0) x / p; ans ans / p * (p - 1); } } if (x 1) ans ans / x * (x - 1); return ans; } int64 reduce_exp(int64 e, int64 phi) { return e phi ? e : e % phi phi; } const int MAXN 1000000 5; vectorint primes; int mu[MAXN]; bool vis[MAXN]; void sieve_mu(int n) { mu[1] 1; for (int i 2; i n; i) { if (!vis[i]) { primes.push_back(i); mu[i] -1; } for (int p : primes) { if (1LL * i * p n) break; vis[i * p] true; if (i % p 0) { mu[i * p] 0; break; } else { mu[i * p] -mu[i]; } } } } int main() { long long n, k, MOD; cin n k MOD; if (MOD 1) { cout 0 \n; return 0; } sieve_mu((int)n); long long phiM get_phi(MOD); long long ek reduce_exp(k, phiM); vectorlong long pw(n 1), pre(n 1, 0); for (int i 1; i n; i) { pw[i] mod_pow(i, ek, MOD); pre[i] (pre[i - 1] pw[i]) % MOD; } long long ans 0; for (int d 1; 1LL * d * d n; d) { if (n % d ! 0) continue; int dd d; for (int step 0; step 2; step) { if (step 1) { if (d n / d) break; dd n / d; } if (mu[dd] 0) continue; long long dk mod_pow(dd, ek, MOD); long long term dk * pre[n / dd] % MOD; if (mu[dd] 1) ans (ans term) % MOD; else ans (ans - term MOD) % MOD; } } cout ans \n; return 0; }4.2 手把手拆解代码流程第一步读入 (n,k,MOD)。如果 (MOD1)所有数模 1 都是 0直接输出 0这一步省去后面所有计算。第二步线性筛 (\mu) 到 (n)。注意 (\mu[1]1) 一定不能漏。第三步计算 (\varphi(MOD)) 并统一降指数得到ek。这里用get_phi做质因数分解复杂度 (O(\sqrt{MOD}))对 (10^9) 级别的模数完全够用。第四步预处理pw[i]和前缀和pre[i]。pre[x]就是公式里的 (S(x))。第五步枚举 (n) 的所有约数。约数成对出现只用枚举到 (\sqrt{n})每找到一个 d同时处理 d 和 n/d注意平方约数去重。第六步根据 (\mu(d)) 的正负决定加还是减。如果 (\mu(d)0) 就直接跳过。4.3 复杂度与极端数据表现整体复杂度是线性筛(O(n))计算欧拉函数(O(\sqrt{MOD}))预处理幂(O(n \log k))枚举约数(O(\sqrt n \log k))主要瓶颈在mod_pow做了 (n) 次。在 (n10^6)、(k10^{18}) 时log k大约 60总操作量六千万左右。加点常数优化在区域赛时限两秒内能过。如果 n 到 (10^7)这题就得换线性筛求幂的优化做法了但一般 Easy Problem 不会给那么大的 n。5. 实战踩坑与调试技巧5.1 最容易错的三个地方第一个坑是 (\mu(1))。忘了设 (\mu(1)1)公式里 (d1) 这一项会变成 0答案少一大块。这种错非常隐蔽因为很多小样例里其他约数项会部分抵消样例可能恰好能过。第二个坑是欧拉降幂只取余不加 (\varphi(MOD))。只有模数是质数且底数不是模数倍数时才能直接用 (k \bmod (MOD-1))。只要模数是任意的见到大指数就老老实实用广义欧拉降幂。第三个坑是约数枚举重复。(d6) 和 (n/d6) 在 (n36) 时是同一个约数如果循环里不判断直接处理两遍结果会重复。代码里用d n / d判断一次这个细节必须写对。5.2 用暴力解法对拍我这人写数论题从来不敢直接交一定先写一个 (O(n\log n)) 的暴力做对拍。暴力代码很短long long brute(long long n, long long k, long long MOD) { long long ans 0; for (long long i 1; i n; i) { if (std::gcd(i, n) 1) { ans (ans mod_pow(i, k, MOD)) % MOD; } } return ans; }对拍时随机生成 (n \le 1000)(k \le 10^{18})(MOD) 在 (2 \sim 1000) 之间乱取让奇偶、平方数、质数、合数都出现。跑几十组随机数据如果全对基本可以放心交。5.3 现场调题的真实经历我在实际写这题时遇到过一种很恶心的情况小数据全对一到 (n10^6) 就 WA。最后发现是vis数组开小了线性筛访问越界把mu的值覆盖了。这个问题在本地不报错但交上去结果就是飘的。所以提醒一句线性筛的数组上限一定要比题目给的 (n) 大最好大 5 以上。另外所有涉及乘法的地方都要留心溢出。比赛环境如果是 64 位 Linuxlong long 乘 long long 本身不会崩但一旦溢出WA 得莫名其妙。用__int128中转一下是成本最低的安全措施。6. 变式与扩展换一个外壳还是同一个内核6.1 变式一gcd 的另一侧变成任意数有些题会写成[ \sum_{i1}^{n} [\gcd(i,m)1] \cdot i^k ]这时反演公式变成枚举 (d \mid m) 且 (d \le n)[ \sum_{d\mid m} \mu(d)\cdot d^k \cdot S(\lfloor n/d\rfloor) ]本质上还是同一套东西只是约数枚举对象从 (n) 变成了 (m)。如果 (m) 也很大可以先对 (m) 做质因数分解再用 DFS 生成约数。比赛里经常这么考提前准备好会快很多。6.2 变式二把幂指数从常数变成函数如果题目改成[ \sum_{i1}^{n} [\gcd(i,n)1] \cdot i^{f(i)} ]那就不能统一降指数了因为每个底数的指数不同。你需要对每个 i 分别判断 (f(i)) 和 (\varphi(MOD)) 的大小。复杂度会上升但核心思路没变指数大就降幂降完再快速幂。6.3 变式三莫比乌斯函数与欧拉函数的对偶关系还有一个很有意思的扩展利用[ \varphi(x) \sum_{d\mid x} \mu(d)\cdot \frac{x}{d} ]可以把某些与 (\varphi) 有关的求和也转化成莫比乌斯反演的形式。比如求 (\sum_{i1}^{n} \varphi(i))用杜教筛能进一步优化到 (O(n^{2/3}))。虽然 Easy Problem 用不到但理解了这个对偶关系以后再看到 (\varphi) 和 (\mu) 同时出现就不会慌。6.4 什么时候才配叫 Easy最后说点心得。这种题在赛场上配不配叫 Easy完全取决于你对两个板子的熟练度。如果你能把莫比乌斯反演公式默写出来能把广义欧拉降幂的加号写对那它确实就是一道快速拿分的题如果你还在纠结 (MOD) 不互质能不能用费马小定理那它就会吃掉你一整场的时间。我的建议是平时把“互质判断 幂和 大指数”这一套模板练到闭眼能写。上了赛场看到类似关键词先圈出来再在草稿纸上把反演公式推一遍确认边界然后直接敲代码。这题真正考的不是智商而是你有没有把数论基础打扎实。