数论菜狗鼓起勇气，学习了莫比乌斯反演之后，——发现自己连菜狗都不是。。。

一些基本的数论函数的定义

• \(id(n)=n\)

• \(1(n)=1\)

• \(\epsilon(n)=\left\{\begin{array}{rcl}1&n=1\\0&n\neq 1\end{array}\right.\)

这几个数论函数都是完全积性函数。

（积性函数满足\(f(a\times b)=f(a)\times f(b)\)，\(gcd(a,b)=1\)，而完全积性函数满足\(f(a\times b)=f(a)\times f(b)\)，无需满足\(gcd=1\)的条件）

狄利克雷卷积

\((f*g)_{(n)}=\sum_{d|n}f(d)\times g(\frac{n}{d})\)

这东西满足交换律、结合律、分配律。

• 交换律的证明：

\((f*g)_{{n}}=\sum_{d|n}f(d)\times g(\frac{n}{d})=\sum_{d|n}f(\frac{n}{d})\times g(d)=(g*f)_{(n)}\)

• 结合律的证明：

\(((f*g)*h)_{(n)}=\sum_{d|n}h(\frac{n}{d})\sum_{k|d}f(k)\times g(\frac{d}{k})\)

\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\sum_{d|n}\sum_{k|d}f(k)\times g(\frac{d}{k})\times h(\frac{n}{d})\)

\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\sum_{k|n}\sum_{q|\frac{n}{k}}f(k)\times g(q)\times h(\frac{n}{kq})\)

\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\sum_{k|n}f(k)\sum_{q|\frac{n}{k}}g(q)\times h(\frac{n}{kq})\)

\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =(f*(g*h))_{(n)}\)

• 分配律的证明：

\((f*(g+h))_{(n)}=\sum_{d|n}f(d)\times(g(\frac{n}{d})+h(\frac{n}{d}))\)

\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\sum_{d|n}f(d)\times g(\frac{n}{d})+f(d)\times h(\frac{n}{d})\)

\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =(f*g)_{(n)}+(f*g)_{(n)}\)

• \(f*\epsilon=f\)，很简单，不证了。

\(\varphi\)函数的定义

\(\varphi (n)\)的定义为：\(1-n\) 中所有与\(n\)互质的数的个数。

\(\varphi\)的积性及证明

\(\varphi\)是一个积性函数

我们把\(1-a\times b\)这些数写成一个长方形：

\(\left(\begin{array}{cc}1&2&…&a\\a+1&a+2&…&2a\\.&.&…&.\\.&.&…&.\\.&.&…&.\\(b-1)a+1&(b-1)a+2…&…&ab\end{array}\right)\)

对于每一行：

• 因为\((a,b)=1\)所以每一行都有\(\varphi(a)\)个数与\(a\)互质。

对于每一列：

• 因为这\(b\)个数\(\%b\) 的余数互不相同，所以每一列都会有\(\varphi(a)\)个数与\(b\)互质。

综上：\(\varphi(a\times b)=\varphi(a)\times\varphi(b)\)，即\(\varphi\)为积性函数。

\(\varphi\)函数的一些性质

• 如果\(\varphi (n)\)，\(n\)是一个质数，设\(n=p^c\)，那么\(\varphi(n)=p^c-p^{c-1}\)。（不证了)

• \(\varphi(n)=n\times\prod_{i=1}^k1-\frac{1}{p_i}\)

证明：

设\(n=\prod_{i=1}^{k}p_i^{c_i}\)。

\(\varphi(n)=\prod_{i=1}^k\varphi(p_i^{c_i})\)

\(\varphi(n)=\prod_{i=1}^kp_i^{c_i}\times(1-\frac{1}{p_i})\)

\(\varphi(n)=n\times\prod_{i=1}^k1-\frac{1}{p_i}\)

证毕

• \(\varphi*1=id\)

证明：

设\(f(n)=\sum_{d|n}\varphi(d)\)。

\(\because (n,m)=1\)时

\(f(n)\times f(m)=\sum_{i|n}\varphi(i)\times\sum_{j|m}\varphi(j)\)

\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\sum_{i|n}\sum_{j|m}\varphi(i)\times \varphi(j)\)

