7
头图
正文
本人来随便学点高级数论 （其实是乱翻《算法竞赛》），有错轻喷。
莫比乌斯函数
μ(n)={1n=1(−1)kn 是 k 个不同质数的乘积0n 含有平方因子\mu(n)= \begin{cases} 1 & n=1 \\\\ (-1)^k & n\text{ 是 }k\text{ 个不同质数的乘积} \\\\ 0 & n\text{ 含有平方因子} \end{cases} μ(n)=⎩⎨⎧ 1(−1)k0 n=1n 是 k 个不同质数的乘积n 含有平方因子
即：
* 只要有 p2∣np^2 \mid np2∣n，就有 μ(n)=0\mu(n)=0μ(n)=0。
* 若 n=p1p2⋯pkn=p_1p_2\cdots p_kn=p1 p2 ⋯pk （pip_ipi 都是质数且所有数互不相同），则 μ(n)=(−1)k\mu(n)=(-1)^kμ(n)=(−1)k。
计算
因为莫比乌斯函数是积性函数（即 f(1)=1f(1) =1f(1)=1 且在 gcd(a,b)=1gcd(a,b)=1gcd(a,b)=1 的情况下有 f(a⋅b)=f(a)⋅f(b)f(a⋅b)=f(a)⋅f(b)f(a⋅b)=f(a)⋅f(b)），所以可以用在 O(n)O(n)O(n) 时间内预处理出所有 [1,n][1,n][1,n] 内的莫比乌斯函数值。
[1] 质数的 μμμ 为 −1-1−1。
[2] 如果一个数存在某个质因子的指数大于 111，那么它的 μμμ 值为 000 。
* 值得注意的是，只有当数存在最小质因子的指数大于 111 时，才会被直接筛为 000
* 其他情况则由公式 μ(d)=−μ(i)\mu(d)=-\mu(i)μ(d)=−μ(i) 完成，其中 ddd 是当前数，iii 是某个小于 ddd 的数
这种方法利用了积性函数的性质，使得每个数只被处理一次，从而实现线性筛。
示例 Python 代码：
基础恒等式
这个式子是可以证明的，只是没那么简洁，这里不贴了，想看可以点我。
∑d∣nμ(d)={1n=10n>1\sum_{d\mid n} \mu(d) = \begin{cases} 1 & n=1 \\\\ 0 & n>1 \end{cases} d∣n∑ μ(d)=⎩⎨⎧ 10 n=1n>1
莫比乌斯反演
根据上方恒等式，可推出若两个函数满足：
g(n)=∑d∣nf(d)g(n)=\sum_{d\mid n} f(d) g(n)=d∣n∑ f(d)
则有：
f(n)=∑d∣nμ(d) g (nd)f(n)=\sum_{d\mid n} \mu(d)\, g\!\left(\frac{n}{d}\right) f(n)=d∣n∑ μ(d)g(dn )
莫比乌斯反演例子
欧拉函数
已知：
n=∑d∣nφ(d)n = \sum_{d\mid n} \varphi(d) n=d∣n∑ φ(d)
反演得：
φ(n)=∑d∣nμ(d)nd\varphi(n)=\sum_{d\mid n} \mu(d)\frac{n}{d} φ(n)=d∣n∑ μ(d)dn
统计互质对数
∑i=1n∑j=1n[gcd(i,j)=1]=∑d=1nμ(d)⌊nd⌋2\sum_{i=1}^n \sum_{j=1}^n [\gcd(i,j)=1] = \sum_{d=1}^n \mu(d)\left\lfloor \frac{n}{d}\right\rfloor^2 i=1∑n j=1∑n [gcd(i,j)=1]=d=1∑n μ(d)⌊dn ⌋2
莫比乌斯反演例题
P2522
题目求的是 ∑i=xn∑j=ym[gcd(i,j)=k]\sum_{i=x}^n \sum_{j=y} ^m [\gcd(i,j) = k]∑i=xn ∑j=ym [gcd(i,j)=k]，简单的类似二维前缀和的方法优化式子，然后消掉 kkk 变为 ∑i=1⌊nk⌋∑j=1⌊mk⌋[gcd(i,j)=1]\sum_{i=1}^{\lfloor \frac{n}{k} \rfloor} \sum_{j=1} ^{\lfloor \frac{m}{k} \rfloor} [\gcd(i,j) = 1]∑i=1⌊kn ⌋ ∑j=1⌊km ⌋ [gcd(i,j)=1]。
再变为 ∑i=1⌊nk⌋∑j=1⌊mk⌋∑d∣gcd(i,j)μ(d)\sum_{i=1}^{\lfloor \frac{n}{k} \rfloor} \sum_{j=1} ^{\lfloor \frac{m}{k} \rfloor} \sum _{d | \gcd(i,j)} \mu(d)∑i=1⌊kn ⌋ ∑j=1⌊km ⌋ ∑d∣gcd(i,j) μ(d)。
接下来交换求和顺序，在上述式子中，如果 ddd 要被枚举到，显然需要当且仅当 d∣id∣id∣i 并且 d∣jd∣jd∣j。所以把这个部分计入到贡献当中：
∑dμ(d)∑i=1⌊nk⌋[d ∣ i]∑j=1⌊mk⌋[d ∣ j]\sum_d \mu(d) \sum_{i=1}^{\lfloor \frac{n}{k} \rfloor} [d \space | \space i] \sum_{j=1} ^{\lfloor \frac{m}{k} \rfloor } [d \space | \space j] d∑ μ(d)i=1∑⌊kn ⌋ [d ∣ i]j=1∑⌊km ⌋ [d ∣ j]
最后化简：
∑dμ(d)⌊ndk⌋⌊mdk⌋\sum_d\mu(d)\lfloor\dfrac{n}{dk}\rfloor\lfloor\dfrac{m}{dk}\rfloor d∑ μ(d)⌊dkn ⌋⌊dkm ⌋
但是数据太强了，直接计算过不了，所以我们可以用到积性函数的性质做前缀和用 O(n)O(\sqrt n)O(n ) 的复杂度求解。
P2257
题目求的是 ∑i=xn∑j=ym[gcd(i,j)∈Prime]\sum_{i=x}^n \sum_{j=y} ^m [\gcd(i,j) \in \text{Prime}]∑i=xn ∑j=ym [gcd(i,j)∈Prime]。
按照 P2522 的套路变为：
∑k∈Prime∑dμ(d)⌊ndk⌋⌊mdk⌋\sum _{k \in \text{Prime}} \sum_d \mu(d) \lfloor \dfrac{n}{dk} \rfloor \lfloor \dfrac{m}{dk} \rfloor k∈Prime∑ d∑ μ(d)⌊dkn ⌋⌊dkm ⌋
发现过不了。
观察到复杂度高的原因是双求和导致的，并且 dkdkdk 重复出现了，所以可以令 T=dkT = dkT=dk。接下来，先枚举 TTT，显然 T≤min(n,m)T \le \min(n,m)T≤min(n,m)。先把后面的那个部分写下来。再考虑会有多少的 μ()μ()μ() 会加在这个部分上。我们要让求的和的值等价不变，由于 d=T÷kd = T \div kd=T÷k，所以：
∑T=1min(n,m)⌊nT⌋⌊mT⌋∑k∣T,k∈Primeμ(Tk)\sum _{T=1} ^{\min(n,m)} \lfloor \dfrac{n}{T} \rfloor \lfloor \dfrac{m}{T} \rfloor \sum _{k | T,k \in \text{Prime}} \mu (\dfrac{T}{k}) T=1∑min(n,m) ⌊Tn ⌋⌊Tm ⌋k∣T,k∈Prime∑ μ(kT )
发现后面那个部分跟 n,mn,mn,m 没有一点关系了。所以这个求和被我们优化掉了。开个数组记录一下就可以了。
注意，交换求和的意义是将东西一起计算，我们通常都会把一些相同的东西给组合到一起，这样就可以离线处理一些东西，继而达到降低时间复杂度的意义。
我的这份 Python 代码由于语言本身较慢所以是无法通过的。
应该不会有人第一遍就发现代码里的小彩蛋。
有帮助，赞一个