对于一个函数f(x)f(x), 如果满足对于任意的 $(a, b) |gcd(a,b)1,a∈Z,b∈Zgcd(a,b)1,a∈Z,b∈Z,f(ab)f(a)f(b)f(ab)f(a)f(b), 那么称这个函数为积性函数(数论函数)特别地, 如果对于所有的(a,b)∣a∈Z,b∈Z(a,b)∣a∈Z,b∈Z 都有f(ab)f(a)f(b)f(ab)f(a)f(b) 的话, 函数ff 被称为 完全积性函数(完全数论函数)二者区别在于是否要求两整数互质常见的积性函数常数函数:1(n)11(n)1 (完全积性函数)单位函数:ε(n)[n1]ε(n)[n1][1] (完全积性函数)恒等函数:idk(n)nkidk​(n)nk, 这里通常所说的恒等函数当kk 取11, 即id1id1​, 一般记作idid (完全积性函数)除数函数:σk(n)∑d∣ndkσk​(n)d∣n∑​dk, 通常我们把σ1(n)σ1​(n) 记作σ(n)σ(n) 或者d(n)d(n), 实际意义是nn 的因数和欧拉函数:φ(n)∑i1n[gcd(i,n)1]φ(n)i1∑n​[gcd(i,n)1], 即统计小于等于nn 的数中与nn 互质的数的个数莫比乌斯函数: 简单说来: 当nn 等于11 时,μ(n)1μ(n)1; 否则, 当nn 的素数分解中有非一次的素因子时μ(n)0μ(n)0; 否则, 当nn 有奇数个素因子时,μ(n)−1μ(n)−1; 否则,μ(n)1μ(n)1. 形式化地μ(n){1,n10,n有平方素因子(−1)k,np1p2⋯pkk个不同素因子μ(n)⎩⎨⎧​1,0,(−1)k,​n1n 有平方素因子np1​p2​⋯pk​k 个不同素因子​推荐读者自己证明所有的积性函数的 积性狄利克雷卷积对于积性函数ff 和gg, 它们的卷积f∗gf∗g 满足这样一个关系式:(f∗g)(n)∑d∣nf(n)g(nd)(f∗g)(n)d∣n∑​f(n)g(dn​)这里有一个良好的性质, 因为因数是成对出现的, 所以积性函数卷积显然满足交换律(当然卷积本身就满足交换律), 也就是说我们有(f∗g)(n)∑d∣nf(n)g(nd)∑d∣ng(n)f(nd)(f∗g)(n)d∣n∑​f(n)g(dn​)d∣n∑​g(n)f(dn​)莫比乌斯反演莫比乌斯反演就是利用莫比乌斯函数和狄利克雷卷积将一些难以直接计算的量转化为便于计算的量从而降低复杂度最常用的是下列恒等式∑d∣nμ(d)[n1]ε(n)d∣n∑​μ(d)[n1]ε(n)Proof根据狄利克雷卷积, 我们还可以知道ε1∗με1∗μ以这一个最常见的莫比乌斯反演作为例子, 读者理解后应当可以推出大多其它的反演式子求解莫比乌斯函数根据定义我们显然可以枚举出来质因数然后 check, 是O(n)O(n​) 的, 但当我们要求出很多数的莫比乌斯函数的时候这个复杂度就有些难以接受了为了解决这个问题, 我们来思考如何确定nn 的莫比乌斯函数的取值, 因为这是一个积性函数, 且对于一个质数pp,μ(p)μ§ 一定等于−1−1. 所以当nn 为合数时, 我们可以枚举小于nn 的质数pp, 然后分为两类:p∣np∣n, 这个时候的μ(pn)μ(pn) 一定含有一个p2p2的因子项, 所以μ(pn)0μ(pn)0p∤np∤n, 这个时候μ(pn)μ(pn) 相当于在nn 的基础上添加了一个新的因子pp, 由积性函数定义,μ(pn)μ(p)×μ(n)μ(pn)μ§×μ(n), 由我们刚才所讲的μ(p)μ§ 一定等于−1−1, 我们有μ(pn)−1μ(n)−μ(n)μ(pn)−1μ(n)−μ(n)我们发现这个过程很类似于筛法, 所以我们可以使用埃氏筛O(nlnlnn)O(n ln ln n) 的做但事实上还可以优化, 如果我们使用线性筛, 则可以做到O(n)O(n). 简要介绍一下线性筛的思想, 只用一个合数最小的质因子来筛除这个数, 具体可以看代码然后感性理解或者 OI-Wiki而几乎在所有的本文提到的数论函数中, 线性筛其实是好写于埃氏筛的, 通常表现在于我们只需要找到一个最小的nn 的质因数pp, 这个目标是与线性筛相同的这里贴一份代码// Made By BilllIlllly std::vector is_prime;std::vector mu;std::vector 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)的一道例题, 虽然好像并没有找到被出成题的版本给定一个正整数nn, 求∑i1n∑j1n[gcd(i,j)1]i1∑n​j1∑n​[gcd(i,j)1], 简单来说就是在[1,n][1,n] 中有多少个互质的整数对朴素做法枚举i,ji,j, 然后求gcd, 是O(n2logn)O(n2logn) 的, 不能接受反演做法我们发现[gcd(i,j)1][gcd(i,j)1] 可以写成ε(gcd(i,j))ε(gcd(i,j)), 所以原式等于∑i1n∑j1nε(gcd(i,j))i1∑n​j1∑n​ε(gcd(i,j))由莫比乌斯反演, 原式等于∑i1n∑j1n∑d∣gcd(i,j)μ(i)i1∑n​j1∑n​d∣gcd(i,j)∑​μ(i)∑i1n∑j1n∑d∣id∣jμ(i)i1∑n​j1∑n​d∣id∣j​∑​μ(i)考虑从枚举(i,j)(i,j) 变为枚举dd, 原式等于∑d1n∑d∣in∑d∣jnμ(d)d1∑n​d∣i∑n​d∣j∑n​μ(d)这里需要注意的是, 虽然我们写的是d∣i,d∣jd∣i,d∣j, 但事实上这两个求和的求和记号分别是i,ji,j, 简单来说我们实际上实在令i,ji,j 是dd 的倍数这个时候发现原式的μ(d)μ(d) 和i,ji,j 无关, 所以我们直接交换求和次序, 原式等于∑d1nμ(d)∑d∣in∑d∣jn1d1∑n​μ(d)d∣i∑n​d∣j∑n​1最后我们考虑这里的后面两个∑∑ 怎么处理, 事实上,i,ji,j 的取值数量为nn 中的dd 的倍数的数量, 也就是⌊nd⌋⌊dn​⌋, 所以总共有⌊nd⌋2⌊dn​⌋2个取值, 原式就终于被我们化为了∑d1n(μ(d)⌊nd⌋2)d1∑n​(μ(d)⌊dn​⌋2)我们分析这个式子μ(d)μ(d) 事实上是可以通过预处理达到O(1)O(1) 的, 预处理的复杂度最常见的可以线性筛(前文讲过); 或者如果需求更快, 可以用杜教筛; 想要更快, 可以用洲阁筛或者Min-25筛(当然我只会线性筛).⌊nd⌋2⌊dn​⌋2显然可以O(1)O(1) 每次的求出综上, 通过线性筛预处理, 我们 至少 可以做到O(n)O(n).优化整除分块现在具体再来讲一下莫比乌斯反演最严厉的父亲——整除分块。预处理出μμ 的前缀和利用整除分块也叫数论分块我们可以把单次查询的复杂度降到O(n)O(n​)观察式子⌊nd⌋⌊dn​⌋当dd 在[1,n][1,n] 内变化时这个式子的取值其实只有O(n)O(n​) 种。为什么呢当d≤nd≤n​时⌊nd⌋⌊dn​⌋ 显然最多只有nn​种取值。当dndn​时⌊nd⌋≤n⌊dn​⌋≤n​所以也最多只有nn​种取值。综上取值总数不超过2n2n​。而且对于同一个取值k⌊nd⌋k⌊dn​⌋满足条件的dd 一定是一段连续的区间[l,r][l,r]。这个区间的右端点rr 怎么求呢由k⌊nd⌋≤ndk⌊dn​⌋≤dn​可得d≤nkd≤kn​所以最大的dd 就是⌊nk⌋⌊kn​⌋。也就是说右端点r⌊n⌊n/l⌋⌋r⌊⌊n/l⌋n​⌋。这样我们就可以把dd 分成O(n)O(n​) 段每一段内的⌊nd⌋2⌊dn​⌋2是相同的提出来之后只需要乘上这一段μ(d)μ(d) 的和即前缀和之差即可。预处理前缀和O(n)O(n)单次查询O(n)O(n​)。我们将一些问题的复杂度从最初的O(n2logn)O(n2logn) 降为了O(n)O(n​)!YY的GCD有了整除分块我们来看一道真正的板子题。题目大意给定N,MN,M求∑i1N∑j1M[gcd⁡(i,j)∈prime]i1∑N​j1∑M​[gcd(i,j)∈prime]。多组询问。推导过程首先枚举质数pp∑p∈prime∑i1N∑j1M[gcd⁡(i,j)p]p∈prime∑​i1∑N​j1∑M​[gcd(i,j)p]把pp 除进去∑p∈prime∑i1⌊N/p⌋∑j1⌊M/p⌋[gcd⁡(i,j)1]p∈prime∑​i1∑⌊N/p⌋​j1∑⌊M/p⌋​[gcd(i,j)1]使用基本反演公式[gcd⁡(i,j)1]∑d∣gcd⁡(i,j)μ(d)[gcd(i,j)1]∑d∣gcd(i,j)​μ(d)∑p∈prime∑i1⌊N/p⌋∑j1⌊M/p⌋∑d∣gcd⁡(i,j)μ(d)p∈prime∑​i1∑⌊N/p⌋​j1∑⌊M/p⌋​d∣gcd(i,j)∑​μ(d)把dd 提出来先枚举∑p∈prime∑d1min⁡(⌊N/p⌋,⌊M/p⌋)μ(d)⌊Npd⌋⌊Mpd⌋p∈prime∑​d1∑min(⌊N/p⌋,⌊M/p⌋)​μ(d)⌊pdN​⌋⌊pdM​⌋这里令TpdTpd则dT/pdT/p。我们改变枚举顺序先枚举TT∑T1min⁡(N,M)⌊NT⌋⌊MT⌋∑p∣T,p∈primeμ(Tp)T1∑min(N,M)​⌊TN​⌋⌊TM​⌋p∣T,p∈prime∑​μ(pT​)令f(T)∑p∣T,p∈primeμ(Tp)f(T)p∣T,p∈prime∑​μ(pT​)。那么原式 ∑T1min⁡(N,M)⌊NT⌋⌊MT⌋f(T)T1∑min(N,M)​⌊TN​⌋⌊TM​⌋f(T)对于f(T)f(T)我们可以用类似埃氏筛的方法在O(Nlog⁡N)O(NlogN) 内预处理出来并求出前缀和S(T)∑i1Tf(i)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];}