从基础数论函数说起1：整除分块、数论函数、狄利克雷卷积

本文内容：整除分块、几种常见的数论函数和狄利克雷卷积。

整除分块

在数论相关的题中，常常会遇到带有 (lfloorfrac{n}{i} floor) 求和的式子。而考虑到有很多 (i) ，它们的 (lfloorfrac{n}{i} floor) 都是一样的（最多 (lfloor2sqrt{n} floor) 个）。所以可以在 (O(sqrt{n})) 的时间内解决（如果剩下部分可以 (O(1)) 计算的话）。可以看下面的代码：

for( int x = 1, y; x <= N; x = y + 1 ) {
    y = min( N / ( N / x ), M / ( M / x ) );
}

数论函数

定义

定义域为 正整数 的函数为 数论函数。

如果 (forall a,b，gcd(a,b)=1) ，有 (f(ab)=f(a)f(b)) ，则称这个函数是 积性函数 ，如果 (forall a, b) ，有 (f(ab)=f(a)f(b)) ，则称这个函数是 完全积性函数 。

例

单位函数 (e(n)=[n=1]) 。（当 ([]) 中值为真时，取值为 (1) ，否则为 (0) 。） 是完全积性函数。

幂函数 (id_k(n)=n^k) 。是完全积性函数。

欧拉函数 (phi(n)=sumlimits_{i=1}^n[gcd(n,i)=1]) 。是积性函数。

证明：

设 (phi(n)=n-N) ， (phi(m)=m-M) 。（即 (n) 不为 (1) 的因子有 (N) 个， (m) 不为 (1) 的因子有 (M) 个。）那么 (nm) 不为 (1) 的因子有 (nM+mN-MN) 个（容斥原理）。

即 (phi(nm)=nm-nM-mN+NM=phi(n)phi(m))

除数函数 (sigma_k(n)=sumlimits_{d|n}d^k) 。或记为 (d(n), au(n)) ，是积性函数。

证明：

由于 (gcd(n,m)=1) ，那么 (forall a|n, b|m) ，都有 (gcd(a,b)=1) 。那么 (n) 的因数乘上 (b) 的因数是 (nm) 的因数，且不会重复。所以 (sigma_k(n)sigma_k(m)=sigma_k(nm)) 。

莫比乌斯函数 (mu(n)) 。当 (n) 有平方因子的时候 (mu(n)=0) 。否则 (mu(n)=(-1)^omega(n)) 。其中 (omega(n)) 表示 (n) 不同质因子的个数。

证明平凡，略。

狄利克雷卷积（Dirichlet 卷积）

定义

两个数论函数 (f,g) 的狄利克雷卷积定义为

也可以写成这样：

性质

交换律： (f*g=g*f) 。

结合律： ((f*g)*h=f*(g*h)) 。

单位函数为单位元： (f*e=f) 。

分配律： (f*(g+h)=f*g+f*h)

当 (f) 和 (g) 都为积性函数时 (f*g) 也为积性函数。反过来， 若 (h=f*g) 为积性函数， (f) 为积性函数，那么 (g) 也为积性函数。

证明：

前面已经提到了，如果有 (gcd(n,m)=1,a|n,b|m) ，那么 (gcd(a,b)=1) 。

[egin{aligned} (f*g)(n) imes (f*g)(m) &= sumlimits_{i_1j_1=n}f(i_1)g(j_1) imes sumlimits_{i_2j_2=m}f(i_2)g(j_2)\ &= sumlimits_{i_1i_2j_1j_2=nm}f(i_1)f(i_2)g(j_1)g(j_2)\ &= sumlimits_{ij=nm}f(i)g(j)\ &= (f*g)(n) end{aligned} ]

两个等式

证明：略

证明：

若 (n) 有 (k) 个不同的质因子，那么

[sumlimits_{d|n} mu(d) = sumlimits_{i=0}^k (-1)^i imes {kchoose i} ]

根据二项式定理， ((1-1)^k= sumlimits_{i=0}^k (-1)^i imes {kchoose i}=0^k)

而由于 (mu(1)=1) ，所以 (mu * 1=e)