哇，我复活啦
高考炸了，低于100分的数学让我被迫苟近了中大
然后就被“邀请”去参加acm选拔赛了。
康复训练效果感觉不佳啊，tarjan都快忘了，更别提什么网络流min25多项式之类的了。
靠着切切水题混着看了。
复习了一下杜教筛，就拿这个来当个重启的契机吧。
原博客地址
补充几个小小的有用的性质：
1
、
μ
∗
I
=
ϵ
1、\mu * I=\epsilon
1、μ∗I=ϵ
2
、
φ
∗
I
=
i
d
2、φ*I=id
2、φ∗I=id
3
、
μ
∗
i
d
=
φ
3、\mu * id=φ
3、μ∗id=φ
4
、
∑
d
∣
n
μ
(
d
)
d
=
φ
(
n
)
n
4、\sum_{d|n}\frac{\mu(d)}{d}=\frac{φ(n)}{n}
4、∑d∣ndμ(d)=nφ(n)
证明：
1
、
μ
∗
I
=
∑
d
∣
n
μ
(
d
)
1、\mu*I=\sum_{d|n}\mu(d)
1、μ∗I=∑d∣nμ(d)
那么如果n不为1，那么必然可以分为多个不同的质因数。
然后观察
μ
\mu
μ的计算公式：
那么
m
=
1
、
2
、
3
、
4
…
m=1、2、3、4…
m=1、2、3、4…时，那么不就是组合数中的交替正负号然后求和吗。
于是乎就可以知道只有当
n
=
1
n=1
n=1时原式等于1，其余都为0。
2
、
φ
∗
I
=
∑
d
∣
n
φ
(
d
)
2、φ*I=\sum_{d|n}φ(d)
2、φ∗I=∑d∣nφ(d)
φ
(
n
)
φ(n)
φ(n)的意义是1到n-1中与n互质的数的个数。
首先我们看当
n
=
p
q
（
p
为某质数）
n=p^q（p为某质数）
n=pq（p为某质数）时会发生什么：
∑
d
∣
n
φ
(
d
)
=
φ
(
1
)
+
φ
(
p
)
+
φ
(
p
2
)
+
…
+
φ
(
p
q
)
\sum_{d|n}φ(d)=φ(1)+φ(p)+φ(p^2)+…+φ(p^q)
∑d∣nφ(d)=φ(1)+φ(p)+φ(p2)+…+φ(pq)
=
1
+
(
p
−
1
)
+
(
p
2
−
p
)
+
…
…
+
(
p
q
−
p
q
−
1
)
=
p
q
=1+(p-1)+(p^2-p)+……+(p^q-p^{q-1})=p^q
=1+(p−1)+(p2−p)+……+(pq−pq−1)=pq
然后如果
n
=
Π
p
i
q
i
n=\Pi p_i^{q_i}
n=Πpiqi
那么由于
φ
(
n
)
φ(n)
φ(n)是积性函数，根据狄利克雷卷积性质，那么
φ
(
n
)
∗
I
φ(n)*I
φ(n)∗I也是积性函数，那么我们就可以分成：
(
φ
∗
I
)
(
Π
p
i
q
i
)
=
Π
(
φ
∗
I
)
(
p
i
q
i
)
(φ*I)(\Pi p_i^{q_i})=\Pi(φ*I)(p_i^{q_i})
(φ∗I)(Πpiqi)=Π(φ∗I)(piqi)
那么就和上面的同理了。
3
、
μ
∗
i
d
=
∑
d
∣
n
μ
(
d
)
∗
n
d
3、\mu * id=\sum_{d|n}\mu(d)*\frac{n}{d}
3、μ∗id=∑d∣nμ(d)∗dn
当n为质数时，那么
原式
=
μ
(
1
)
∗
n
+
μ
(
n
)
∗
1
=
n
−
1
=
φ
(
n
)
原式=\mu(1)*n+\mu(n)*1=n-1=φ(n)
原式=μ(1)∗n+μ(n)∗1=n−1=φ(n)
如果n可以表达成：
n
=
p
q
n=p^q
n=pq，那么
原式
=
μ
(
1
)
∗
n
+
μ
(
p
)
∗
p
q
−
1
+
…
+
μ
(
p
q
)
∗
1
原式=\mu(1)*n+\mu(p)*p^{q-1}+…+\mu(p^q)*1
原式=μ(1)∗n+μ(p)∗pq−1+…+μ(pq)∗1
可以发现中间的项都为0。于是原式化简为：
μ
(
1
)
∗
n
+
μ
(
p
)
∗
p
q
−
1
=
n
−
p
q
−
1
=
φ
(
n
)
\mu(1)*n+\mu(p)*p^{q-1}=n-p^{q-1}=φ(n)
μ(1)∗n+μ(p)∗pq−1=n−pq−1=φ(n)
如果n可以表达成：
n
=
Π
p
i
q
i
n=\Pi p_i^{q_i}
n=Πpiqi那么类似于第二条性质一样，拆开即可。
4
、
∑
d
∣
n
μ
(
d
)
d
=
φ
(
n
)
n
4、\sum_{d|n}\frac{\mu(d)}{d}=\frac{φ(n)}{n}
4、∑d∣ndμ(d)=nφ(n)
两边同时乘一个n试试？
关于单位元
由于之前并没有仔细研究单位元。
又看到
ϵ
(
n
)
=
[
n
=
=
1
]
\epsilon(n)=[n==1]
ϵ(n)=[n==1]被称为狄利克雷卷积的单位元。
小证一下？
(
f
∗
ϵ
)
(
n
)
=
∑
d
∣
n
f
(
d
)
∗
ϵ
(
n
d
)
=
f
(
n
)
(f*\epsilon)(n)=\sum_{d|n}f(d)*\epsilon(\frac{n}{d})=f(n)
(f∗ϵ)(n)=∑d∣nf(d)∗ϵ(dn)=f(n)
挺显然的
有什么用呢？
关于逆元
既然我们知道了
f
(
n
)
f(n)
f(n)的单位元是
ϵ
(
n
)
\epsilon(n)
ϵ(n)
那么我们可以找到一个函数
g
(
n
)
g(n)
g(n)使得：
(
f
∗
g
)
(
n
)
=
ϵ
(
n
)
(f*g)(n)=\epsilon(n)
(f∗g)(n)=ϵ(n)
那么这个
g
(
n
)
g(n)
g(n)便是
f
(
n
)
f(n)
f(n)的逆元。
怎么找呢？
(
f
∗
g
)
(
1
)
=
∑
d
∣
1
f
(
d
)
∗
g
(
1
d
)
=
f
(
1
)
∗
g
(
1
)
=
1
(f*g)(1)=\sum_{d|1}f(d)*g(\frac 1 d)=f(1)*g(1)=1
(f∗g)(1)=∑d∣1f(d)∗g(d1)=f(1)∗g(1)=1
那么按理来讲，我们可以直接令
g
(
1
)
=
1
f
(
1
)
g(1)=\frac 1{f(1)}
g(1)=f(1)1
其他呢？
(
f
∗
g
)
(
2
)
=
∑
d
∣
2
f
(
d
)
∗
g
(
2
d
)
=
f
(
1
)
∗
g
(
2
)
+
f
(
2
)
∗
g
(
1
)
=
f
(
1
)
∗
g
(
2
)
+
f
(
2
)
f
(
1
)
=
0
(f*g)(2)=\sum_{d|2}f(d)*g(\frac 2 d)=f(1)*g(2)+f(2)*g(1)=f(1)*g(2)+\frac{f(2)}{f(1)}=0
(f∗g)(2)=∑d∣2f(d)∗g(d2)=f(1)∗g(2)+f(2)∗g(1)=f(1)∗g(2)+f(1)f(2)=0
那么
g
(
2
)
=
−
f
(
2
)
(
f
(
1
)
)
2
g(2)=-\frac{f(2)}{(f(1))^2}
g(2)=−(f(1))2f(2)
同理：
(
f
∗
g
)
(
3
)
=
∑
d
∣
3
f
(
d
)
∗
g
(
3
d
)
=
f
(
1
)
∗
g
(
3
)
+
f
(
3
)
∗
g
(
1
)
=
f
(
1
)
∗
g
(
3
)
+
f
(
3
)
f
(
1
)
=
0
(f*g)(3)=\sum_{d|3}f(d)*g(\frac 3 d)=f(1)*g(3)+f(3)*g(1)=f(1)*g(3)+\frac{f(3)}{f(1)}=0
(f∗g)(3)=∑d∣3f(d)∗g(d3)=f(1)∗g(3)+f(3)∗g(1)=f(1)∗g(3)+f(1)f(3)=0
g
(
3
)
=
−
f
(
3
)
(
f
(
1
)
)
2
g(3)=-\frac{f(3)}{(f(1))^2}
g(3)=−(f(1))2f(3)
(
f
∗
g
)
(
4
)
=
∑
d
∣
4
f
(
d
)
∗
g
(
4
d
)
=
f
(
1
)
∗
g
(
4
)
+
f
(
2
)
∗
g
(
2
)
+
f
(
4
)
∗
g
(
1
)
=
f
(
1
)
∗
g
(
4
)
−
(
f
(
2
)
)
2
(
f
(
1
)
)
2
+
f
(
4
)
f
(
1
)
=
0
(f*g)(4)=\sum_{d|4}f(d)*g(\frac 4 d)=f(1)*g(4)+f(2)*g(2)+f(4)*g(1)=f(1)*g(4)-\frac{(f(2))^2}{(f(1))^2}+\frac{f(4)}{f(1)}=0
(f∗g)(4)=∑d∣4f(d)∗g(d4)=f(1)∗g(4)+f(2)∗g(2)+f(4)∗g(1)=f(1)∗g(4)−(f(1))2(f(2))2+f(1)f(4)=0
g
(
4
)
=
−
f
(
4
)
(
f
(
1
)
)
2
+
(
f
(
2
)
)
2
(
f
(
1
)
)
3
g(4)=-\frac{f(4)}{(f(1))^2}+\frac{(f(2))^2}{(f(1))^3}
g(4)=−(f(1))2f(4)+(f(1))3(f(2))2
归根结底来看，我们可以总结为这条式子：
g
(
n
)
=
{
1
f
(
1
)
n
=
1
−
1
f
(
1
)
∗
∑
d
∣
n
d
!
=
1
f
(
d
)
∗
g
(
n
d
)
n
>
1
g(n)=\begin{cases} \frac 1{f(1)} & n=1 \\ -\frac 1 {f(1)} *\sum_{d|n\ d!=1}f(d)*g(\frac n d) & n>1 \\ \end{cases}
g(n)={f(1)1−f(1)1∗∑d∣n d!=1f(d)∗g(dn)n=1n>1
其中还能发现：只有
f
(
1
)
f(1)
f(1)不为0时有其逆元。文章来源：https://www.toymoban.com/news/detail-405889.html
有什么用？文章来源地址https://www.toymoban.com/news/detail-405889.html
到了这里，关于复活小记？的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
