初等数论笔记-算法竞赛相关-Ⅲ

常见的积性函数

单位函数，完全积性函数$\epsilon(n):=\begin{cases} 1,\qquad n=1\\ 0,\qquad otherwise \end{cases} \\$​​​

注意到

$\begin{aligned} (f*\epsilon)(n)&=\sum_{d|n}f(d)1(n/d)\\ &=f(n) \end{aligned}$

显然单位函数$\epsilon$是迪利克雷卷积的单位元

幂函数，完全积性函数，$Id_k(n):=n^k$​​​​​
特别地，当$k=1$​​时为恒等函数$Id(n):=n$​​，$k=0$​​时$1(n):=1.$​​​

除数函数$\sigma_k(n):=\sum_{d|n}d^k,\qquad d\in N$​
特别地，当$k=1$​时，为$\sigma(n)$​，$k=0$​时,为$\tau(n)$

因子和$\sigma(n)=\frac{p_1^{a_1+1}-1}{p_1-1}·\frac{p_2^{a_2+1}-1}{p_2-1}...\frac{p_s^{a_s+1}-1}{p_s-1} =\prod_{j=1}^s\frac{p_j^{a_j+1}-1}{p_j-1}$​

因子个数和$\tau(n)=(a_1+1)·(a_2+1)...(a_s+1)=\prod_{j=1}^s(a_j+1)$​

对于$\tau(n)$​，我们有$\tau(ij)=\sum_{x|i} \sum_{y|j}[gcd(i,j)==1]$​

欧拉函数$\phi(m)=m(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_m})$

迪利克雷卷积

$(f*g)(n):=\sum_{d|n}f(n/d)g(d) \qquad (x,y\in Z)\\ (f*g)(n):=\sum _{xy=n}f(x)g(x) \;\;\; \qquad(x,b \in Z)$

四个性质

1.若$f,g$​​​​​为积性函数，则$f*g$​​​​​也是积性函数
2.迪利克雷卷积满足交换律，即$f*g=g*f$​​​​​
3.满足结合律，$(f*g)h=f(g*h)$​​​​​
4.满足分配律，$f*(g+h)=f*g+f*h$​​​​​​​

重要结论

如果一个函数和1作迪利克雷卷积，就相当于把其参数所有的因子枚举出来带入原函数，然后求和，即

$(f*1)(n)=\sum_{d|n}f(d)$

e.g.

1.$Id_k*1=\sigma_k$

$\begin{aligned} Id_k*1&=\sum_{d|n}Id_k(d)1(n/d) \\ &=\sum_{d|n}d^k\\ &=\sigma_k \end{aligned}$

2.$\phi*1=Id$

$\begin{aligned} \phi*1&=\sum_{d|n}\phi(d)1(n/d)\\ &=\sum_{d|n}\phi(d)\\ \end{aligned}\\ \\$

考虑$n=p^d,p\in P$时，有

$\begin{aligned} &=\phi(1)+\sum_{i=1}^d\phi(p^i)\\ &=\phi(1)+\sum_{i=1}^dp^i(1-\frac{1}{p})\\ &=1+\sum_{i=1}^dp^i-p^{i-1}\\ &=p^d\\ &=Id\\ \end{aligned}\\ \\$

考虑更普遍的情况，当n为任意整数时，有

$\begin{aligned} (\phi*1)(n)&=(\phi*1)(\prod p^m)\\ &=\prod (\phi*1)(p^m)\\ &=\prod p^m\\ &=n \end{aligned}\\ \\$

3.$1*1=d$

$\begin{aligned} (1*1)(n)&=\sum_{d|n}1(d)1(n/d)\\ &=\sum_{d|n}1\\ &=d(n) \end{aligned}$

4.$\mu*1=\epsilon$​​，莫比乌斯函数

显然可得$\sigma=Id*1=\phi*1*1=\phi*d$

迪利克雷逆

积性函数必有迪利克雷逆，且逆也为积性函数且唯一的。对迪利克雷逆，$f*f^{-1}=\epsilon$，定义如下：

$f^{-1}(n):= \begin{cases} \frac{1}{f(1)},\qquad \qquad \qquad\qquad\qquad\qquad n=1,\\ -\frac{1}{f(1)}\sum_{d|n,d\neq n}f(n/d)f^{-1}(d),\;\;\;\;\;otherwise. \end{cases}$

ps.关于迪利克雷逆遇见过一个很好玩的题，但是题目打不开了…QwQ

莫比乌斯反演

因数形式

定义1：对于算术函数$f$​​​​，有其和函数

$F(n)=\sum_{d|n}f(d)$

得到​

$f(n)=\sum_{d|n}\mu(d)F(n/d)$

其中莫比乌斯函数定义为

$\mu(n)= \begin{cases}1,\qquad \qquad \; \; n=1 \\ (-1)^m,\qquad \; n=p_1p_2...p_m,p_i\in P \\0 ,\qquad \qquad \; \; else \end{cases}$

且$\mu (n)$​和函数定义为

