一些函数的一些性质
取整函数 \(\lfloor x \rfloor\)
(一)\(\lfloor x \rfloor <= x <\lfloor x \rfloor +1\)
(二) 对任意 x 与正整数 a,b\(\lfloor \lfloor \frac{x}{a} \rfloor /b\rfloor=\lfloor \frac{x}{ab}\rfloor\)
(三) 对于正整数 n,1 -- n 中 d 的倍数个数为 \(\lfloor \frac{n}{d} \rfloor\)
(四) 若 n 为正整数,\(\lfloor \frac{n}{d}\rfloor\) 不同取值个数不超过 \(2\times\sqrt{n} 种 \)
证明:
\((1) 若 d \leq{\sqrt{n}},\lfloor \frac{n}{d}\rfloor 只有不超过 \ sqrt{n} 种 \)
\((2) 若 d>\sqrt{n},\lfloor \frac{n}{d} \rfloor \leq \frac{n}{d} \leq \sqrt{n},\lfloor \frac{n}{d}\rfloor 不超过 \ sqrt{n} 种 \)
\(综上,\lfloor \frac{n}{d}\rfloor 不超过 2\times{\sqrt{n}} 种 \)
调和数
定义 \[Hn=\sum\limits_{k=1}^{n}\frac{1}{k}\] 运算得 \[ Hn=ln(n)+r+o(1) \] 其中 r 为欧拉马歇罗尼常数, r 约为 0.577 , 因此 \[ \sum\limits_{d=1}^{n} \lfloor \frac{n}{d}\rfloor = o(n\times{logn)} \]
素数计数函数
\[ \pi(n)\sim \frac{n}{ln (n)}\]\[ 因此 n 附近素数密度近似为 \ frac{1}{ln(n)}\]\[ 第 n 个素数 pn\sim n\times{ln(n)}\]
数论函数
积性函数
\[ f 为数论函数, 对互质的正整数 a,b,f(a\times{b})=f(a)\times{f(b})\]
完全积性函数
\[ f 为数论函数, 对任意的正整数 a,b,f(a\times{b})=f(a)\times{f(b})\]
\(若 f 为积性函数,\) \[ n=p1^{a1}\times{p_2^{a_2}}\times{p_3^{a_3}}......\times{p_s^{a_s}}\]\[ f(n)=f(p_1^{a_1})\times{f(p_2^{a_2})}\times{f(p_3^{a_3})}......\times{f(p_s^{a_s})}\]
单位函数
\[\epsilon(n)=[n==1]= \left\{ \begin{aligned} 1&,n=1\ 0&,n!=1\\end{aligned} \right. \]
除数函数
\(\delta_k(n) 表示 n 因子的 k 次方之和 \)
\[ \delta_k(n)=\sum\limits_{d|n}d^k\]
Euler 函数:\(\phi(n)\)
\(Euler 函数表示不超过 n 且与 n 互质的正整数个数 \)
性质:
\[ n=\sum\limits_{d|n}\phi(d) \]
证明:
\(若 gcd(n,i)=d,gcd(\frac{n}{d},\frac{i}{d})=1\)
\(其中 \ frac{i}{d} 是不超过 \ frac{n}{d} 的整数, 由欧拉函数的定义, i 的个数为 \ phi(\frac{n}{d}) 个 \)
\(对于所有的 d|n,n=\sum\limits_{d|n}\phi(\frac{n}{d})=\sum\limits_{d|n}\phi(d)\)
Dirichlet 卷积
- \(f,g 为数论函数, 数论函数 h 满足 \) \[ h(n)=\sum\limits_{
- d|n
- }f(d)g(\frac{
- n
- }{
- d
- })\]
- \(则 h 为 f 与 g 的 Dirichlet 卷积, 记为 \)
- \[h=f \ast g\]
性质
\((1) 单位函数 \ epsilon 为 Dirichlet 卷积的单位元, 即对于任意函数 f, 有 \)
\[\epsilon \ast f=f \ast \epsilon =f\]
\((2) 满足交换律和结合律 \)
\((3) 若 f,g 为积性函数, f \ast g 也为积性函数 \)
\((4) 逆函数: f \ast f_逆 =\epsilon\)
- \(定义幂函数: Id_k(n)=n^k,Id=Id_1\)
- \(所以除数函数: \delta_k=1 \ast Id_k\)
- \(Euler 函数: \phi(n) = 1 \ast Id\)
计算 Dirichlet 卷积:
- \(f,g 为数论函数, 则 f \ast g 在 n 处的值需要枚举 n 的所有约数 \)
- \(计算 f \ast g 的前 n 项, 枚举 1 到 n 中每个数的倍数 \)
Mobius 函数
- \[\mu(n)= \left\{
- \begin{
- aligned
- } &1&n=1 \&(-1)^s&n=p_1\times{
- p_2
- }\times{
- p_3
- }......\times{
- p_s
- }\&0&otherwise \\end{
- aligned
- } \right. \]
- \(其中 p_1,p_2,p_3 为素数 \)
性质
\[\sum\limits_{d|n}\mu(n)= \epsilon(n) \Rightarrow \mu \ast 1 = \epsilon\]
证明:
- \(n=1, 显然成立 \)
- \(n>1\)
- \(设 n 有 s 个不同的素因子, 由 Mobius 函数定义,\)
- \(当且仅当 d 无平方因子的时候,\mu(d)!=0\)
- \(于是 d 中的每一个素因子的指数只能是 0 或 1\)
- \(故由二项式定理 \)
- \[\sum\limits_{
- d|n
- }\mu(d)=\sum\limits_{
- k=0
- }^s (-1)^k(s,k)=(1-1)^s=0\]
- \(得证 \)
Mobius 变换
- \(设 f 为数论函数, 定义函数 g 满足:\)
- \[g(n)=\sum\limits_{
- d|n
- }f(d)\]
- \(则称 g 为 f 的 Mobius 变换, f 是 g 的 Mobius 逆变换 \)
- \(Dirichlet 卷积 \) \[g=f \ast 1\]
Mobius 反演
\(g(n)=\sum\limits_{d|n}f(d) 的充要条件为 f(n)=\sum\limits_{d|n}g(d)\mu(\frac{n}{d})\)
证明:
- \[g=f \ast 1\]
- \[f=f \ast \epsilon =f \ast 1 \ast \mu =g \ast \mu\]
得证.
应用
利用 Dirichlet 卷积可以解决一系列求和问题.
常用一个 Dirichlet 卷积替换求和式中的一部分, 然后调换求和顺序, 最终降低时间复杂度.
常用:
- \(\mu \ast 1= \epsilon\)
- \(Id = 1 \ast \phi\)
来源: http://www.bubuko.com/infodetail-3257609.html