莫比乌斯反演习题总结

一:常用卷积

\[1 * \mu = \epsilon\]

\[Id * \mu = \varphi\]

\[1 * \varphi = Id \]

最后一个是欧拉反演.

根据这些卷积之间的相互转化,在推式子时只要够敏感,就能巧妙地化简。(如P3768简单的数学题

二: 推式子的技巧

1. 改变枚举对象、枚举顺序

比如
\[ \begin{aligned} 1. &\sum_{i=1}^n\sum_{j=1}^n[gcd(i,j)=p]\\ =&\sum_{x=1}^{\frac{n}{p}}\sum_{y=1}^{\frac{n}{p}}[gcd(i,j)=1]\\ 2.&\sum_{i=1}^{n}\sum_{j=1}^ngcd(i,j)\\ =&\sum_{d=1}^{n}d\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{n}{d}}[gcd(i,j)=1] \end{aligned} \]

当一个一个数不受之前的 \(\sum\) 限制时可提前

2. 替换变量,优化复杂度(式子中不必要的枚举)

比如求这个:

\[ \begin{aligned} &\sum_{k=1}^nk\sum_{d=1}^\frac{n}{k}\mu(d)\frac{n}{dk}\frac{m}{dk}\\ =&\sum_{T=1}^n\frac{n}{T}\frac{m}{T}\sum_{d|T}\frac{T}{d}\mu(d) \end{aligned} \]

为什么这样?

其实替换变量也是为了改变枚举顺序,然后就可以愉快地整除分块了。

3. 一些连乘可以化成指数的 \(\sum\) 形式

P3704数字表格

这里不展开叙述 (其实是写的题太少)

三: 筛积性函数前缀和

如果一道题数据范围 \(1e10\), 大多都要用杜教筛

感谢 青灯夜游's Luogu blog 给出的一种线性筛积性函数的通用方法:

假设 \(g=f*h\), 是我们所要求的函数

定义 \(low(i) = p^c\), \(p\) 为 \(i\) 的最小质因子,\(c\) 为 \(i\) 质因数分解后 \(p\) 的指数.

线筛时,当 \(i \% prime[j] == 0\) 时

1: \(low(i)\ne i\)

\[g(prime(j)\times i)=g(\frac{i}{low(i)})\times g(prime(j)\times low(i))\]

2: \(low(i)=i\)

\[g(prime(j)\times i)=g(i)\times f(prime(j))+f(1)\times h(prime(j)\times i)\]


题目:

P2257 YY的GCD

P3327 [SDOI2015]约数个数和

P3455 [POI2007]ZAP-Queries

P2522 [HAOI2011]Problem b

P2522 [HAOI2011]Problem b

CF920G List Of Integers

P1829 [国家集训队]Crash的数字表格 / JZPTAB

P3704 [SDOI2017]数字表格

P4449 于神之怒加强版

由于本蒟蒻做题太少未完待续...

上一篇:C语言笔记 循环语句


下一篇:GDOI2018D2T1 谈笑风生