\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\sum_{ij|nm}\varphi(ij)\)

\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =f(n\times m)\)

\(\therefore f(n)\)为积性函数。

\(f(p^c)=\sum_{d|p^c}\varphi(d)=\varphi(1)+\varphi(p)+\varphi(p^2)+…+\varphi(p^{c-1})=p^c\)

设\(n=\prod_{i=1}^{k}p_i^{c_i}\)。

\(\therefore f(n)=\prod_{i=1}^kp_i^{c_i}=n\)

即\(f=\varphi*1=id\)。

证毕

\(\varphi\)函数的求法

既然我们之前已经得出了\(\varphi\)的通项公式，那么现在就来想一想\(\varphi\)应该怎么来求吧。

听说这家伙又叫欧拉函数，那——，当然是用线性筛来求啦。

我们可以在用线筛求出质数的同时，把\(\varphi\)也给更新了。

代码：

void sieve(){
    varphi[1]=1;
    for(int i=2;i<=n;i++){
        if (!vis[i]) p[++p[0]]=i,varphi[i]=i-1;
        for (int j=1;j<=p[0]&&i*p[j]<=n;j++){
            vis[i*p[j]]=1;
            if (i%p[j]==0){
                varphi[i*p[j]]=varphi[i]*p[j];
                break;
            }
            varphi[i*p[j]]=varphi[i]*(p[j]-1);
        }
    }
}

\(\mu\)函数的定义

设\(n=\prod_{i=1}^{k}p_i^{c_i}\)。

\(\mu(n)=\left\{\begin{array}{rcl}1&n=1\\(-1)^k&\forall c_i,c_i\le1\\0&\exists c_i>1\end{array}\right.\)

\(\mu\)函数的一些性质

• \(\mu\)有积性

证明：

若\(\mu(a)=0\)或\(\mu(b)=0\)，则\(\mu(a\times b)=\mu(a)\times\mu(b)\)。

\(\because (a,b)=1 \therefore a\)的质因数，与\(b\)的质因数互不相同。

\(\therefore \mu(a\times b)=\mu(a)\times\mu(b),(a,b)=1\)

证毕

• \(\mu*1=\epsilon\)

证明：

原命题可转化为：\(\sum_{d|n}\mu(d)=[d=1]\)

设\(n\)有\(k\)个质因数。

\(\mu*1=\sum_{d|n}\mu(d)=\sum_{i=0}^k(-1)^i\times C_k^i\)

展开\(\sum\)，得到：

\(u*1=C_k^0-C_k^1+C_k^2-…(+/-)C_m^m=(1-1)^m\)，中间用了二项式定理。

\(\therefore \mu*1=\epsilon\)

证毕

• \(id*\mu=\varphi\)

证明：

两边同时卷上\(1\)。

\(\ \ \ \ \ \ id*\mu=\varphi\)

\(id*\mu*1=\varphi*1\)

\(\ \ \ \ \ \ \ \mu*1=\epsilon\)

证毕

莫比乌斯反演

若\(g(n)=\sum_{d|n}f(d)\)则\(f(n)=\sum_{d|n}\mu(d)\times g(\frac{n}{d})\)

证明：

\(f(n)=\sum_{d|n}\mu(d)\times g(\frac{n}{d})\)

\(\ \ \ \ \ \ \ \ \ =\sum_{d|n}\mu(d)\sum_{i|\frac{n}{d}}f(i)\)

\(\ \ \ \ \ \ \ \ \ =\sum_{i|n}f(i)\sum_{d|\frac{n}{i}}\mu(d)\)

\(\ \ \ \ \ \ \ \ \ =\sum_{i|n}f(i)\times (\mu*1)_{[\frac{d}{i}]}\)

\(\ \ \ \ \ \ \ \ \ =\sum_{i|n}f(i)\times\epsilon(\frac{n}{i})\)

\(\ \ \ \ \ \ \ \ \ =f(n)\)

证毕

其实还有别的形式：

\(g(n)=∑_{d|n}f(n)\)，\(f(n)=∑_{d|n}μ(d)g(\frac{n}{d})\)

证明类似，还请读者自行推导。