莫比乌斯反演
目录反演公式&性质
\[f(n)=\sum_{d|n}g(d)\\ g(n)=\sum_{d|n}\mu(d)f(\frac nd) \]感觉我不太会用上面那个
我只会用莫比乌斯函数的性质
\[\sum_{d|n}\mu(d)=\begin{cases}1&n=1\\0&n\ne 1\end{cases} 或者 \sum_{d|n}\mu(d)=(n==1) \]然后特殊的
\[\sum_{d|gcd(a,b)}\mu(d)=(gcd(a,b)==1) \]例题
然后直接上例题
[HAOI2011]Problem b
化简题意求\(\sum_{i=1}^n\sum_{j=1}^m(gcd(i,j)==k)\)，要求\(\sqrt n\)求出
\[\sum_{i=1}^{\left \lfloor \frac{n}{k} \right \rfloor}\sum_{j=1}^{\left \lfloor \frac{m}{k} \right \rfloor}(gcd(i,j)==1) \]直接套上面的性质：
\[=\sum_{i=1}^{\left \lfloor \frac{n}{k} \right \rfloor}\sum_{j=1}^{\left \lfloor \frac{m}{k} \right \rfloor}\sum_{d|gcd(a,b)}\mu(d) \]然后设\(i=di',j=dj'(d=gcd(i,j))\)
\[=\sum_{d=1}^{\frac{n}{k}}\mu(d)\sum_{i'=1}^{\frac{n}{kd}}\sum_{j'=1}^{\frac{m}{kd}}1 \]\[=\sum_{d=1}^{\frac{n}{k}}\mu(d)\left \lfloor \frac{n}{kd} \right \rfloor\left \lfloor \frac{m}{kd} \right \rfloor \]然后熟悉的式子，可以数论分块
所以记住一条式子方便推：
\[\sum_{i=1}^{n}\sum_{j=1}^{m}(gcd(i,j)==1)=\sum_{d=1}^{n}\mu(d)\left \lfloor \frac{n}{d} \right \rfloor\left \lfloor \frac{m}{d} \right \rfloor \]YY的GCD
求\(\sum_{i=1}^{n}\sum_{j=1}^{m}(gcd(i,j)\in P)\)，P指素数集，要求\(\sqrt n\)求出
\[\sum_{p\in P}\sum_{i=1}^{n}\sum_{j=1}^{m}(gcd(i,j)==p) \]\[=\sum_{p\in P}\sum_{i=1}^{\left \lfloor \frac{n}{p} \right \rfloor}\sum_{j=1}^{\left \lfloor \frac{m}{p} \right \rfloor}(gcd(i,j)==1) \]\[=\sum_{p\in P}\sum_{d=1}^{\left \lfloor \frac{n}{p} \right \rfloor}\mu(d)\left \lfloor \frac{n}{pd} \right \rfloor\left \lfloor \frac{m}{pd} \right \rfloor \]令T=pd
\[=\sum_{T=1}^n\left \lfloor \frac{n}{T} \right \rfloor\left \lfloor \frac{m}{T} \right \rfloor\sum_{p|T,p\in P}\mu(\frac Tp) \]\(\sum_{p|T,p\in P}\mu(\frac Tp)\)用线性筛处理，然后还是数论分块
于神之怒加强版
求\(\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j)^k\)，要求\(\sqrt n\)求出
\[\sum_{x=1}^n\sum_{i=1}^{n}\sum_{j=1}^{m}(gcd(i,j)==x)x^k \]\[=\sum_{x=1}^n\sum_{d=1}^{\left \lfloor \frac{n}{x} \right \rfloor}\mu(d)\left \lfloor \frac{n}{dx} \right \rfloor\left \lfloor \frac{m}{dx} \right \rfloor x^k \]令T=dx
\[=\sum_{T=1}^n\left \lfloor \frac{n}{T} \right \rfloor\left \lfloor \frac{m}{T} \right \rfloor \sum_{d|T}\mu(\frac Td)x^k \]\(\sum_{d|T}\mu(\frac Td)x^k\)用线性筛处理，然后还是数论分块
Crash的数字表格/JZPTAB
求\(\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)\)，要求\(O(n)\)求出
\[\sum_{i=1}^{n}\sum_{j=1}^{m}\frac{ij}{gcd(i,j)} \]\[=\sum_{k=1}^n\sum_{i=1}^{n}\sum_{j=1}^{m}(gcd(i,j)==k)\frac{ij}{k} \]然后设\(i=di',j=dj'(d=gcd(i,j))\)
\[=\sum_{k=1}^n\sum_{i'=1}^{\frac nk}\sum_{j'=1}^{\frac mk}(gcd(i,j)==1)i'j'k \]化简得
\[=\sum_{k=1}^nk\sum_{d=1}^{\frac{n}{k}}\mu(d)d^2\sum_{i=1}^{\frac{n}{kd}}\sum_{j=1}^{\frac{m}{kd}}ij \]设\(g(n,m)=sum_{i=1}^n\sum_{j=1}^mij\)然后注意到
\[g(n,m)=\sum_{i=1}^n\sum_{j=1}^mij=\frac{(n+1)n}{2}·\frac{(m+1)m}{2} \]原式=
\[\sum_{k=1}^nk\sum_{d=1}^{\frac{n}{k}}\mu(d)d^2g(\frac n{kd},\frac m{kd}) \]维护\(f(k)=\sum_{d=1}^{\frac{n}{k}}\mu(d)d^2g(\frac n{kd},\frac m{kd})\)即可
[SDOI2014]数表
\[\sum_{i=1}^n\sum_{j=1}^mg(gcd(i,j)) \]\(设x=\Pi p_i^{k_i},g(x)=\Pi(k_i+1)\)即表示x的因数个数
\[=\sum_{x=1}^n\sum_{i=1}^n\sum_{j=1}^m(gcd(i,j)==x)g(x) \]\[=\sum_{x=1}^ng(x)\sum_{i=1}^{\left \lfloor \frac{n}{x} \right \rfloor}\sum_{j=1}^{\left \lfloor \frac{m}{x} \right \rfloor}(gcd(i,j)==1) \]\[=\sum_{x=1}^ng(x)\sum_{d=1}^{\frac{n}{x}}\mu(d)\left \lfloor \frac{n}{xd} \right \rfloor\left \lfloor \frac{m}{xd} \right \rfloor \]设T=xd
\[=\sum_{T=1}^n\left \lfloor \frac{n}{T} \right \rfloor\left \lfloor \frac{m}{T} \right \rfloor \sum_{d|T}\mu(d)g(\frac Td) \]然后就是预处理\(\sum_{d|T}\mu(d)g(\frac Td)\)
[SDOI2015]约数个数和
\[\sum_{i=1}^n\sum_{j=1}^mg(ij) \]\(设x=\Pi p_i^{k_i},g(x)=\Pi(k_i+1)\)即表示x的因数个数
首先要知道一个式子：\(d(ij)=\sum\limits_{x\mid i}\sum\limits_{y\mid j} [\gcd(x,y)=1]\)
标签：lfloor,right,frac,乌斯,sum,rfloor,反演,莫比,left From： https://www.cnblogs.com/zhy114514/p/18024048