526互联

狄利克雷卷积和积性函数

发布时间 2023-08-19 06:56:14作者: -白简-

数论函数

数论函数指定义域为正整数，值域是一个数集且满足 \(f(1) \neq 0\) 的函数。我们可以将数论函数看作一个数列。

设有 \(f(n),g(n)\) 两个数论函数，有几种常见运算：

  • 加法：\((f+ g)(n)=f(n)+g(n)\)
  • 数乘：\((af)(n)=a \cdot f(n)\)
  • 乘法：\((f \cdot g)(n)=f(n) \cdot g(n)\)
  • 复合：\(f(g)(n)=f(g(n))\)

此外，加法、数乘和乘法运算满足交换律、结合律、分配律和消去律。

狄利克雷卷积（Dirichlet）

定义

对于两个数论函数 \(f,g\)，他们的狄利克雷卷积也是一个数论函数，我们记为 \(h\)，则 \(h=f * g\)。

\(h\) 定义为：

\[\displaystyle h(n)=(f * g)(n)=\sum_{d \mid n}f(d) g({n\over d}) \]

狄利克雷卷积符合交换律、结合律和分配律：

  • 交换律：

\[\displaystyle (f*g)(n)=\sum_{d\mid n}f(d)g({n\over d})=\sum_{d\mid n}f({n\over d})g(d)=(g*f)(n) \]

  • 结合律：

\[\displaystyle (\ (f*g)*h\ )(n)=\sum_{i\cdot j\cdot k=n}(\ f(i)\cdot g(j)\ )\cdot h(k)=\sum_{i\cdot j\cdot k=n}f(i)(\ g(j)\cdot h(k)\ )=(\ f*(g*h)\ )(n) \]

  • 分配律：

\[\displaystyle (\ (f+g)*h\ )(n)=\sum_{d\mid n}(\ f(d)+g(d)\ )\cdot h({n\over d})=\sum_{d\mid n}f(d)h({n\over d})+\sum_{d\mid n}g(d)h({n\over d})=(f*h+g*h)(n) \]

单位元：单位函数 \(\epsilon\) 是狄利克雷卷积运算中的单位元，即对于任何数论函数 \(f\)，都有 \(f * \epsilon=f\)。

逆元：对于任何一个满足 \(f(x)\neq 0\) 的数论函数，如果有另一个数论函数 \(g(n)\) 满足 \(f * g = \epsilon\)，则称 \(g(n)\) 是 \(f(n)\) 的逆元，逆元是唯一的。

重要结论

两个积性函数的狄利克雷卷积也是积性函数

证明： 设两个积性函数为 \(f(x)\) 和 \(g(x)\)，再记 \(h=f*g\)。

设 \(\gcd(a,b)=1\)，则：

\[h(a)=\sum_{d_1\mid a}{f(d_1)g\left(\dfrac a{d_1} \right)},h(b)=\sum_{d_2\mid b}{f(d_2)g\left(\dfrac b{d_2} \right)}, \]

所以：

\[\begin{aligned} h(a)h(b)&=\sum_{d_1\mid a}{f(d_1)g\left(\dfrac a{d_1} \right)}\sum_{d_2\mid b}{f(d_2)g\left(\dfrac b{d_2} \right)}\\ &=\sum_{d\mid ab}{f(d)g\left(\dfrac {ab}d \right)}\\ &=h(ab) \end{aligned} \]

证毕。

积性函数的逆元也是积性函数

几个常见数论函数的例子：

\[\begin{aligned} \varepsilon=\mu \ast 1&\iff\varepsilon(n)=\sum_{d\mid n}\mu(d)\\ d=1 \ast 1&\iff d(n)=\sum_{d\mid n}1\\ \sigma=\operatorname{id} \ast 1&\iff\sigma(n)=\sum_{d\mid n}d\\ \varphi=\mu \ast \operatorname{id}&\iff\varphi(n)=\sum_{d\mid n}d\cdot\mu(\frac{n}{d}) \end{aligned} \]

积性函数

定义

若函数 \(f(n)\) 满足 \(f(1)=1\) 且 \(\forall x,y\in\mathbf{N}^+,\gcd(x,y)=1\) 都有 \(f(xy)=f(x)f(y)\)，则 \(f(n)\) 为积性函数。

若函数 \(f(n)\) 满足 \(f(1)=1\) 且 \(\forall x,y\in\mathbf{N}^+\) 都有 \(f(xy)=f(x)f(y)\)，则 \(f(n)\) 为完全积性函数。

性质

若 \(f(x)\) 和 \(g(x)\) 均为积性函数，则有：

  • \(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\left(\dfrac{x}{d}\right)\)

均为积性函数。

若 \(f(x)\) 为积性函数，则有 \(f(x)=\prod f(p_i^{k_i})\)；若 \(f(x)\) 为完全积性函数，则有 \(f(x)=\prod f(p_i)^{k_i}\)。

