一些函数的一些性质
取整函数 (lfloor x floor)
（一）(lfloor x floor <= x < lfloor x floor +1)
（二）对任意x与正整数a，b(lfloor lfloor frac{x}{a} floor /b floor=lfloor frac{x}{ab} floor)
（三）对于正整数n，1 -- n中d的倍数个数为 (lfloor frac{n}{d} floor)
（四）若n为正整数，(lfloor frac{n}{d} floor)不同取值个数不超过(2 imessqrt{n}种)
证明：
(（1）若d leq{sqrt{n}},lfloor frac{n}{d}
floor只有不超过sqrt{n}种)
(（2）若d>sqrt{n}，lfloor frac{n}{d} floor leq frac{n}{d} leq sqrt{n},lfloor frac{n}{d} floor 不超过sqrt{n}种)
(综上,lfloor frac{n}{d} floor 不超过2 imes{sqrt{n}}种)
调和数
定义 $$Hn=sumlimits_{k=1}^{n}frac{1}{k}$$运算得$$
Hn=ln(n)+r+o(1) $$其中r为欧拉马歇罗尼常数，r约为0.577 ，因此$$
sumlimits_{d=1}^{n} lfloor frac{n}{d}
floor = o(n imes{logn)} $$
素数计数函数
因此n附近素数密度近似为frac{1}{ln(n)}$$$$
第n个素数pnsim n imes{ln(n)}$$
数论函数
积性函数
完全积性函数
(若f为积性函数，) $$
n={p1{a1}} imes{p_2{a_2}} imes{p_3{a_3}}...... imes{p_s{a_s}}$$$$
f(n)=f(p_1{a_1}) imes{f(p_2{a_2})} imes{f(p_3{a_3})}...... imes{f(p_s{a_s})}$$
单位函数
除数函数
(delta_k(n)表示n因子的k次方之和)
Euler函数：(phi(n))
(Euler函数表示不超过n且与n互质的正整数个数)
性质：
证明：
(若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=sumlimits_{d|n}phi(frac{n}{d})=sumlimits_{d|n}phi(d))
Dirichlet 卷积
(f,g为数论函数，数论函数h满足) $$
h(n)=sumlimits_{d|n}f(d)g(frac{n}{d})$$
(则h为f与g的Dirichlet卷积，记为)
性质
((1)单位函数epsilon为Dirichlet卷积的单位元，即对于任意函数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 函数
(其中p_1,p_2,p_3为素数)
性质
证明：
(n=1,显然成立)
(n>1)
(设n有s个不同的素因子，由Mobius函数定义,)
(当且仅当d无平方因子的时候，mu(d)!=0)
(于是d中的每一个素因子的指数只能是0或1)
(故由二项式定理)
(得证)
Mobius变换
(设f为数论函数，定义函数g满足：)
(则称g为f的Mobius变换，f是g的Mobius逆变换)
(Dirichlet卷积) $$g=f ast 1$$
Mobius反演
(g(n)=sumlimits_{d|n}f(d)的充要条件为f(n)=sumlimits_{d|n}g(d)mu(frac{n}{d}))
证明：
得证。
应用
利用Dirichlet卷积可以解决一系列求和问题。
常用一个Dirichlet卷积替换求和式中的一部分，然后调换求和顺序，最终降低时间复杂度。
常用：
(mu ast 1= epsilon)
(Id = 1 ast phi)