一、前置知识
艾佛森括号
[
P
]
=
{
1
if
P
is true
0
otherwise
[P]= \begin{cases} 1 & \text{if}\ P\ \text{is true} \\ 0 & \text{otherwise} \end{cases}
[P]={10if P is trueotherwise
其中 P P P 是一个可真可假的命题。
如 [ 114514 ≤ 1919810 ] = 1 , [ − 1 ∈ N ] = 0 [114514\le 1919810] = 1, [-1 \in \mathbb{N}] = 0 [114514≤1919810]=1,[−1∈N]=0。
二、加性函数
加性函数：对于 ∀ n , m ∈ N ∗ , gcd ( n , m ) = 1 \forall n, m \in \mathbb{N}^*, \gcd(n, m) = 1 ∀n,m∈N∗,gcd(n,m)=1，若 f ( n ) + f ( m ) = f ( n m ) f(n) + f(m) = f(nm) f(n)+f(m)=f(nm)，称函数 f f f 为加性函数；
注：此处加性函数指数论上的加性函数 ( A d d i t i v e f u n c t i o n ) (\rm Additive\ function) (Additive function)，应与代数中的加性函数 ( A d d i t i v e m a p ) (\rm Additive\ map) (Additive map) 区分。
完全加性函数：对于 ∀ n , m ∈ N ∗ \forall n, m \in \mathbb{N}^* ∀n,m∈N∗，若 f ( n ) + f ( m ) = f ( n m ) f(n) + f(m) = f(nm) f(n)+f(m)=f(nm)，称函数 f f f 为完全加性函数。完全加性函数为加性函数的一种。
对于所有的加性函数，根据 f ( 1 ) = f ( 1 × 1 ) = f ( 1 ) + f ( 1 ) f(1) = f(1\times 1) = f(1) + f(1) f(1)=f(1×1)=f(1)+f(1) 可得 f ( 1 ) = 0 f(1) = 0 f(1)=0。
加性函数 f f f 满足 f ( ∏ i = 1 k p i α i ) = ∑ i = 1 k f ( p i α i ) f\left(\prod\limits_{i=1}^k p_i^{\alpha_i}\right) = \sum\limits_{i=1}^k f(p_i^{\alpha_i}) f(i=1∏kpiαi)=i=1∑kf(piαi)，完全加性函数 f f f 满足 f ( ∏ i = 1 k p i α i ) = ∑ i = 1 k f ( p i α i ) = ∑ i = 1 k f ( p i ) ⋅ α i f\left(\prod\limits_{i=1}^k p_i^{\alpha_i}\right) = \sum\limits_{i=1}^k f(p_i^{\alpha_i}) = \sum\limits_{i=1}^k f(p_i) \cdot \alpha_i f(i=1∏kpiαi)=i=1∑kf(piαi)=i=1∑kf(pi)⋅αi。
证明时，先证明 f ( 1 ) = 0 f(1) = 0 f(1)=0。
然后证明加性需证明 gcd ( n , m ) = 1 \gcd(n,m) = 1 gcd(n,m)=1 时 f ( n ) + f ( m ) = f ( n m ) f(n) + f(m) = f(nm) f(n)+f(m)=f(nm)（废话）；
证明完全加性只需证明 f ( n ) + f ( p i ) = f ( n p i ) , p i ∈ P f(n) + f(p_i) = f(np_i), p_i\in \mathbb{P} f(n)+f(pi)=f(npi),pi∈P 即可，因为证明 f ( n ) + f ( m ) = f ( n m ) f(n) + f(m) = f(nm) f(n)+f(m)=f(nm) 可将 m m m 分解质因数再合并。
常见加性函数
-
ω ( n ) = ∑ p ∈ P [ p ∣ n ] \omega(n) = \sum\limits_{p\in \mathbb{P}} [p\mid n] ω(n)=p∈P∑[p∣n] 表示 n n n 的本质不同质因数个数
证明：
ω ( 1 ) = ∑ p ∈ P [ p ∣ 1 ] = 0 \omega(1) = \sum\limits_{p\in \mathbb{P}} [p\mid 1] = 0 ω(1)=p∈P∑[p∣1]=0
当 gcd ( n , m ) = 1 \gcd(n, m) = 1 gcd(n,m)=1 时，
ω ( n m ) = ∑ p ∈ P [ p ∣ n m ] = ∑ p ∈ P [ p ∣ n ] ∨ [ p ∣ m ] = ∑ p ∈ P [ p ∣ n ] + ∑ p ∈ P [ p ∣ m ] − ∑ p ∈ P [ p ∣ n ] ∧ [ p ∣ m ] = ∑ p ∈ P [ p ∣ n ] + ∑ p ∈ P [ p ∣ m ] − ∑ p ∈ P [ p ∣ gcd ( n , m ) ] = ∑ p ∈ P [ p ∣ n ] + ∑ p ∈ P [ p ∣ m ] − ∑ p ∈ P [ p ∣ 1 ] ( 不互质时不满足 ) = ω ( n ) + ω ( m ) − ω ( 1 ) = ω ( n ) + ω ( m ) \begin{aligned} \omega(nm) & = \sum\limits_{p\in \mathbb{P}} [p\mid nm] \\ & = \sum\limits_{p\in \mathbb{P}} [p\mid n] \lor [p\mid m] \\ & = \sum\limits_{p\in \mathbb{P}} [p\mid n] + \sum\limits_{p\in \mathbb{P}} [p\mid m] - \sum\limits_{p\in \mathbb{P}} [p\mid n] \land [p\mid m] \\ & = \sum\limits_{p\in \mathbb{P}} [p\mid n] + \sum\limits_{p\in \mathbb{P}} [p\mid m] - \sum\limits_{p\in \mathbb{P}} [p\mid \gcd(n, m)] \\ & = \sum\limits_{p\in \mathbb{P}} [p\mid n] + \sum\limits_{p\in \mathbb{P}} [p\mid m] - \sum\limits_{p\in \mathbb{P}} [p\mid 1]\ (\textsf{不互质时不满足})\\ & = \omega(n) + \omega(m) - \omega(1) \\ & = \omega(n) + \omega(m) \end{aligned} ω(nm)=p∈P∑[p∣nm]=p∈P∑[p∣n]∨[p∣m]=p∈P∑[p∣n]+p∈P∑[p∣m]−p∈P∑[p∣n]∧[p∣m]=p∈P∑[p∣n]+p∈P∑[p∣m]−p∈P∑[p∣gcd(n,m)]=p∈P∑[p∣n]+p∈P∑[p∣m]−p∈P∑[p∣1] (不互质时不满足)=ω(n)+ω(m)−ω(1)=ω(n)+ω(m) -
a 1 ( n ) = ∑ p ∈ P [ p ∣ n ] p a_1(n) = \sum\limits_{p\in \mathbb{P}} [p\mid n] p a1(n)=p∈P∑[p∣n]p 表示 n n n 的本质不同质因数和
证明：
a 1 ( 1 ) = ∑ p ∈ P [ p ∣ 1 ] p = 0 a_1(1) = \sum\limits_{p\in \mathbb{P}} [p\mid 1] p = 0 a1(1)=p∈P∑[p∣1]p=0
当 gcd ( n , m ) = 1 \gcd(n, m) = 1 gcd(n,m)=1 时，
a 1 ( n m ) = ∑ p ∈ P [ p ∣ n m ] p = ∑ p ∈ P ( [ p ∣ n ] ∨ [ p ∣ m ] ) p = ∑ p ∈ P [ p ∣ n ] p + ∑ p ∈ P [ p ∣ m ] p − ∑ p ∈ P ( [ p ∣ n ] ∧ [ p ∣ m ] ) p = a 1 ( n ) + a 1 ( m ) − a 1 ( 1 ) ( 不互质时不满足 ) = a 1 ( n ) + a 1 ( m ) \begin{aligned} a_1(nm) & = \sum\limits_{p\in \mathbb{P}} [p\mid nm] p \\ & = \sum\limits_{p\in \mathbb{P}} ([p\mid n] \lor [p\mid m]) p \\ & = \sum\limits_{p\in \mathbb{P}} [p\mid n] p + \sum\limits_{p\in \mathbb{P}} [p\mid m] p - \sum\limits_{p\in \mathbb{P}} ([p\mid n] \land [p\mid m]) p \\ & = a_1(n) + a_1(m) - a_1(1)\ (\textsf{不互质时不满足})\\ & = a_1(n) + a_1(m) \end{aligned} a1(nm)=p∈P∑[p∣nm]p=p∈P∑([p∣n]∨[p∣m])p=p∈P∑[p∣n]p+p∈P∑[p∣m]p−p∈P∑([p∣n]∧[p∣m])p=a1(n)+a1(m)−a1(1) (不互质时不满足)=a1(n)+a1(m)
常见完全加性函数
-
Ω ( n ) = ∑ p ∈ P ∑ p α ∣ n 1 ( α > 0 ) \Omega(n) = \sum\limits_{p\in \mathbb{P}} \sum\limits_{p^\alpha \mid n} 1(\alpha > 0) Ω(n)=p∈P∑pα∣n∑1(α>0) 表示 n n n 的总质因数个数
证明：
Ω ( 1 ) = ∑ p ∈ P ∑ p α ∣ 1 1 = 0 \Omega(1) = \sum\limits_{p\in \mathbb{P}} \sum\limits_{p^\alpha \mid 1} 1 = 0 Ω(1)=p∈P∑pα∣1∑1=0
首先由 p i ∈ P p_i\in \mathbb{P} pi∈P 有 Ω ( p i ) = ∑ p ∈ P ∑ p α ∣ p i 1 = 1 \Omega(p_i) = \sum\limits_{p\in \mathbb{P}} \sum\limits_{p^\alpha \mid p_i} 1 = 1 Ω(pi)=p∈P∑pα∣pi∑1=1。
Ω ( n p i ) = ∑ p ∈ P ∑ p α ∣ n p i 1 = ∑ p ∈ P ∧ p ≠ p i ∑ p α ∣ n p i 1 + ∑ p i α ∣ n p i 1 = ∑ p ∈ P ∧ p ≠ p i ∑ p α ∣ n 1 + ( ∑ p i α ∣ n 1 + 1 ) = ( ∑ p ∈ P ∧ p ≠ p i ∑ p α ∣ n 1 + ∑ p i α ∣ n 1 ) + 1 = ∑ p ∈ P ∑ p α ∣ n 1 + 1 = Ω ( n ) + Ω ( p i ) \begin{aligned} \Omega(np_i) & = \sum\limits_{p\in \mathbb{P}} \sum\limits_{p^\alpha \mid np_i} 1 \\ & = \sum\limits_{p\in \mathbb{P} \land p\ne p_i} \sum\limits_{p^\alpha \mid np_i} 1 + \sum\limits_{p_i^\alpha \mid np_i} 1 \\ & = \sum\limits_{p\in \mathbb{P} \land p\ne p_i} \sum\limits_{p^\alpha \mid n} 1 + \left(\sum\limits_{p_i^\alpha \mid n} 1 + 1\right) \\ & = \left(\sum\limits_{p\in \mathbb{P} \land p\ne p_i} \sum\limits_{p^\alpha \mid n} 1 + \sum\limits_{p_i^\alpha \mid n} 1\right) + 1 \\ & = \sum\limits_{p\in \mathbb{P}} \sum\limits_{p^\alpha \mid n} 1 + 1 \\ & = \Omega(n) + \Omega(p_i) \end{aligned} Ω(npi)=p∈P∑pα∣npi∑1=p∈P∧p=pi∑pα∣npi∑1+piα∣npi∑1=p∈P∧p=pi∑pα∣n∑1+⎝⎛piα∣n∑1+1⎠⎞=⎝⎛p∈P∧p=pi∑pα∣n∑1+piα∣n∑1⎠⎞+1=p∈P∑pα∣n∑1+1=Ω(n)+Ω(pi) -
a 0 ( n ) = ∑ p ∈ P ∑ p α ∣ n p a_0(n) = \sum\limits_{p\in \mathbb{P}} \sum\limits_{p^\alpha \mid n} p a0(n)=p∈P∑pα∣n∑p 表示 n n n 的总质因数和
证明：
a 0 ( 1 ) = ∑ p ∈ P ∑ p α ∣ 1 p = 0 a_0(1) = \sum\limits_{p\in \mathbb{P}} \sum\limits_{p^\alpha \mid 1} p = 0 a0(1)=p∈P∑pα∣1∑p=0
首先由 p i ∈ P p_i\in \mathbb{P} pi∈P 有 a 0 ( p i ) = ∑ p ∈ P ∑ p α ∣ p i p = p i a_0(p_i) = \sum\limits_{p\in \mathbb{P}} \sum\limits_{p^\alpha \mid p_i} p = p_i a0(pi)=p∈P∑pα∣pi∑p=pi。
a 0 ( n p i ) = ∑ p ∈ P ∑ p α ∣ n p i p = ∑ p ∈ P ∧ p ≠ p i ∑ p α ∣ n p i p + ∑ p i α ∣ n p i p i = ∑ p ∈ P ∧ p ≠ p i ∑ p α ∣ n p + ∑ p i α ∣ n p i + p i = ∑ p ∈ P ∑ p α ∣ n p + p i = a 0 ( n ) + a 0 ( p i ) \begin{aligned} a_0(np_i) & = \sum\limits_{p\in \mathbb{P}} \sum\limits_{p^\alpha \mid np_i} p \\ & = \sum\limits_{p\in \mathbb{P} \land p\ne p_i} \sum\limits_{p^\alpha \mid np_i} p + \sum\limits_{p_i^\alpha \mid np_i} p_i \\ & = \sum\limits_{p\in \mathbb{P} \land p\ne p_i} \sum\limits_{p^\alpha \mid n} p + \sum\limits_{p_i^\alpha \mid n} p_i + p_i \\ & = \sum\limits_{p\in \mathbb{P}} \sum\limits_{p^\alpha \mid n} p + p_i \\ & = a_0(n) + a_0(p_i) \end{aligned} a0(npi)=p∈P∑pα∣npi∑p=p∈P∧p=pi∑pα∣npi∑p+piα∣npi∑pi=p∈P∧p=pi∑pα∣n∑p+piα∣n∑pi+pi=p∈P∑pα∣n∑p+pi=a0(n)+a0(pi)
三、积性函数
积性函数：对于 ∀ n , m ∈ N ∗ , gcd ( n , m ) = 1 \forall n,m\in\mathbb{N}^*, \gcd(n, m) = 1 ∀n,m∈N∗,gcd(n,m)=1， 若 f ( n ) f ( m ) = f ( n m ) f(n)f(m)=f(nm) f(n)f(m)=f(nm)，称函数 f f f 为积性函数；
完全积性函数：对于 ∀ n , m ∈ N ∗ \forall n,m\in\mathbb{N}^* ∀n,m∈N∗，若 f ( n ) f ( m ) = f ( n m ) f(n)f(m)=f(nm) f(n)f(m)=f(nm)，称函数 f f f 为完全积性函数。完全积性函数为积性函数的一种。
对于所有的积性函数，根据 f ( 1 ) = f ( 1 × 1 ) = f ( 1 ) f ( 1 ) f(1) = f(1\times 1) = f(1)f(1) f(1)=f(1×1)=f(1)f(1) 可得 f ( 1 ) = 1 f(1)=1 f(1)=1。
注意：值恒等于 0 0 0 的函数一般不看作积性函数。
积性函数 f f f 满足 f ( ∏ i = 1 k p i α i ) = ∏ i = 1 k f ( p i α i ) f\left(\prod\limits_{i=1}^k p_i^{\alpha_i}\right) = \prod\limits_{i=1}^k f(p_i^{\alpha_i}) f(i=1∏kpiαi)=i=1∏kf(piαi)，完全积性函数 f f f 满足 f ( ∏ i = 1 k p i α i ) = ∏ i = 1 k f ( p i α i ) = ∏ i = 1 k f ( p i ) α i f\left(\prod\limits_{i=1}^k p_i^{\alpha_i}\right) = \prod\limits_{i=1}^k f(p_i^{\alpha_i}) = \prod\limits_{i=1}^k f(p_i)^{\alpha_i} f(i=1∏kpiαi)=i=1∏kf(piαi)=i=1∏kf(pi)αi。
加性函数与积性函数的互相转化
若函数 f f f 为加性函数，函数 g g g 满足 g ( n ) = C f ( n ) g(n) = C^{f(n)} g(n)=Cf(n)，其中 C C C 为常数。
首先 g ( 1 ) = C f ( 1 ) = C 0 = 1 g(1) = C^{f(1)} = C^0 = 1 g(1)=Cf(1)=C0=1；
当 gcd ( n , m ) = 1 \gcd(n, m) = 1 gcd(n,m)=1 时， g ( n ) g ( m ) = C f ( n ) + f ( m ) g(n) g(m) = C^{f(n) + f(m)} g(n)g(m)=Cf(n)+f(m)，由 f f f 为加性函数可得 C f ( n ) + f ( m ) = C f ( n m ) C^{f(n) + f(m)} = C^{f(nm)} Cf(n)+f(m)=Cf(nm)，即 g ( n ) g ( m ) = g ( n m ) g(n) g(m) = g(nm) g(n)g(m)=g(nm)，所以函数 g g g 为积性函数。
同理，当函数 f f f 为完全加性函数时，函数 g g g 为完全积性函数。
证明时，先证明 f ( 1 ) = 1 f(1) = 1 f(1)=1。
然后证明积性需证明 gcd ( n , m ) = 1 \gcd(n,m) = 1 gcd(n,m)=1 时 f ( n ) f ( m ) = f ( n m ) f(n) f(m) = f(nm) f(n)f(m)=f(nm)；
证明完全积性只需证明 f ( n ) f ( p i ) = f ( n p i ) , p i ∈ P f(n) f(p_i) = f(np_i), p_i\in \mathbb{P} f(n)f(pi)=f(npi),pi∈P 即可，因为证明 f ( n ) f ( m ) = f ( n m ) f(n) f(m) = f(nm) f(n)f(m)=f(nm) 可将 m m m 分解质因数再合并。
常见积性函数
-
常数 k k k 固定时的最大公因数 gcd ( k , n ) \gcd(k, n) gcd(k,n)
证明：
gcd ( 1 , n ) = 1 \gcd(1, n) = 1 gcd(1,n)=1
当 gcd ( n , m ) = 1 \gcd(n, m) = 1 gcd(n,m)=1 时， gcd ( k , n ) gcd ( k , m ) = gcd ( k , n m ) \gcd(k, n) \gcd(k, m) = \gcd(k, nm) gcd(k,n)gcd(k,m)=gcd(k,nm)
-
欧拉函数 φ ( n ) = ∑ i = 1 n [ gcd ( i , n ) = 1 ] \varphi(n) = \sum\limits_{i = 1}^n [\gcd(i, n) = 1] φ(n)=i=1∑n[gcd(i,n)=1]
证明：
φ ( 1 ) = ∑ i = 1 1 [ gcd ( i , 1 ) = 1 ] = 1 \varphi(1) = \sum\limits_{i = 1}^1 [\gcd(i, 1) = 1] = 1 φ(1)=i=1∑1[gcd(i,1)=1]=1
当 gcd ( n , m ) = 1 \gcd(n, m) = 1 gcd(n,m)=1 时，
φ ( n ) φ ( m ) = ∑ i = 1 n [ gcd ( i , n ) = 1 ] ∑ j = 1 m [ gcd ( j , m ) = 1 ] = ∑ i = 1 n ∑ j = 1 m [ gcd ( i , n ) = 1 ] [ gcd ( j , m ) = 1 ] = ∑ i = 1 n m [ gcd ( i , n m ) = 1 ] ( 不互质时为 ∑ i = 1 lcm ( n , m ) [ gcd ( i , lcm ( n , m ) ) = 1 ] ) = φ ( n m ) ( 不互质时为 φ ( lcm ( n , m ) ) ) \begin{aligned} \varphi(n) \varphi(m) & = \sum_{i = 1}^n [\gcd(i, n) = 1] \sum_{j = 1}^m [\gcd(j, m) = 1] \\ & = \sum_{i = 1}^n \sum_{j = 1}^m [\gcd(i, n) = 1] [\gcd(j, m) = 1] \\ & = \sum_{i = 1}^{nm} [\gcd(i, nm) = 1]\ \left(\textsf{不互质时为} \sum_{i = 1}^{\operatorname{lcm}(n, m)} [\gcd(i, \operatorname{lcm}(n, m)) = 1]\right)\\ & = \varphi(nm)\ (\textsf{不互质时为}\ \varphi(\operatorname{lcm}(n, m))) \end{aligned} φ(n)φ(m)=i=1∑n[gcd(i,n)=1]j=1∑m[gcd(j,m)=1]=i=1∑nj=1∑m[gcd(i,n)=1][gcd(j,m)=1]=i=1∑nm[gcd(i,nm)=1] ⎝⎛不互质时为i=1∑lcm(n,m)[gcd(i,lcm(n,m))=1]⎠⎞=φ(nm) (不互质时为 φ(lcm(n,m))) -
γ ( n ) = ( − 1 ) ω ( n ) \gamma(n) = (-1)^{\omega(n)} γ(n)=(−1)ω(n)
证明：
因为 ω \omega ω 为加性函数， ( − 1 ) (-1) (−1) 为常数，所以 γ \gamma γ 为积性函数。
-
莫比乌斯函数 μ ( n ) = { 1 n = 1 0 ∃ d > 1 , d 2 ∣ n γ ( n ) otherwise \mu(n) = \begin{cases} 1 & n = 1 \\ 0 & \exists d > 1, d ^ 2 \mid n \\ \gamma(n)& \text{otherwise}\end{cases} μ(n)=⎩⎪⎨⎪⎧10γ(n)n=1∃d>1,d2∣notherwise
证明：
μ ( 1 ) = 1 \mu(1) = 1 μ(1)=1
当 n , m n, m n,m 中有一者为 1 1 1 时，不妨设 n = 1 n = 1 n=1，则 μ ( n m ) = μ ( m ) = 1 ⋅ μ ( m ) = μ ( n ) μ ( m ) \mu(nm) = \mu(m) = 1\cdot \mu(m) = \mu(n) \mu(m) μ(nm)=μ(m)=1⋅μ(m)=μ(n)μ(m)；
当 ∃ d > 1 , d 2 ∣ n \exists d > 1, d^2 \mid n ∃d>1,d2∣n 时，必有 ∃ d > 1 , d 2 ∣ n m \exists d > 1, d^2 \mid nm ∃d>1,d2∣nm，则 μ ( n m ) = 0 = 0 ⋅ μ ( m ) = μ ( n ) μ ( m ) \mu(nm) = 0 = 0 \cdot \mu(m) = \mu(n) \mu(m) μ(nm)=0=0⋅μ(m)=μ(n)μ(m)；
否则，说明 μ ( n ) = γ ( n ) , μ ( m ) = γ ( m ) \mu(n) = \gamma(n), \mu(m) = \gamma(m) μ(n)=γ(n),μ(m)=γ(m)，当 gcd ( n , m ) = 1 \gcd(n, m) = 1 gcd(n,m)=1 时，由 γ ( n ) γ ( m ) = γ ( n m ) \gamma(n) \gamma(m) = \gamma(nm) γ(n)γ(m)=γ(nm) 可得 μ ( n ) μ ( m ) = μ ( n m ) \mu(n) \mu(m) = \mu(nm) μ(n)μ(m)=μ(nm)。
-
除数函数 σ k ( n ) = ∑ d ∣ n d k \sigma_k(n) = \sum\limits_{d \mid n} d^k σk(n)=d∣n∑dk，因数个数函数 d ( n ) = ∑ d ∣ n 1 = σ 0 ( n ) d(n) = \sum\limits_{d\mid n} 1 = \sigma_0(n) d(n)=d∣n∑1=σ0(n)，因数和函数 σ ( n ) = ∑ d ∣ n d = σ 1 ( n ) \sigma(n) = \sum\limits_{d\mid n} d = \sigma_1(n) σ(n)=d∣n∑d=σ1(n)。
证明：
σ k ( 1 ) = ∑ d ∣ 1 d k = 1 k = 1 \sigma_k(1) = \sum\limits_{d \mid 1} d ^ k = 1 ^ k = 1 σk(1)=d∣1∑dk=1k=1
当 gcd ( n , m ) = 1 \gcd(n, m) = 1 gcd(n,m)=1 时，
σ k ( n ) σ k ( m ) = ∑ d 1 ∣ n d 1 k ∑ d 2 ∣ m d 2 k = ∑ d 1 ∣ n ∑ d 2 ∣ m d 1 k d 2 k = ∑ d 1 ∣ n ∑ d 2 ∣ m ( d 1 d 2 ) k = ∑ d ∣ n m d k ( 不互质时不满足 ) = σ k ( n m ) \begin{aligned} \sigma_k(n) \sigma_k(m) & = \sum_{d_1\mid n} d_1^k \sum_{d_2\mid m} d_2^k \\ & = \sum_{d_1\mid n} \sum_{d_2\mid m} d_1^k d_2^k \\ & = \sum_{d_1\mid n} \sum_{d_2\mid m} (d_1 d_2)^k \\ & = \sum_{d\mid nm} d^k (\textsf{不互质时不满足}) \\ & = \sigma_k(nm) \end{aligned} σk(n)σk(m)=d1∣n∑d1kd2∣m∑d2k=d1∣n∑d2∣m∑d1kd2k=d1∣n∑d2∣m∑(d1d2)k=d∣nm∑dk(不互质时不满足)=σk(nm)
常见完全积性函数
-
刘维尔函数 λ ( n ) = ( − 1 ) Ω ( n ) \lambda(n) = (-1)^{\Omega(n)} λ(n)=(−1)Ω(n)
证明：
因为 Ω \Omega Ω 为完全加性函数， ( − 1 ) (-1) (−1) 为常数，所以 λ \lambda λ 为积性函数。
-
幂函数 Id k ( n ) = n k \operatorname{Id}_k(n) = n ^ k Idk(n)=nk，常数函数 I ( n ) I(n) I(n) 或 1 ( n ) = 1 = Id 0 ( n ) \boldsymbol{1}(n) = 1 = \operatorname{Id}_0(n) 1(n)=1=Id0(n)，恒等函数 Id ( n ) = n = Id 1 ( n ) \operatorname{Id}(n)=n = \operatorname{Id}_1(n) Id(n)=n=Id1(n)；
证明：
Id k ( 1 ) = 1 k = 1 \operatorname{Id}_k(1) = 1^k = 1 Idk(1)=1k=1
Id k ( n ) Id k ( m ) = n k m k = ( n m ) k = Id k ( n m ) \begin{aligned} \operatorname{Id}_k(n) \operatorname{Id}_k(m) & = n^k m^k \\ & = (nm)^k \\ & = \operatorname{Id}_k(nm) \end{aligned} Idk(n)Idk(m)=nkmk=(nm)k=Idk(nm) -
单位函数 ε ( n ) = [ n = 1 ] \varepsilon(n) = [n=1] ε(n)=[n=1]。
证明：
ε ( 1 ) = [ 1 = 1 ] = 1 \varepsilon(1) = [1 = 1] = 1 ε(1)=[1=1]=1
ε ( n ) ε ( m ) = [ n = 1 ] [ m = 1 ] = [ n m = 1 ] = ε ( n m ) \begin{aligned} \varepsilon(n) \varepsilon(m) & = [n = 1][m = 1] \\ & = [nm = 1] \\ & = \varepsilon(nm) \end{aligned} ε(n)ε(m)=[n=1][m=1]=[nm=1]=ε(nm)
四、线性筛
主要是常见积性函数的，加性函数是类似的。
套路是在线性筛中
void pre(int n) // 线性筛积性函数 f
{
f[1] = 1; // 注意这里，积性函数基本性质
for (int i = 2; i <= n; i++)
{
if (!vis[i])
{
p[++p[0]] = i;
f[i] = ???; //质数得直接算
}
for (int j = 1; j <= p[0] && i * p[j] <= n; j++)
{
vis[i * p[j]] = true;
if (i % p[j] == 0)
{
f[i * p[j]] = ???; // 特殊情况
break;
}
f[i * p[j]] = f[i] * f[p[j]]; // 一般情况
}
}
}
像上面一样分类，原因是当 i % p[j] == 0 ，即
p
j
∣
i
p_j\mid i
pj∣i 时有
gcd
(
i
,
p
j
)
>
1
\gcd(i, p_j) > 1
gcd(i,pj)>1，不满足积性，得单独处理；否则有
gcd
(
i
,
p
j
)
=
1
\gcd(i, p_j) = 1
gcd(i,pj)=1，则
f
(
i
)
⋅
f
(
p
j
)
=
f
(
i
⋅
p
j
)
f(i)\cdot f(p_j) = f(i\cdot p_j)
f(i)⋅f(pj)=f(i⋅pj)。
用线性筛，时间复杂度为 O ( n ) \Omicron(n) O(n)。
1. 欧拉函数
当 p ∣ n p\mid n p∣n 时 φ ( n p ) = φ ( n ) p \varphi(np) = \varphi(n) p φ(np)=φ(n)p。
void pre(int n)
{
phi[1] = 1;
for (int i = 2; i <= n; i++)
{
if (!vis[i])
{
p[++p[0]] = i;
phi[i] = i - 1;
}
for (int j = 1; j <= p[0] && i * p[j] <= n; j++)
{
vis[i * p[j]] = true;
if (i % p[j] == 0)
{
phi[i * p[j]] = phi[i] * p[j];
break;
}
phi[i * p[j]] = phi[i] * phi[p[j]];
}
}
}
2. 莫比乌斯函数
当 p ∣ n p\mid n p∣n 时 μ ( n p ) = 0 \mu(np) = 0 μ(np)=0。
void pre(int n)
{
mu[1] = 1;
for (int i = 2; i <= n; i++)
{
if (!vis[i])
{
p[++p[0]] = i;
mu[i] = -1;
}
for (int j = 1; j <= p[0] && i * p[j] <= n; j++)
{
vis[i * p[j]] = true;
if (i % p[j] == 0)
{
mu[i * p[j]] = 0;
break;
}
mu[i * p[j]] = mu[i] * mu[p[j]];
}
}
}
3. 因数个数函数
由算术基本定理得 n = ∏ i = 1 k p i α i n = \prod\limits_{i = 1}^k p_i^{\alpha_i} n=i=1∏kpiαi，那么我们知道 d ( n ) = ∏ i = 1 k ( α i + 1 ) d(n) = \prod\limits_{i = 1}^k (\alpha_i + 1) d(n)=i=1∏k(αi+1)。
设 n u m ( n ) num(n) num(n) 为 n n n 的最小质因数的次数。
-
i i i 为质数
d ( i ) = 2 d(i) = 2 d(i)=2
n u m ( i ) = 1 num(i) = 1 num(i)=1
-
p j ∤ i p_j\nmid i pj∤i
d ( i ⋅ p j ) = d ( i ) ⋅ d ( p j ) d(i\cdot p_j) = d(i) \cdot d(p_j) d(i⋅pj)=d(i)⋅d(pj)
( i ⋅ p j ) (i\cdot p_j) (i⋅pj) 的最小质因数为 p j p_j pj， n u m ( i ⋅ p j ) = 1 num(i\cdot p_j) = 1 num(i⋅pj)=1
-
p j ∣ i p_j\mid i pj∣i
此时 p j p_j pj 仍为最小质因数，故 α 1 \alpha_1 α1 增加了一， d ( i ⋅ p j ) = d ( i ) α 1 + 1 ⋅ ( α 1 + 2 ) = d ( i ) n u m ( i ) + 1 ⋅ ( n u m ( i ) + 2 ) d(i\cdot p_j) = \dfrac{d(i)}{\alpha_1 +1} \cdot (\alpha_1 + 2) = \dfrac{d(i)}{num(i) + 1} \cdot (num(i) + 2) d(i⋅pj)=α1+1d(i)⋅(α1+2)=num(i)+1d(i)⋅(num(i)+2)
n u m ( i ⋅ p j ) = n u m ( i ) + 1 num(i\cdot p_j) = num(i) + 1 num(i⋅pj)=num(i)+1
void pre(int n)
{
d[1] = 1;
for (int i = 2; i <= n; i++)
{
if (!vis[i])
{
p[++p[0]] = i;
d[i] = 2;
num[i] = 1;
}
for (int j = 1; j <= p[0] && i * p[j] <= n; j++)
{
vis[i * p[j]] = true;
if (i % p[j] == 0)
{
d[i * p[j]] = d[i] / (num[i] + 1) * (num[i] + 2);
num[i * p[j]] = num[i] + 1;
break;
}
d[i * p[j]] = d[i] * d[p[j]];
num[i * p[j]] = 1;
}
}
}
4. 因数和函数
首先 σ ( n ) = ∏ i = 1 k ∑ j = 0 α i p i j \sigma(n) = \prod\limits_{i = 1}^k \sum\limits_{j = 0}^{\alpha_i} p_i^{j} σ(n)=i=1∏kj=0∑αipij。
设 n u m ( n ) num(n) num(n) 为 n n n 的最小质因数 p 1 p_1 p1 的 ∑ i = 0 α 1 p 1 i \sum\limits_{i = 0}^{\alpha_1} p_1^i i=0∑α1p1i。
-
i i i 为质数
σ ( i ) = n u m ( i ) = i + 1 \sigma(i) = num(i) = i + 1 σ(i)=num(i)=i+1
-
p j ∤ i p_j\nmid i pj∤i
σ ( i ⋅ p j ) = σ ( i ) ⋅ σ ( p j ) \sigma(i\cdot p_j) = \sigma(i) \cdot \sigma(p_j) σ(i⋅pj)=σ(i)⋅σ(pj)
n u m ( i ⋅ p j ) = 1 + p j num(i\cdot p_j) = 1 + p_j num(i⋅pj)=1+pj
-
p j ∣ i p_j\mid i pj∣i
p 1 p_1 p1 这一项从 ∑ i = 0 α i p 1 i \sum\limits_{i = 0}^{\alpha_i} p_1^i i=0∑αip1i 变成 ∑ i = 0 α i + 1 p 1 i \sum\limits_{i = 0}^{\alpha_i + 1} p_1^i i=0∑αi+1p1i，那么将原来的集体乘 p 1 p_1 p1 再加 1 1 1 即可。
σ ( i ⋅ p j ) = σ ( i ) ∑ k = 0 α 1 p 1 k ⋅ ∑ k = 0 α 1 + 1 p 1 k = σ ( i ) n u m ( i ) ⋅ [ n u m ( i ) ⋅ p j + 1 ] \sigma(i\cdot p_j) = \dfrac{\sigma(i)}{\sum\limits_{k = 0}^{\alpha_1} p_1^k} \cdot \sum\limits_{k = 0}^{\alpha_1 + 1} p_1^k = \dfrac{\sigma(i)}{num(i)} \cdot [num(i)\cdot p_j + 1] σ(i⋅pj)=k=0∑α1p1kσ(i)⋅k=0∑α1+1p1k=num(i)σ(i)⋅[num(i)⋅pj+1]
n u m ( i ⋅ p j ) = n u m ( i ) ⋅ p j + 1 num(i\cdot p_j) = num(i) \cdot p_j + 1 num(i⋅pj)=num(i)⋅pj+1
UVA1730 Sum of MSLCM（终于有题写了
void pre(int n)
{
sigma[1] = 1;
for (int i = 2; i <= n; i++)
{
if (!vis[i])
{
p[++p[0]] = i;
sigma[i] = i + 1;
num[i] = i + 1;
}
for (int j = 1; j <= p[0] && i * p[j] <= n; j++)
{
vis[i * p[j]] = true;
if (i % p[j] == 0)
{
sigma[i * p[j]] = sigma[i] / num[i] * (num[i] * p[j] + 1);
num[i * p[j]] = num[i] * p[j] + 1;
break;
}
sigma[i * p[j]] = sigma[i] * sigma[p[j]];
num[i * p[j]] = 1 + p[j];
}
}
}
五、参考资料
- [ 1 ] [1] [1] JustinRochester：积性加性函数性质与常见积性加性函数
- [ 2 ] [2] [2] _王小呆：数学 线性筛约数个数和，约数和