莫比乌斯反演

莫比乌斯反演

补了补暑假欠下的账（你怎么寒假才学）

推狮子 >> 写代码。

数论函数：定义域为正整数的函数。

积性函数，对于一个数论函数，任意两个互质的正整数 \(x,y\) ，都有 \(f(xy)=f(x)f(y)\)

完全积性函数就是不要求 \(x,y\) 互质的积性函数。

常见的积性函数：

单位函数 \(\epsilon (n)=[n=1]\)

常数函数 \(1(n)=1\)

恒等函数 \(id_k(n)=n^k\) ，当 \(k=1\) 的时候常记做 \(id(n)\)

除数函数 \(\sigma_k(n)=\displaystyle\sum_{d|n} d^k\) ，当 \(k=0\) 时为约数个数记作 \(d(n)\)，\(k=1\) 时为约数个数和记作 \(\sigma (n)\)

欧拉函数 \(\varphi (n)=\displaystyle\sum_{i=1}^{i=n}[gcd(i,n)=1]\)

莫比乌斯函数 $\mu (n)=\begin{array}{l}
\left{\begin{matrix}
0 \ \ \ \ \ \ \ \ \ \ \ \ \ \exists d>1,d^2|n\
{-1}^{w(n)} \ \ \ \ \ \ \ otherwise \
\end{matrix}\right.
\end{array} $

\(w(n)\) 表示本质不同质因子个数。

狄利克雷卷积：数论函数 \(f,g,h\)

\(f_n=\displaystyle\sum_{d|n}g(d)h(\frac{n}{d})\)

不难看出该卷积有结合律，交换律，分配律。

根据性质有：\(\mu \ast 1 =\epsilon, \varphi \ast 1=id\)

如何快速的求 \(\varphi ,\mu\)？

写出卷积狮子，转化为矩阵形式，再用矩阵求个逆即可。（bushi

线性筛的时候顺带求一下即可。

黑科技：如何线性求两个积性函数？

常见方法是手动算素数的幂次，但其实可以直接暴力卷起来。

为啥复杂度是对的呢？这里空间有的小，不太好证明。可以右转 EI 博客。

设 \(f=g \ast h\)

$f (n)=\begin{array}{l}
\left{\begin{matrix}
f(p^k)f(c) \ \ \ \ \ \ \ \ \ \ \ \ c>1,p^kc\
\displaystyle\sum_{d=0}^{k}g(pd)h(p^{k-d}) \ \ \ \ \ p^k \ \end{matrix}\right.
\end{array} $

开始推狮子：

\(\displaystyle\sum_{i=1}^{i=n}\displaystyle\sum_{j=1}^{j=m}gcd(i,j)\)

\(=\displaystyle\sum_{i=1}^{i=n}\displaystyle\sum_{j=1}^{j=m} \displaystyle\sum_{k=1}^{min(n,m)}[gcd(i,j)=k]\)

\(=\displaystyle\sum_{k=1}^{min(n,m)}\displaystyle\sum_{i=1}^{\lfloor \frac{n}{k} \rfloor} \displaystyle\sum_{j=1}^{\lfloor \frac{m}{k} \rfloor} [gcd(i,j)=1]\)

\(=\displaystyle\sum_{k=1}^{min(n,m)}\displaystyle\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \displaystyle\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} \displaystyle\sum_{d|n} \mu(d)\)

$=\displaystyle\sum_{k=1}^{{min(n,m)}\displaystyle\sum_{d=1}}\rfloor,\lfloor \frac{m}{k} \rfloor)}\mu(d) \displaystyle\sum_{i=1}^{\lfloor \frac{n}{kd} \rfloor} \displaystyle\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor}1 $

$=\displaystyle\sum_{k=1}^{{min(n,m)}\displaystyle\sum_{d=1}}\rfloor,\lfloor \frac{m}{k} \rfloor)}\mu(d) \lfloor \frac{n}{kd} \rfloor \lfloor \frac{m}{kd} \rfloor $

设 \(T=kd\) ，那么有：

\(=\displaystyle\sum_{T=1}^{min(n,m)} \lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor \displaystyle\sum_{d|n}\mu(d)\ast id(\frac{n}{d})\)

套用整除分块做到 \(O(n)-O(\sqrt n)\)

公式貌似有点炸，我还是先去首推去了