常见积性函数

  • 单位函数（元函数）：\(\epsilon(n)=[n=1]\)。
  • 欧拉函数：\(\varphi(n)\)，表示小于 \(n\) 的正整数中与 \(n\) 互质的数的个数。
  • 幂函数：\(\operatorname{id}_k(n)=x^k\)，特别的，\(\operatorname{1}(x)=1\)，\(\operatorname{id}(x)=x\)。
  • 除数函数：\(\sigma_k(x)=\sum_{d \mid x}d^k\)，特别的，\(\sigma(x)=\sum_{d \mid x}d\)。
  • 莫比乌斯函数：\(\mu(n)=\begin{cases}1&n=1\\0&\exists d>1,d^{2}\mid n\\(-1)^{k}&\text{otherwise}\end{cases}\)，其中 \(k\) 表示 \(n\) 的本质不同的质因子个数。莫比乌斯函数是一个加性函数。这里指数论中的加性函数，对于 \(\gcd(a,b)=1\)，有 \(f(ab) = f(a)+f(b)\)。

筛法求积性函数

容易发现，这些积性函数的自变量取值为质数时，都可以简单地 \(\operatorname{O}(1)\) 求出，那我们可以利用积性函数的性质求出函数值。

欧拉函数

首先我们知道，当 \(p\) 为质数时，显然有

\[\varphi(p)=p-1 \]

欧拉函数有一种计算方法

\[\varphi(n) = n \times \prod_{i = 1}^s{\dfrac{p_i - 1}{p_i}} \]

  1. 考虑 \(p \mid n'\)，那么 \(n'\) 就已经包含了 \(n\) 的所有质因子。

\[\begin{aligned} \varphi(n) & = n \times \prod_{i = 1}^s{\frac{p_i - 1}{p_i}} \\\\ & = p \times n' \times \prod_{i = 1}^s{\frac{p_i - 1}{p_i}} \\\\ & = p \times \varphi(n') \end{aligned} \]

  1. 考虑 \(p \nmid n'\)，此时 \(n'\) 与 \(p\) 是互质的，有“

\[\varphi(n)=\varphi(p)\times\varphi(n') \]

void Eular()// 线性筛求欧拉函数  
{
	for(int i = 1;i <= MAXN; i++)
		isprime[i] = 1;
	
	isprime[1] = 0;
	phi[1] = 1;
	
	for(int i = 2;i <= MAXN; i++) {
		if(isprime[i]) {
			prime[++cnt] = i;
			phi[i] = i - 1;
		}
		
		for(int j = 1;j <= cnt and i * prime[j] <= MAXN; j++) {
			isprime[i * prime[j]] = 0;
			if(i % prime[j] != 0)
				phi[i * prime[j]] = phi[i] * phi[prime[j]];
			else {
				phi[i * prime[j]] = phi[i] * prime[j];
				break;
			}
		}
	}
}

莫比乌斯函数

当 \(x\) 为质数时，它只有 \(1\) 和 \(x\) 两个因数，所以 \(\mu(x)=-1\)。

当 \(x\) 为合数时：

  1. 若 \(p \mid x\)，那么 \(p \times i\) 一定含有不只一个 \(p\)，所以 \(\mu(i \times p)=0\)；
  2. 若 \(p \nmid x\)，那么 \(p\) 就是 \(p \times i\) 的新质因数，本质不同的质因数数量增加，所以 \(\mu(p \times i)=-\mu(i)\)。
void GetMu() {
    p[1] = 1;
    mu[1] = 1;

    for(int i = 2;i < N; i++) {
        if(p[i] == 0) {
            pri[++cnt] = i;
            mu[i] = -1;
        }

        for(int j = 1;j <= cnt && i * pri[j] < N; j++) {
            p[i * pri[j]] = 1;

            if(i % pri[j] == 0)
                break;
            
            mu[i * pri[j]] = -mu[i];
        }
    }
    return ;
}

对于一般积性函数 \(f\)，我们考虑如何筛。

  1. 考虑素数部分；
  2. 以 \(p \mid x\) 和 \(p \nmid x\) 两种分类求出非素数部分。

我们知道 \(prime_j\) 一定是 \(i \times prime_j\) 的最小质因子，又因为对于 \(i\) 有算术基本定理可以得到 \(i=p_i^{k_1}p_2^{k_2} \dots p_n^{k_n}\)。

有以下两种情况（即上面写的两种讨论分类）：

  1. \(prime_j=p_1\)，即 i % prime[j] == 0
  2. \(prime_j < p_1\)，即 i % prime[j] != 0

对于第一种情况，\(i \times prime_j\) 的质因子与 \(i\) 的质因子相同，最小质因子的指数比 \(i\) 大 \(1\)，即 \(p_1(i \times prime_j)=p_1(i) +1\)；

对于第二种情况，因为 \(prime_j < p_1\)，所以 \(prime_j\) 与 \(i\) 一定互质。则有 \(f(i \times prime_j)=f(i) \cdot f(prime_j)\)。

（以上只是大概的模板总结，实际情况具体分析）

参考资料

  1. OI Wiki
  2. 积性加性函数的运算到迪利克雷卷积
  3. 常见迪利克雷卷积及其证明
  4. 【数学】各种积性函数的线性筛法