QwQ 文章目前没有题目,只有理论知识
狄利克雷卷积
狄利克雷卷积(Dirichlet Convolution)在解析数论中是一个非常重要的工具.
使用狄利克雷卷积可以很方便地推出一些重要函数和公式,它在信息学竞赛和解析数论中至关重要.
狄利克雷卷积是定义在数论函数间的二元运算.
数论函数,是指定义域为 (mathbb{N})(自然数),值域为 (mathbb{C})(复数) 的一类函数,每个数论函数可以视为复数的序列.
它常见的定义式为:
big(f*gbig)(n)=sum_{xy=n}f(x)g(y)quad (x,yinmathbb{N})
]
狄利克雷卷积的一些定理
- 若 (f)、(g) 都为积性函数,那么 (f*g) 也为积性函数
设 (a)、(b) 满足 (gcd(a,b)=1),那么:
& big(f*gbig)(a) * big(f*gbig)(b) \
=&sum_{d_1|a}f(d_1)g(frac{a}{d_1}) * sum_{d_2|b}f(d_2)g(frac{b}{d_2})\
=&sum_{d_1d_2|ab}f(d_1d_2)g(frac{ab}{d_1d_2})\
=&sum_{d|ab}f(d)g(frac{ab}{d})\
=&big(f*gbig)(ab)
end{aligned}
]
因为满足 (a)、(b) 互质,我们能将 (sum_{d_1|a}sum_{d_2|b}) 合并成 (sum_{d_1d_2|ab}),所以 (f*g) 也就是积性函数了.
- 狄利克雷卷积具有交换律,即 (f*g = g*f)
&big(f*gbig)(n)\
=&sum_{xy=n}f(x)g(y)\
=&sum_{yx=n}f(y)g(x)\
=&big(g*fbig)(n)
end{aligned}
]
显而易见
- 狄利克雷卷积具有结合律,即 ((f*g)*h = f*(g*h))
&Big(big(f*gbig)*hBig)(n)\
=&sum_{wz=n}big(f*gbig)(w) h(z)\
=&sum_{wz=n}Big(sum_{xy=w}f(x)g(y)Big)h(z)\
=&sum_{xyz=n}f(x)g(y)h(z)
end{aligned}
]
&Big(f*big(g*hbig)Big)(n)\
=&sum_{xw=n}f(x)big(g*hbig)(w)\
=&sum_{xw=n}f(x)Big(sum_{yz=w}g(y)h(z)Big)\
=&sum_{xyz=n}f(x)g(y)h(z)
end{aligned}
]
如上,可知两式相等,结合律成立.
- 狄利克雷卷积具有分配律,即 ((f+g)*h = (f*h)+(g*h))
&Big(big(f+gbig)*hBig)(n)\
=&sum_{xy=n}big(f(x)+g(x)big) h(y)\
=&sum_{xy=n}f(x)h(y)+g(x)h(y)\
=&sum_{xy=n}f(x)h(y)+sum_{xy=n}g(x)h(y)\
=&big(f*hbig)(n)+big(g*hbig)(n)
end{aligned}
]
总结一下:
- 若 (f)、(g) 都为积性函数,那么 (f*g) 也为积性函数
- 狄利克雷卷积具有交换律,即 (f*g = g*f)
- 狄利克雷卷积具有结合律,即 ((f*g)*h = f*(g*h))
- 狄利克雷卷积具有分配律,即 ((f+g)*h = (f*h)+(g*h))
关于“狄利克雷卷积”名称:
首先,狄利克雷(Gustav Lejeune Dirichlet)是 19 世纪德国的数学家,他是解析数论的创立者,是解析数论很多重要理论的提出者.
“狄利克雷卷积”亦可称为“狄利克雷乘积”,如果定义普通函数加法为数论函数间的“加”运算,那么这里的狄利克雷卷积就是数论函数的“乘”运算,并且,狄利克雷卷积满足交换律、结合律和分配律,其运算法则和普通算数乘法完全类似.
函数部分(均为积性函数
单位函数(单位元)(epsilon(n))
]
显然,有:
]
因此,单位函数 (epsilon(n)) 称为狄利克雷卷积的单位元,它在狄利克雷卷积中的作用和 (1) 在普通乘法中的作用是类似的.
任何函数(包括 (epsilon))和 (epsilon) 进行狄利克雷卷积,都得到该函数本身.
这里再引入一个东西:
狄利克雷逆
我们可以把这里的“逆”和“逆元”作类比.
例如,在普通运算中,一个数的“逆元”就是这个数的倒数;
在同余运算中,一个数的“逆元”在同个模的意义下,能使得它与这个数相乘的结果与 1 同余.
分别而言,如果我们规定 (n) 的逆元是 (n^{-1})(这个符号是作为整体引入的,大多数情况下不能简单地理解为 (frac{1}{n})),那么就有这样两个式子:
(ntimes n^{-1} = 1)
(ntimes n^{-1} equiv 1 quad mod r)
数字 (1) 代表两种运算中的单位元,所以说,逆元在类似乘法的运算中起着“倒数”的地位.
在狄利克雷卷积中,单位元为 (epsilon),我们定义狄利克雷逆如下:
]
函数 (f^{-1}) 就称为函数 (f) 的狄利克雷逆.
幂函数 (Id_k(n))
]
特别的,有:
-
(k=1) 时,为恒等函数 (Id(n)),即 (Id(n)=n);
-
(k=0) 时,为常数函数 (pmb1(n)),即 (pmb1(n)=1);
这里的常数函数 (pmb 1(n)) 的函数名是加粗了的数字 (1),不要和 (1) 弄混了.
在某些场合,有人会用大写字母 (I) 来代替 (pmb 1),以防混淆,这里还是使用 (pmb 1).
除数函数 (sigma_k(n))
]
直观上理解,(sigma_k(n)) 表示 (n) 的所有因子的 (k) 次幂之和.
特别的,有:
- (k=1) 时,为因数函数 (sigma(n)),即 (sigma(n)=sum_{d|n} d);
- (k=0) 时,为个数函数 (d(n)),即 (d(n)=sum_{d|n} 1);
或者说,假设 (n) 分解为 (prod_{i=1}^m p_i^{c_i} quad (c_iin mathbb{N}^*, p_iin mathbb{P})),那么:
- (sigma(n) = prod_{i=1}^m(sum_{j=0}^{c_i} p_i^j))
- (d(n) = prod_{i=1}^m (c_i+1))
欧拉函数 (varphi(n))
在数论中,对正整数 (n),欧拉函数 (varphi(n)) 是小于或等于 (n) 的正整数中与 (n) 互质的数的数目。此函数以其首名研究者欧拉命名,它又称为 (varphi) 函数(由高斯所命名)或是欧拉总计函数(totient function,由西尔维斯特所命名)。
当 (n) 是质数的时候,显然有 (varphi(n) = n – 1).
一些性质
- 欧拉函数是积性函数
如果有 (gcd(a, b) = 1),那么 (varphi(a times b) = varphi(a) times varphi(b));
特别地,当 (n) 是奇数时 (varphi(2n) = varphi(n));
- (n = sum_{d mid n}{varphi(d)})
可以这样考虑:如果 (gcd(k, n) = d),那么 (gcd(dfrac{k}{d},dfrac{n}{d}) = 1, ( k 。
如果我们设 (f(x)) 表示 (gcd(k, n) = x) 的数的个数,那么 (n = sum_{i = 1}^n{f(i)})。
根据上面的证明,我们发现,(f(x) = varphi(dfrac{n}{x})),从而 (n = sum_{d|n}varphi(dfrac{n}{d})),所以上式化为 (n = sum_{d|n}varphi(d))。
- 若 (n = p^k),其中 (p) 是质数,那么 (varphi(n) = p^k – p^{k – 1})。
显然对于从 (1) 到 (p^k) 的所有数中,除了 (p^{k-1}) 个 (p) 的倍数以外其它数都与 (p^k) 互素,故 (varphi(p^k)=p^k-p^{k-1}=p^{k-1}times(p-1))。
那么根据 1、3 性质可得:
- 若 (n) 的分解为 (prod_{i=1}^m p_i^{c_i} quad (c_i in mathbb{N}^*, p_i in mathbb{P})),则 (varphi(n) = ntimes prod_{i=1}^m frac{p_i-1}{p_i})
证明略.
欧拉定理
若 ((a,m)=1) ,则 (a^{varphi(m)}equiv1 (text{mod} m))
扩展欧拉定理
a^{bbmod varphi(p)}&(a,p)=1\
a^b&(a,p)ne 1,b
莫比乌斯函数 (mu(n)) 与 莫比乌斯反演(Möbius Inversion)
]
或者说,若 (n) 的分解为 (prod_{i=1}^m p_i^{c_i} quad (c_i in mathbb{N}^*, p_i in mathbb{P})):
-
若 (n=1),那么 (mu(n)=1);
-
若 (exists iin[1,m]),使得 (c_i ge 2),那么 (mu(n)=0),否则 (mu(n)=(-1)^m);
一些性质
-
莫比乌斯函数为积性函数;
-
(sum_{dmid n}mu(d)=begin{cases}1&n=1\0&nneq 1\end{cases})
设 (n=prod_{i=1}^k{p_i}^{c_i},n’=prod_{i=1}^k p_i) 那么 (sum_{d|n}mu(d)=sum_{d|n’}mu(d)=sum_{i=0}^k dbinom{k}{i}cdot(-1)^i=(1+(-1))^k),根据二项式定理,易知该式子的值在 (k=0) 即 (n=1) 时值为 (1) 否则为 (0),这也同时证明了 (sum_{d|n}mu(d)=[n=1]=varepsilon(n)) 以及 (mu*1=varepsilon).
所以,莫比乌斯函数也可定义为函数 (pmb 1) 的逆,即 (mu=pmb 1^{-1}),那么就可以使用狄利克雷卷积来推导出莫比乌斯反演的结论了:
]
将其展开,即:
]
莫比乌斯反演扩展
对于数论函数 (f,g) 和完全积性函数 (t) 且 (t(1)=1):
]
常用狄利克雷卷积
(epsilon = mu*pmb1)
上文:
设 (n=prod_{i=1}^k{p_i}^{c_i},n’=prod_{i=1}^k p_i) 那么 (sum_{d|n}mu(d)=sum_{d|n’}mu(d)=sum_{i=0}^k dbinom{k}{i}cdot(-1)^i=(1+(-1))^k),根据二项式定理,易知该式子的值在 (k=0) 即 (n=1) 时值为 (1) 否则为 (0),这也同时证明了 (sum_{d|n}mu(d)=[n=1]=varepsilon(n)) 以及 (mu*1=varepsilon).
(d=pmb1*pmb1)、(sigma = Id*pmb1)
均易证,略
(Id=varphi*pmb1)、(varphi =mu*Id)
上文:
(Id(n) = n = sum_{d mid n}{varphi(d)})
可以这样考虑:如果 (gcd(k, n) = d),那么 (gcd(dfrac{k}{d},dfrac{n}{d}) = 1, ( k 。
如果我们设 (f(x)) 表示 (gcd(k, n) = x) 的数的个数,那么 (n = sum_{i = 1}^n{f(i)})。
根据上面的证明,我们发现,(f(x) = varphi(dfrac{n}{x})),从而 (n = sum_{d|n}varphi(dfrac{n}{d}))。注意到约数 (d) 和 (dfrac{n}{d}) 具有对称性,所以上式化为 (n = sum_{d|n}varphi(d))。
而因为 (mu) 是 (pmb 1) 的逆,所以 (varphi*pmb 1*mu=Id*mu=varphi)
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net