积性函数

定义

若 \(\gcd(x,y) = 1\) 且 \(f(xy)=f(x)f(y)\)，则 \(f(n)\) 为积性函数。

性质

若 \(f(x)\)，\(g(x)\)均为积性函数，则以下函数也为积性函数：

\[\begin{aligned} & h(x) = f(x^p)\\ & h(x) = f^p(x)\\ & h(x) = f(x)g(x)\\ & h(x) = \sum_{d\mid x} f(d)g(\dfrac{x}{d}) \end{aligned}\]

常见积性函数

单位函数 \(e(n) = [n = 1]\)。
幂函数 \(\operatorname{Id}_{k}(n) = n^k\)， \(\operatorname{id}_1(n)\) 通常简记为\(\operatorname{id}(n)\)。
常数函数 \(1(n) = 1\)。
因数个数 \(\operatorname{d}(n) = \sum\limits_{d\mid n} 1\)。
除数函数 \(\sigma_{k}(n) = \sum\limits_{d\mid n} d^k\)。
\(k=1\) 时为因数和函数，通常简记为 \(\sigma(n)\)。
\(k=0\) 时为因数个数函数 \(\sigma_{0}(n)\)。
欧拉函数 \(\varphi(n) = \sum\limits_{i=1}^{n} [\gcd(i,n) = 1]\)。
莫比乌斯函数 \(\mu(n) = \begin{cases}1 &n=1\\0 &n\ \text{含有平方因子}\\(-1)^k &k\text{为}\ n\ \text{的本质不同质因子个数} \end{cases}\)

不是很懂上面写的什么玩意？
不用深究，有个印象继续往下看就好。

莫比乌斯函数

定义

\(\mu\) 为莫比乌斯函数，定义为

\[\mu(n) = \begin{cases} 1 &n=1\\0 &n\ \text{含有平方因子}\\(-1)^k &k\text{为}\ n\ \text{的本质不同质因子个数} \end{cases}\]

解释

令 \(n = \prod\limits_{i=1}^{k} p_{i}^{c_i}\)，其中\(p_i\)为质因子，\(c_i\ge 1\)。

\(n=1\)时，\(\mu (n) = 1\)。
\(n\not ={1}\)时，
- \(\exist i\in [1,k], c_i > 1\) 时，\(\mu (n) = 0\)。
  当某质因子出现次数大于\(1\)时，\(\mu (n) = 0\)。
- \(\forall i\in [1,k], c_i = 1\) 时，\(\mu (n) = (-1)^k\)。
  当每个质因子只出现一次时，即\(n = \prod\limits_{i=1}^{k}p_i\)，\(\{p_i\}\)中元素唯一。
  \(\mu (n) = (-1)^k\)，此处\(k\)为质因子的种类数。

性质

莫比乌斯函数是积性函数，且具有以下性质

\[\large \sum_{d\mid n} \mu (d) = [n=1] \]

