定义

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

性质

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

常见积性函数

• 单位函数 \(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\) 为莫比乌斯函数，定义为

解释

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

1. \(n=1\)时，\(\mu (n) = 1\)。
2. \(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\)为质因子的种类数。

性质

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

证明，设 \(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\)。

补充结论

反演结论:

证明 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\) 的狄利克雷卷积为

性质

1. 显然满足 交换律，结合律，分配律。
   • \(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\)
2. \(e\) 为狄利克雷卷积的单位元，有\((f\ast e)(n) = f(n)\)。
3. 若 \(f,g\) 为积性函数，则 \(f\ast g\) 为积性函数。

\(e\)

有：

证明

• 对于\([\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\)。

显然有：

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

欧拉函数与恒等函数

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

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

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

得证。

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

写在最后

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

希望人没事