$G(n)=\sum_{d|n}\mu(d)= \begin{cases} 1,\qquad \qquad n=1\\ 0,\qquad \qquad n>1 \end{cases}\qquad=\epsilon(n)$

Proof.
我们将$F(n/d)$用表达式$\sum_{e|(n/d)}f(e)$​​​来代替，得到

$\sum_{d|n}\mu(d)F(n/d)=\sum_{d|n}(\mu(d)\sum_{e|(n/d)}f(e))=\sum_{d|n}(\sum_{e|(n/d)}\mu(d)f(e))$

注意到$(d,e)$满足$d|n$和$e|(n/d)$，同样有$e|n$和$d|(n/e)$​

$\sum_{d|n}(\sum_{e|(n/d)}\mu(d)f(e))=\sum_{e|n}(\sum_{d|(n/e)}f(e)\mu(d))=\sum_{e|n}(f(e)\sum_{d|(n/e)}\mu(d)).$

显然当$n=e$​时，$\sum_{d|(n/e)}\mu(d))=1$​​​，否则=0；
因此有

$\sum_{e|n}(f(e)\sum_{d|(n/e)}\mu(d))=f(n)·1=f(n).$

定义2：定义单位函数1$(n)$​​的迪利克雷逆为莫比乌斯函数$\mu(n)$​​，即

$\mu:=1^{-1}$

在定义2中，我们使用迪利克雷卷积来推导莫比乌斯反演公式：

$g=f*1\iff f=g*\mu$

展开后有

$g(n)=\sum_{d|n}f(d)\iff f(n)=\sum_{d|n}\mu(d)g(\frac{n}{d})$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

void pre(int n=1e7){
	//	int vis[N],pri[N],mu[N],tot;
	mu[1]=1;
	for(int i=2;i<=n;i++){
		if(!vis[i]){
			pri[++tot]=i;
			mu[i]=-1;
		}
		for(int j=1;j<=tot&&pri[j]*i<=n;j++){
			int cur=pri[j]*i;
			vis[cur]=1;
			if(i%pri[j]==0){
				mu[cur]=0;
				break;
			} else{
				mu[cur]=mu[pri[j]]*mu[i];
			}
		}
	}
}

倍数形式

$g(n)=\sum_{n|N}f(N)\iff f(n)=\sum_{n|N}g(N)\mu(\frac{N}{n})$

常用技巧

提取公因式

设有

$\sum_{i=1}^n\sum_{j=1}^{m}\sum_{d|gcd(i,j)}f(d,i,j)$

令$x=\frac{i}{d},y=\frac{j}{d}$，得到

$\sum_{d=1}^{min(n,m)}\sum_{x=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{y=1}^{\lfloor\frac{m}{d}\rfloor}f(d,xd,yd)$

e.g.

对于

$\sum_{i=1}^n \sum_{j=1}^m \sum_{d|gcd(i,j)}\mu(d)\\$

令$x=\frac{i}{d},y=\frac{j}{d}$​，得到

$\sum_{d=1}^{min(n,m)}\sum_{x=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{y=1}^{\lfloor\frac{n}{d}\rfloor}\mu(d)$

该公式还可进行推广：

$\sum_{i=1}^n\sum_{d|i}f(d,i)\implies \sum_{d=1}^{n}\sum_{x=1}^{\lfloor\frac{n}{d}\rfloor}f(d,xd)$

其中，$x=\frac{i}{d}$

$\sum_{i=1}^n\sum_{j=1}^{m}\sum_{k=1}^{l}\sum_{d|gcd(i,j,k)}f(d,i,j,k)\implies\sum_{d=1}^{min(n,m,l)}\sum_{x=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{y=1}^{\lfloor\frac{m}{d}\rfloor}\sum_{z=1}^{\lfloor\frac{l}{d}\rfloor}f(d,xd,yd,zd)\\$

其中，$x=\frac{i}{d},y=\frac{j}{d},z=\frac{k}{d}$

整除分块

对于

$\sum_{d=1}^{n}\lfloor\frac{k}{d}\rfloor$

记区间左端点为$l$​，区间右端点为$r$​。存在整数$a$​，s.t.

$a+1>\frac{k}{l}≥\frac{k}{r}≥a$

显然，$l$为满足上式的最小整数，$r$为满足上式的最大整数，且$a=\lfloor \frac{k}{l} \rfloor$​，则​

$r≤\frac{k}{a}=\frac{k}{\lfloor \frac{k}{l} \rfloor}$

由于$r$为整数，所以$r=\lfloor \frac{k}{\lfloor\frac {k}{l}\rfloor}\rfloor$

即若区间左端点为$l$​​​，那么右端点为$r=\lfloor \frac{k}{\lfloor\frac {k}{l}\rfloor}\rfloor$​。复杂度是$O(\sqrt n)$​，​复杂度的证明比较繁琐，这里就不写了。

1
2
3
4
5
6
7
8

ll ans=0;
for(int l=1,r;l<=n;l=r+1){
	if(k/l)
		r=min(k/(k/l),n);
	else
		r=n;
	ans+=(r-l+1)*(n/l);
}