cc0000 想学会莫（魔）反（法）！
关于莫反：
最没用的东西： 若 \(f(x)=\sum \limits_{d|x} g(d)\)，则 \(g(x)=\sum\limits_{d|x} \mu(d) f(d)\)。这是莫比乌斯反演的定义式。
关于一车有用的狄利克雷卷积：
\(\mu*1=\varepsilon\)
\(id*1=\sigma\)，\(\sigma\) 为因子的和。
\(\mu * id =\varphi\)。
证明省略。
最重要的式子：\([\gcd (i,j)==1]=\sum\limits_{d|\gcd (i,j)} \mu(d)\)
然后我至今位置想到的做法：
- 不会了就把式子往前提。
- 连乘形式的就枚举底数然后把乘法转化到指数的加法。
- 出现形如 \(dt\) 之类的设一个 \(T=td\)。
P5518 [MtOI2019]幽灵乐团 / 莫比乌斯反演基础练习题
有人和我讲写完这题莫反就是学会了。
所以我决定写一写这个题解。
首先是讲式子分别拆成 \(\prod \limits_{i=1}^A\prod\limits_{j=1}^B\prod\limits_{k=1}^C i^{f(type)}\) 和 \(\prod \limits_{i=1}^A\prod\limits_{j=1}^B\prod\limits_{k=1}^C \gcd (i,j)^{f(type)}\)
这样形式比较简单，到时候左边除以右边就行。
\(type=0\)
\((1)\)
\(\prod\limits_{i=1}^A\prod\limits_{j=1}^B\prod\limits_{k=1}^C i\)
\(=\prod\limits_{i=1}^A i^{BC}\)
\(=(i!)^{BC}\)
非常的简单啊。
\((2)\)
\(\large\prod\limits_{i=1}^A\prod\limits_{j=1}^B\prod\limits_{k=1}^C \gcd(i,j)\)
\(\large=\Big(\prod\limits_{i=1}^A\prod\limits_{j=1}^B \gcd(i,j)\Big)^C\)
\(\large=\Big(\prod\limits_{d=1} d^{\sum_{i=1}^A\sum_{j=1}^B[\gcd（i,j)==d]}\Big)^C\)
\(=\large \Big( \prod\limits_{d=1} d^{\sum\limits_{i=1}^{\lfloor \frac A d\rfloor}\sum\limits_{h=1}^{\lfloor \frac B d\rfloor}[\gcd (i,j)==1]}\Big)^C\)
\(=\large \Big( \prod\limits_{d=1} d^{\sum\limits_{i=1}^{\lfloor \frac A d\rfloor}\sum\limits_{h=1}^{\lfloor \frac B d\rfloor}\sum\limits _{t|\gcd(i,j)}\mu(t)}\Big)^C\)
\(=\large \Big( \prod\limits_{d=1} d^{\sum\limits _{t}\mu(t){\lfloor \frac A {td}\rfloor}{\lfloor \frac B {td}\rfloor}}\Big)^C\)
\(=\large \Big( \prod \limits _{T=1} (\prod\limits_{d|T} d^{\mu(\frac T d)})^{\lfloor \frac A{T}\rfloor \lfloor\frac B {T}\rfloor}\Big)^C\)
我们可以通过 \(O(n\log n)\) 的时间预处理 $f(T)=\prod \limits_{d|T} d^{\mu(\frac T d)} $，然后到求的时候直接整除分块即可。
\(type=1,2\)
困了，咕咕咕。
标签：lfloor,frac,limits,Big,sum,重学莫反,prod From： https://www.cnblogs.com/cc0000/p/17234705.html