[学习笔记] 数论函数(欧拉函数以及莫比乌斯反演)

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

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

  • (id(n)=n)

  • (1(n)=1)

  • (epsilon(n)=left{egin{array}{rcl}1&n=1\0&n eq 1end{array} ight.)

  • (d(n)=sum_{d|n}1)

  • (sigma(n)=sum_{d|n}d)

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

(积性函数满足(f(a imes b)=f(a) imes f(b))(gcd(a,b)=1),而完全积性函数满足(f(a imes b)=f(a) imes f(b)),无需满足(gcd=1)的条件)


狄利克雷卷积

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

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


  • 交换律的证明:

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


  • 结合律的证明:

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

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

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

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

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


  • 分配律的证明:

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

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

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


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

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

    证明:

    (n=a imes b)((a,b)=1)(f)(g)为两个积性函数,(h=f*g)

    (h(n)=sum_{T|n}f(T) imes g(frac nT))

    (~~~~~~~~~=sum_{d_1|a,d_2|b}f(d_1) imes f(d_2) imes g(frac{a}{d_1}) imes g(frac{b}{d_2}))

    (~~~~~~~~~=sum_{d_1|a}f(d_1) imes g(frac a{d_1})sum_{d_2|b}f(d_2) imes g(frac b{d_2}))

    (~~~~~~~~~=h(a) imes h(b))

    证毕


(varphi)函数的定义

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


(varphi)的积性及证明

(varphi)是一个积性函数

我们把(1-a imes b)这些数写成一个长方形:

(left(egin{array}{cc}1&2&...&a\a+1&a+2&...&2a\.&.&...&.\.&.&...&.\.&.&...&.\(b-1)a+1&(b-1)a+2...&...&abend{array} ight))

对于每一行:

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

对于每一列:

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

综上:(varphi(a imes b)=varphi(a) imesvarphi(b)),即(varphi)为积性函数。

(varphi)函数的一些性质

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

  • (varphi(n)=n imesprod_{i=1}^k1-frac{1}{p_i})

    证明:

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

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

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

    (varphi(n)=n imesprod_{i=1}^k1-frac{1}{p_i})

    证毕


  • (varphi*1=id)

    证明:

    (f(n)=sum_{d|n}varphi(d))

    (ecause (n,m)=1)

    (f(n) imes f(m)=sum_{i|n}varphi(i) imessum_{j|m}varphi(j))

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

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

    ( =f(n imes m))

    ( herefore 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})

    ( herefore 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{egin{array}{rcl}1&n=1\(-1)^k&forall c_i,c_ile1\0&exists c_i>1end{array} ight.)

(mu)函数的一些性质

  • (mu)有积性

    证明:

    (mu(a)=0)(mu(b)=0),则(mu(a imes b)=mu(a) imesmu(b))

    (ecause (a,b)=1 herefore a)的质因数,与(b)的质因数互不相同。

    ( herefore mu(a imes b)=mu(a) imesmu(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 imes C_k^i)

    展开(sum),得到:

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

    ( herefore 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) imes g(frac{n}{d}))

证明:

(f(n)=sum_{d|n}mu(d) imes 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) imes (mu*1)_{[frac{d}{i}]})

( =sum_{i|n}f(i) imesepsilon(frac{n}{i}))

( =f(n))

证毕

其实还有别的形式:

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

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

原文地址:https://www.cnblogs.com/WR-Eternity/p/10939746.html