证明，设 \(n = \prod\limits_{i=1}^{k}{p_i^{c_i}}, n' = \prod\limits_{i=1}^{k}{p_i}\)。

根据莫比乌斯函数定义，则有：\(\sum\limits_{d\mid n}{\mu(d)} = \sum\limits_{d\mid n'}{\mu(d)}\)。
若 \(n'\) 的某因子 \(d\)，有 \(\mu (d) = (-1)^i\)，则它由 \(i\) 个本质不同的质因子组成。
由于质因子总数为 \(k\)，满足上式的因子数为 \(C_{k}^{i}\)。
对于原求和式，转为枚举 \(\mu(d)\) 的值。
则 \(\sum\limits_{d\mid n'}{\mu(d)} = \sum\limits_{i=0}^{k}{C_{k}^{i} \times (-1)^i} = \sum\limits_{i=0}^{k}{C_{k}^{i} \times (-1)^i\times 1^{k-i}}\)
根据二项式定理，上式 \(= (1+(-1))^k\)，
易知该式在 \(k=0\)，即 \(n=0\) 时为 \(1\)，否则为 \(0\)。

补充结论

反演结论:

\[[\gcd(i,j) = 1] \iff \sum\limits_{d\mid \gcd(i,j)} {\mu (d)} \]

证明 1：
设 \(n = \gcd(i,j)\)，则右\(= \sum\limits_{d\mid n} {\mu (d)} = [n = 1] = [\gcd(i,j) = 1]=\) 左。

证明 2：
暴力展开：\([\gcd(i,j) = 1] = e(\gcd(i,j)) = \sum\limits_{d\mid \gcd(i,j)}\mu(d)\)

线性筛求莫比乌斯函数

\(\mu\) 为积性函数，因此可以线性筛莫比乌斯函数。

int cnt, Mobius[kMaxn], Prime[kMaxn];
bool vis[kMaxn];

void GetMobius() {
  Mobius[1] = 1;
  for (int i = 2; i <= n; i ++) {
    if (!vis[i]) Mobius[i] = - 1, Prime[++ cnt] = i;
    for (int j = 1; j <= cnt && i * Prime[j] <= n; j ++) {
      vis[i * Prime[j]] = true;
      if (i % Prime[j] == 0) break;
      Mobius[i * Prime[j]] = - Mobius[i];
    }
  }
}

狄利克雷(Dirichlet)卷积

建议阅读算法学习笔记(35): 狄利克雷卷积 By: Pecco。

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

\[\large(f\ast g) (n) = \sum_{d\mid n} f(d)g(\dfrac{n}{d}) \]

性质

显然满足交换律，结合律，分配律。
- \(f \ast g = g \ast f\)
- \((f \ast g) \ast h = f\ast (g\ast h)\)
- \(f\ast (g+h) = f\ast g + f\ast h\)
\(e\) 为狄利克雷卷积的单位元，有\((f\ast e)(n) = f(n)\)。
若 \(f,g\) 为积性函数，则 \(f\ast g\) 为积性函数。

关于单位元 \(e\)

有：

\[e = \mu \ast 1=\sum\limits_{d\mid n} \mu (d) \]

证明

\[\begin{aligned} (f\ast e)(n) = \sum_{d\mid n} f(d)e(\dfrac{n}{d}) = \sum_{d\mid n} f(d)[\dfrac{n}{d} = 1] \end{aligned}\]

对于\([\dfrac{n}{d} = 1]\)，当且仅当 \(\dfrac{n}{d}=1\)，即 \(d=n\) 时为 \(1\)，否则为\(0\)。
则当 \(d=n\) 时，\(f(d)[\dfrac{n}{d}=1] = f(n)\)。
当 \(d\not ={n}\) 时，\(f(d)[\dfrac{n}{d}=1] = 0\)。

综上，\((f\ast e)(n) = \sum\limits_{d\mid n} f(d)[\dfrac{n}{d} = 1] = f(n)\)，满足单位元的性质。
则 \(e = \mu \ast 1\) 成立。

除数函数与幂函数

幂函数 \(\operatorname{Id}_{k}(n) = n^k\)。
除数函数 \(\sigma_{k}(n) = \sum\limits_{d\mid n} d^k\)。

显然有：

\[(\operatorname{Id}_k\ast 1)(n) = \sum_{d\mid n} \operatorname{Id_k(d)} = \sum_{d\mid n} d^k = \sigma_k \]

当 \(k=0\) 时，\(\operatorname{Id_0}=1\)，\(\sigma_0\) 为因数个数函数，有：

\[(1\ast 1)(n) = \sum_{d\mid n}1 = \sigma_0 \]

欧拉函数与恒等函数

\[\begin{aligned} \varphi \ast 1 =& \operatorname{Id}\\ \varphi =& \operatorname{Id}\ast \mu \end{aligned}\]

对于一式，当 \(n=p^m\) 时（\(p\) 为质数），有：

\[(\varphi \ast 1)(p^m) = \sum_{d\mid n}\varphi(d) = \varphi(1) +\sum_{i=1}^{m}\varphi(p^i) = 1 +\sum_{i=1}^{m}(p^i-p^{i-1}) = p^m \]

\(p^i\) 的因子有 \(p^{i-1}\) 个，为 \(1\sim p^{i-1}\)，故 \(\varphi(p^i) = p^i-p^{i-1}\)。

又 \((\varphi \ast 1)(n)\) 为积性函数，则对于任意正整数 \(n\)，有：

\[(\varphi \ast 1)(n) = (\varphi \ast 1)(\prod p^m) = \prod(\varphi \ast 1)(p^m) = \prod p^m = n \]

得证。

对于 2 式，在 1 式基础上两侧同时 \(\ast \mu\) 即得。
左侧变为 \(\varphi \ast 1\ast \mu = \varphi \ast e = \varphi\)。

写在最后

算法学习笔记(35): 狄利克雷卷积 By: Pecco

希望人没事

「笔记」积性函数