数论函数（欧拉函数以及莫比乌斯反演）

AFO_WR_Eternity · 2019-05-28 19:27:33 · 个人记录

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

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

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

这几个数论函数都是积性函数，其中前三个为完全积性函数。

（积性函数满足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})=\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)}

• 一个积性函数，卷上另一个积性函数，还是积性函数。

  证明：

  设n=a\times b，(a,b)=1，f、g为两个积性函数，h=f*g。

  h(n)=\sum_{T|n}f(T)\times g(\frac nT) ~~~~~~~~~=\sum_{d_1|a,d_2|b}f(d_1)\times f(d_2)\times g(\frac{a}{d_1})\times g(\frac{b}{d_2}) ~~~~~~~~~=\sum_{d_1|a}f(d_1)\times g(\frac a{d_1})\sum_{d_2|b}f(d_2)\times g(\frac b{d_2}) ~~~~~~~~~=h(a)\times h(b)

  证毕

\varphi函数的定义

对于每一行：

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

对于每一列：

• 因为这b个数\%b 的余数互不相同，所以每一列都会有\varphi(b)个数与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)。

  $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) $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函数的一些性质

• 证明： 若$\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，得到：

  $\therefore \mu*1=\epsilon

  证毕

• id*\mu=\varphi

  证明：

  两边同时卷上1。

  \ \ \ \ \ \ id*\mu=\varphi id*\mu*1=\varphi*1 \ \ \ \ \ \ \ \mu*1=\epsilon

  证毕

• \frac{\varphi(n)}{n}=\sum_{d|n}\frac{\mu(d)}{d}

  证明：

  我们从\varphi*1=id 开始推导。

  \ \ \ \ \ \ \varphi*1=id \varphi*\mu*1=id*\mu \ \ \ \ \ \ \ \varphi*\epsilon=id*\mu \ \ \ \ \ \ \ \ \ \ \ \ \ \varphi=id*\mu

  展开后得到：

  \varphi(n)=\sum_{d|n}\mu(d)*\frac{n}{d} \ \ \frac{\varphi(n)}{n}=\sum_{d|n}\frac{\mu(d)}{d}

  证毕

莫比乌斯反演

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

证明：

证毕

其实还有别的形式：

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