数论菜狗鼓起勇气, 学习了莫比乌斯反演之后,-- 发现自己连菜狗都不是...
一些基本的数论函数的定义
- \(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})\)
证明类似, 还请读者自行推导.
来源: http://www.bubuko.com/infodetail-3074772.html