积性函数一说数论函数, 我个人认为积性函数这个叫法更好对于一个函数 ()f(x), 如果满足对于任意的 $(a, b) | (,)1,∈,∈gcd(a,b)1,a∈Z,b∈Z, ()()()f(ab)f(a)f(b), 那么称这个函数为积性函数(数论函数)特别地, 如果对于所有的 (,)∣∈,∈(a,b)∣a∈Z,b∈Z 都有 ()()()f(ab)f(a)f(b) 的话, 函数 f 被称为完全积性函数(完全数论函数)二者区别在于是否要求两整数互质常见的积性函数常数函数:1()11(n)1 (完全积性函数)单位函数:()[1]ε(n)[n1][1] (完全积性函数)恒等函数:()idk​(n)nk, 这里通常所说的恒等函数当 k 取 11, 即 1id1​, 一般记作 id (完全积性函数)除数函数:()∑∣σk​(n)d∣n∑​dk, 通常我们把 1()σ1​(n) 记作 ()σ(n) 或者 ()d(n), 实际意义是 n 的因数和欧拉函数:()∑1[(,)1]φ(n)i1∑n​[gcd(i,n)1], 即统计小于等于 n 的数中与 n 互质的数的个数莫比乌斯函数:简单说来: 当 n 等于 11 时, ()1μ(n)1; 否则, 当 n 的素数分解中有非一次的素因子时 ()0μ(n)0; 否则, 当 n 有奇数个素因子时, ()−1μ(n)−1; 否则, ()1μ(n)1. 形式化地(){1,10, 有平方素因子(−1),12⋯ 个不同素因子μ(n)⎩⎨⎧​1,0,(−1)k,​n1n 有平方素因子np1​p2​⋯pk​k 个不同素因子​推荐读者自己证明所有的积性函数的 积性狄利克雷卷积对于积性函数 f 和 g, 它们的卷积 ∗f∗g 满足这样一个关系式:(∗)()∑∣()()(f∗g)(n)d∣n∑​f(n)g(dn​)这里有一个良好的性质, 因为因数是成对出现的, 所以积性函数卷积显然满足交换律(当然卷积本身就满足交换律), 也就是说我们有(∗)()∑∣()()∑∣()()(f∗g)(n)d∣n∑​f(n)g(dn​)d∣n∑​g(n)f(dn​)莫比乌斯反演莫比乌斯反演就是利用莫比乌斯函数和狄利克雷卷积将一些难以直接计算的量转化为便于计算的量从而降低复杂度最常用的是下列恒等式∑∣()[1]()d∣n∑​μ(d)[n1]ε(n)Proof根据狄利克雷卷积, 我们还可以知道 1∗ε1∗μ以这一个最常见的莫比乌斯反演作为例子, 读者理解后应当可以推出大多其它的反演式子求解莫比乌斯函数根据定义我们显然可以枚举出来质因数然后 check, 是 ()O(n​) 的, 但当我们要求出很多数的莫比乌斯函数的时候这个复杂度就有些难以接受了为了解决这个问题, 我们来思考如何确定 n 的莫比乌斯函数的取值, 因为这是一个积性函数, 且对于一个质数 p, ()μ(p) 一定等于 −1−1. 所以当 n 为合数时, 我们可以枚举小于 n 的质数 p, 然后分为两类:∣p∣n, 这个时候的 ()μ(pn) 一定含有一个 2p2 的因子项, 所以 ()0μ(pn)0∤p∤n, 这个时候 ()μ(pn) 相当于在 n 的基础上添加了一个新的因子 p, 由积性函数定义, ()()×()μ(pn)μ(p)×μ(n), 由我们刚才所讲的 ()μ(p) 一定等于 −1−1, 我们有 ()−1()−()μ(pn)−1μ(n)−μ(n)我们发现这个过程很类似于筛法, 所以我们可以使用埃氏筛 ( )O(n ln ln n) 的做但事实上还可以优化, 如果我们使用线性筛, 则可以做到 ()O(n). 简要介绍一下线性筛的思想, 只用一个合数最小的质因子来筛除这个数, 具体可以看代码然后感性理解或者 OI-Wiki而几乎在所有的本文提到的数论函数中, 线性筛其实是好写于埃氏筛的, 通常表现在于我们只需要找到一个最小的 n 的质因数p, 这个目标是与线性筛相同的这里贴一份代码// Made By BilllIlllly std::vectorbool is_prime; std::vectorint mu; std::vectorint primes; void sieve(int n) { is_prime.assign(n 1, true); mu.assign(n 1, 0); is_prime[1] false; // 如果你认为 1 是质数, 那你也可以去掉这一行 mu[1] 1; for (int i 2; i n; i) { if (is_prime[i]) { primes.emplace_back(i); mu[i] -1; } for (int p : primes) { if (i * p n) break; is_prime[i * p] false; if (i % p 0) { mu[i * p] 0; break; } mu[i * p] -mu[i]; } } }例题互质数对个数这是莫比乌斯反演最经(jian)典(dan)的一道例题, 虽然好像并没有找到被出成题的版本给定一个正整数 n, 求 ∑1∑1[(,)1]i1∑n​j1∑n​[gcd(i,j)1], 简单来说就是在 [1,][1,n] 中有多少个互质的整数对朴素做法枚举 ,i,j, 然后求gcd, 是 (2)O(n2logn) 的, 不能接受反演做法我们发现 [(,)1][gcd(i,j)1] 可以写成 ((,))ε(gcd(i,j)), 所以原式等于∑1∑1((,))i1∑n​j1∑n​ε(gcd(i,j))由莫比乌斯反演, 原式等于∑1∑1∑∣(,)()i1∑n​j1∑n​d∣gcd(i,j)∑​μ(i)∑1∑1∑∣∣()i1∑n​j1∑n​d∣id∣j​∑​μ(i)考虑从枚举 (,)(i,j) 变为枚举 d, 原式等于∑1∑∣∑∣()d1∑n​d∣i∑n​d∣j∑n​μ(d)这里需要注意的是, 虽然我们写的是 ∣,∣d∣i,d∣j, 但事实上这两个求和的求和记号分别是 ,i,j, 简单来说我们实际上实在令 ,i,j 是 d 的倍数这个时候发现原式的 ()μ(d) 和 ,i,j 无关, 所以我们直接交换求和次序, 原式等于∑1()∑∣∑∣1d1∑n​μ(d)d∣i∑n​d∣j∑n​1最后我们考虑这里的后面两个 ∑∑ 怎么处理, 事实上, ,i,j 的取值数量为 n 中的 d 的倍数的数量, 也就是 ⌊⌋⌊dn​⌋, 所以总共有 ⌊⌋2⌊dn​⌋2 个取值, 原式就终于被我们化为了∑1(()⌊⌋2)d1∑n​(μ(d)⌊dn​⌋2)我们分析这个式子()μ(d) 事实上是可以通过预处理达到 (1)O(1) 的, 预处理的复杂度最常见的可以线性筛(前文讲过); 或者如果需求更快, 可以用杜教筛; 想要更快, 可以用洲阁筛或者Min-25筛(当然我只会线性筛).⌊⌋2⌊dn​⌋2 显然可以 (1)O(1) 每次的求出综上, 通过线性筛预处理, 我们至少可以做到 ()O(n).优化整除分块现在具体再来讲一下莫比乌斯反演最严厉的父亲——整除分块。预处理出 μ 的前缀和利用整除分块也叫数论分块我们可以把单次查询的复杂度降到 ()O(n​)观察式子 ⌊⌋⌊dn​⌋当 d 在 [1,][1,n] 内变化时这个式子的取值其实只有 ()O(n​) 种。为什么呢当 ≤d≤n​ 时⌊⌋⌊dn​⌋ 显然最多只有 n​ 种取值。当 dn​ 时⌊⌋≤⌊dn​⌋≤n​所以也最多只有 n​ 种取值。综上取值总数不超过 22n​。而且对于同一个取值 ⌊⌋k⌊dn​⌋满足条件的 d 一定是一段连续的区间 [,][l,r]。这个区间的右端点 r 怎么求呢由 ⌊⌋≤k⌊dn​⌋≤dn​可得 ≤d≤kn​所以最大的 d 就是 ⌊⌋⌊kn​⌋。也就是说右端点 ⌊⌊/⌋⌋r⌊⌊n/l⌋n​⌋。这样我们就可以把 d 分成 ()O(n​) 段每一段内的 ⌊⌋2⌊dn​⌋2 是相同的提出来之后只需要乘上这一段 ()μ(d) 的和即前缀和之差即可。预处理前缀和 ()O(n)单次查询 ()O(n​)。我们将一些问题的复杂度从最初的 (2)O(n2logn) 降为了 ()O(n​)!YY的GCD有了整除分块我们来看一道真正的板子题。题目大意给定 ,N,M求 ∑1∑1[gcd⁡(,)∈prime]i1∑N​j1∑M​[gcd(i,j)∈prime]。多组询问。推导过程首先枚举质数 p∑∈prime∑1∑1[gcd⁡(,)]p∈prime∑​i1∑N​j1∑M​[gcd(i,j)p]把 p 除进去∑∈prime∑1⌊/⌋∑1⌊/⌋[gcd⁡(,)1]p∈prime∑​i1∑⌊N/p⌋​j1∑⌊M/p⌋​[gcd(i,j)1]使用基本反演公式 [gcd⁡(,)1]∑∣gcd⁡(,)()[gcd(i,j)1]∑d∣gcd(i,j)​μ(d)∑∈prime∑1⌊/⌋∑1⌊/⌋∑∣gcd⁡(,)()p∈prime∑​i1∑⌊N/p⌋​j1∑⌊M/p⌋​d∣gcd(i,j)∑​μ(d)把 d 提出来先枚举∑∈prime∑1min⁡(⌊/⌋,⌊/⌋)()⌊⌋⌊⌋p∈prime∑​d1∑min(⌊N/p⌋,⌊M/p⌋)​μ(d)⌊pdN​⌋⌊pdM​⌋这里令 Tpd则 /dT/p。我们改变枚举顺序先枚举 T∑1min⁡(,)⌊⌋⌊⌋∑∣,∈prime()T1∑min(N,M)​⌊TN​⌋⌊TM​⌋p∣T,p∈prime∑​μ(pT​)令 ()∑∣,∈prime()f(T)p∣T,p∈prime∑​μ(pT​)。那么原式 ∑1min⁡(,)⌊⌋⌊⌋()T1∑min(N,M)​⌊TN​⌋⌊TM​⌋f(T)对于 ()f(T)我们可以用类似埃氏筛的方法在 (log⁡)O(NlogN) 内预处理出来并求出前缀和 ()∑1()S(T)∑i1T​f(i)。cpp// 预处理 f(T) for (int i 1; i MAXN; i) { if (is_prime[i]) { for (int j 1; i * j MAXN; j) { f[i * j] mu[j]; } } } // 求前缀和 for (int i 1; i MAXN; i) { sum_f[i] sum_f[i - 1] f[i]; }然后对于每次询问利用整除分块可以在 ()O(N​M​) 的时间内求出答案cpplong long solve(int n, int m) { long long res 0; int limit min(n, m); for (int l 1, r; l limit; l r 1) { r min(n / (n / l), m / (m / l)); res (long long)(n / l) * (m / l) * (sum_f[r] - sum_f[l - 1]); } return res; }预处理 (log⁡)O(NlogN)单次询问 ()O(N​)这题就愉快地解决了。NDPC_L - LCM现在回顾这道让我学这个东西的题题意给定 N 和 1…1…N 的一个排列 A。有一个 N 个顶点的有向图对于 1≤≤1≤ij≤N从顶点 i 到顶点 j 有 lcm(,)lcm(Ai​,Aj​) 条有向边。求对于每个 2,3,…,v2,3,…,N从顶点 1 到顶点 v 的路径数对 998244353 取模。两条路径不同当且仅当它们经过的边的集合不同。≤2×105N≤2×105。做法首先最直接的思路肯定是 DP废话这都是ndpc了。设 dpj​ 为从顶点 1 到顶点 j 的路径数。显然 11dp1​1。对于 1j1转移方程为∑1−1×lcm(,)dpj​i1∑j−1​dpi​×lcm(Ai​,Aj​)这坨直接算是 (2)O(N2) 的对于 2×105N2×105 显然你 T 飞了。考虑优化。看到 lcmlcm显然要把它转化为 gcd⁡gcdlcm(,)gcd⁡(,)lcm(x,y)gcd(x,y)xy​代入转移方程∑1−1gcd⁡(,)∑1−11gcd⁡(,)dpj​i1∑j−1​dpi​gcd(Ai​,Aj​)Ai​Aj​​Aj​i1∑j−1​dpi​Ai​gcd(Ai​,Aj​)1​现在问题变成了如何快速处理 1gcd⁡(,)gcd(x,y)1​。我们知道对于任意积性函数 f都可以写成 (gcd⁡(,))∑∣gcd⁡(,)()f(gcd(x,y))∑d∣gcd(x,y)​g(d) 的形式其中 ∗gf∗μ。这里 ()1f(n)n1​我们来求一下对应的 ()g(d)为了方便下面记作 ℎ()h(d)ℎ()∑∣()()∑∣1()h(d)k∣d∑​f(k)μ(kd​)k∣d∑​k1​μ(kd​)因为 f 和 μ 都是积性函数所以 ℎh 也是积性函数。我们只需要算它在质数幂 pa 处的值ℎ()∑01(−)h(pa)i0∑a​pi1​μ(pa−i)因为 (−)μ(pa−i) 只有在 −0a−i0 或 11 时非零所以只有最后两项ℎ()1(1)1−1()1−1−11−h(pa)pa1​μ(1)pa−11​μ(p)pa1​−pa−11​pa1−p​所以对于任意 ∏n∏piai​​ℎ()∏1−1∏∣(1−)h(n)∏piai​​1−pi​​n1​p∣n∏​(1−p)于是我们得到了一个非常漂亮的恒等式1gcd⁡(,)∑∣gcd⁡(,)ℎ()gcd(x,y)1​d∣gcd(x,y)∑​h(d)将这个恒等式代回 dpj​ 的式子中∑1−1∑∣gcd⁡(,)ℎ()dpj​Aj​i1∑j−1​dpi​Ai​d∣gcd(Ai​,Aj​)∑​h(d)交换求和顺序先枚举 d。因为 d 必须同时整除 Ai​ 和 Aj​所以 d 必须是 Aj​ 的约数∑∣ℎ()∑1−1[∣]dpj​Aj​d∣Aj​∑​h(d)i1∑j−1​dpi​Ai​[d∣Ai​]令 ∑1−1[∣]Sd​∑i1j−1​dpi​Ai​[d∣Ai​]表示前面所有满足 ∣d∣Ai​ 的 dpi​Ai​ 的和。那么转移方程就变成了∑∣ℎ()dpj​Aj​d∣Aj​∑​h(d)Sd​在计算出 dpj​ 之后我们需要更新所有的 Sd​。对于 Aj​ 的每一个约数 d我们将 dpj​Aj​ 加到 Sd​ 中←Sd​←Sd​dpj​Aj​复杂度这个算法的复杂度如何呢对于每个 j我们需要枚举 Aj​ 的所有约数。因为 A 是 1…1…N 的排列所以 ≤Aj​≤N。一个数 ≤x≤N 的约数个数平均是 (log⁡)O(logN)。所以枚举约数的总复杂度是 ∑1()∑1()(log⁡)∑j1N​d(Aj​)∑x1N​d(x)O(NlogN)。预处理 ℎ()h(d) 和每个数的列表也显然可以在 (log⁡)O(NlogN) 的复杂度内完成所以总时间复杂度 (log⁡)O(NlogN)空间复杂度 (log⁡)O(NlogN)代码实现这里贴一份核心代码// divs[x] 存储了 x 的所有约数 // h[d] 就是 h(d) // S[d] 维护 S_d static constexpr int MOD 998244353 std::vectorlong long dp(N 1, 0); std::vectorlong long S(N 1, 0); dp[1] 1; // 初始化 S把 dp[1] * A[1] 加到 A[1] 的所有约数对应的 S 中 long long val1 A[1]; // dp[1] * A[1] for (int d : divs[A[1]]) S[d] (S[d] val1) % MOD; for (int j 2; j N; j) { long long sum 0; // 计算 dp[j] for (int d : divs[A[j]]) sum (sum S[d] % MOD * h[d]) % MOD; dp[j] sum * A[j] % MOD; // 输出答案 std::cout dp[j] \n; // 更新 S为了后面的 j 转移 if (j N) { long long val dp[j] * A[j] % MOD; for (int d : divs[A[j]]) S[d] (S[d] val) % MOD; } }代码里的h[d]可以提前用 YY的GCD 的方法预用线性筛处理出来初始时h[i] inv[i]然后对于每个质数p把它的倍数的h都乘上(1 - p MOD) % MOD即可。