求欧拉函数逆
Li2021
·
·
算法·理论
约定
定义
狄利克雷生成函数
对于数论函数 f，定义其狄利克雷生成函数为
\sum_i \frac{f(i)}{i^x}
我们简记为 \hat{f}(x)。
狄利克雷卷积
对于数论函数 f，g，其狄利克雷生成函数之积为两者的狄利克雷卷积的狄利克雷生成函数，即
\begin{aligned}
\hat{f}(x)\cdot \hat{g}(x)
&= \left(\sum_i\frac{f(i)}{i^x}\right)\left(\sum_i\frac{g(i)}{i^x}\right) \\
&= \sum_i\sum_j\frac{f(i)g(j)}{i^xj^x} \\
&= \sum_i\frac{1}{i^x}\sum_{d \mid i} f(d)g(\frac{i}{d}) \\
&= \sum_i\frac{h(i)}{i^x} \\
&= \hat{h}(x)
\end{aligned}
其中 h(n)=\sum\limits_{d \mid n}f(d)g(\frac{n}{d})，即 h=f*g。
性质
积性函数
如果数论函数 f 为积性函数，则其狄利克雷生成函数可以表示为
\hat{f}(s)=\sum_n\frac{f(n)}{n^s}=\prod_{p\in\mathbb{P}}\left(\sum_{t\geqslant0}\frac{f(p^t)}{p^{st}}\right)
一些例子
对于复数 s，定义黎曼 \zeta 函数为
\zeta(s)=\sum_n\frac{1}{n^s}=\sum_n\frac{1(n)}{n^s}=\hat{1}(s)
对于狄利克雷环的幺元 \varepsilon，其狄利克雷生成函数为
\hat{\varepsilon}(s)=\sum_n\frac{\varepsilon(n)}{n^s}=1=1(n)
对于莫比乌斯函数 \mu，由于 \mu*1=\varepsilon，因此其狄利克雷生成函数为
\hat{\mu}(s)=\frac{\hat{\varepsilon}(s)}{\hat{1}(s)}=\frac{1}{\zeta(s)}
对于幂函数 id_k，其狄利克雷生成函数为
\widehat{id_k}(s)=\sum_n\frac{n^k}{n^s}=\sum_n\frac{1}{n^{s-k}}=\zeta(s-k)
对于欧拉函数 \varphi，因为 \varphi * 1=id，因此其狄利克雷生成函数为
\widehat{\varphi}(s)=\frac{\hat{id}(s)}{\hat{1}(s)}=\frac{\zeta(s-1)}{\zeta(s)}
对于约数幂函数 \sigma_k，其狄利克雷生成函数为
\widehat{\sigma_k}(s)=\hat{1}(s)\cdot\hat{id_k}(s)=\zeta(s)\zeta(s-k)
对于无平方因子数（|\mu(s)|），其狄利克雷生成函数为
\widehat{u}(s)=\prod_{p\in\mathbb{P}} \left(1+\frac{1}{p}+\frac{0}{p^2}+\dots\right)=\frac{\zeta(s)}{\zeta(2s)}
求欧拉函数逆元
其实我写这篇文章的目的是解决这个。
我们需要构造一个函数 \varphi^{-1} 使得 \varphi^{-1}*\varphi=\varepsilon。
直接造显然有点困难，考虑它的狄利克雷生成函数，即
\widehat{\varphi^{-1}}(s)=\frac{\hat{\varepsilon}(s)}{\hat{\varphi}(s)}=\frac{\zeta(s)}{\zeta(s-1)}
容易发现分子部分即 \hat{1}，分母部分即 \hat{\mu}(s-1)。考虑
\hat{\mu}(s-1)=\sum_n\frac{\mu(n)}{n^{s-1}}=\sum_n\frac{n\cdot\mu(n)}{n^s}=\widehat{id\cdot\mu}(s)
则 \varphi^{-1}=1*(id\cdot\mu)。也即
\boxed{\varphi^{-1}(n)=\sum_{d\mid n}^{\text{}^\text{}}d\mu(d)}
闲话
这个做法好像可以出很多题阿。
也可能是我太菜了，连这种题都没见过。