莫比乌斯反演·学习记录
程序员文章站
2022-05-08 11:06:08
莫比乌斯反演·学习记录 cyw在6.8左右学的莫比乌斯反演,记录一下 这个东西感觉不大好描述,我一开始也不知道这玩意能干嘛~~(其实现在也不知道)~~ CYW认为,对关于一些因数/倍数关系进行操作的行为,可以用莫比乌斯反演来解决 莫比乌斯函数 这并不是什么高大上的东西,但是很有用 对于 莫比乌斯函数 ......
莫比乌斯反演·学习记录
cyw在6.8左右学的莫比乌斯反演,记录一下
这个东西感觉不大好描述,我一开始也不知道这玩意能干嘛(其实现在也不知道)
CYW认为,对关于一些因数/倍数关系进行操作的行为,可以用莫比乌斯反演来解决
莫比乌斯函数
这并不是什么高大上的东西,但是很有用
对于 莫比乌斯函数 的定义是
- $d=1,\mu(d)=1 $
-
\(d=\prod_{k=1}^n p_k\;(k\in prime),\mu(d)=(-1)^k\)
即数\(d\)可以被表示为若干互异素数相乘的形式(指数不超过\(1\)),此时函数值根据分解数量而定 - \(Otherwise,\mu(d)=0\)
当然了 它有一些性质
- \(\mu\)是积性函数,这是它可以通过线性筛求的必要条件
- 对于正整数\(n\),\(\sum_{d|n}\mu(d)=[n=1]\),这是莫比乌斯反演中非常常用的一条性质
- 对于正整数\(n\),\(\sum_{d|n}\frac{\mu(d)}{d}=\frac{\phi(n)}{n}\),不过这个我还没用过
-
\[\mu \times id\;=\;\phi\]
\(\times\)表示卷积,这里是常见狄利克雷卷积的一种,有的时候有奇效
在公式里书写为
\[\sum_{d|n}\mu(\frac{n}{d})*d=\phi(n)\]贴一份线筛代码
inline void getmiu(int n){ memset(vis,0,sizeof(vis)); mu[1]=vis[1]=1; for (int i=2;i<=n;i++){ if (!vis[i]){pri[++cnt]=i;mu[i]=-1;} for (int j=1;j<=cnt&&(LL)i*pri[j]<=n;j++){ vis[i*pri[j]]=1; if (i%pri[j]==0) break;else mu[i*pri[j]]=-mu[i]; } } }
PS:一些题目中要求\(\sum\mu(d)\),可以通过预处理来降低复杂度
整除分块
一个同样在莫比乌斯反演及一些计算中十分重要的东西
\[\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor\]
这个东西暴力算是\(O(N)\)的,容易发现,\(\lfloor\frac{n}{i}\rfloor\)至多只有\(\sqrt{n}\)种取值,可以对每种取值的个数进行计算,再乘上对应的i,复杂度\(O(\sqrt{n})\)
for (int l=1,r;l<=n;l=r+1){ //可能会用到(for LL l=1,r;...) r=n/(n/l); ans+=(LL)(n/l)*(r-l+1); //注意在部分大运算前加(LL)或"1ll*",避免炸int }
好的,那么所有的前言:莫比乌斯函数,整除分块都讲完了,可以开始我们的正题
莫比乌斯反演
莫比乌斯反演
(有点小困 明晚更完)
上一篇: PHP+MYSQL的文章管理系统(二)
下一篇: Java打造CD、DVD数据库