积性函数与线性筛 学习笔记

- 这里主要说明积性函数的一些定义和通性，并不会对某些函数的特殊性质进行过多展开。 ### 积性函数的定义 **数论函数**： $f:\mathbb Z\to \mathbb C$。 **积性函数**：若有数论函数 $f(x)$ 满足：$\forall x,y\in \mathbb N,(x,y)=1$ 有 $f(ab)=f(a)f(b)$，则称 $f$ 为**积性函数**。 **完全积性函数**：若有数论函数 $f(x)$ 满足：$\forall x,y\in \mathbb N$ 有 $f(ab)=f(a)f(b)$，则称 $f$ 为**完全积性函数**。 --- ### 常见积性函数 $d(x)=\sum_{i\mid n} 1$ ①**（约数函数）** $\sigma_k(x)=\sum_{i\mid n} i^k$ （$\sigma(x)=\sigma_1(x)$）②**（除数函数）** $\varphi(x)=\sum\limits_{i=1}^{x}[\gcd(i,x)=1]$ ③**（欧拉函数）** $\mu(x)=\begin{cases} 1&x=1\\(-1)^k&x=\prod_{i=1}^k p_i(p_i\in \mathbb P)\\0&\max\{q_i\}>1\end{cases}$ ④**（莫比乌斯函数）** $\epsilon(n)=[n=1]$ ⑤**（单位函数）**（完全积性函数） $Id_k(n)=n^k$ （$Id(n)=Id_1(n)$）⑥**（幂函数）**（完全积性函数） $1(n)=1$ ⑦**（常数函数）**（完全积性函数） 都是积性函数。 **简要证明**：① $x\mid ab\Leftrightarrow \exists u,v\in \mathbb N,u\mid a\land v\mid b\land uv=x$ ②由上，$\sum uv=\sum u\sum v$，$\sum u^kv^k=\sum u^k\sum v^k$ ③$\gcd(x,ab)=1\Leftrightarrow \gcd(x,a)=1\land \gcd(x,b)=1$ ④⑤⑥⑦由定义显然。 --- ### 积性函数的性质 **性质：对任意积性函数 $f$，若 $\exists a\in\mathbb Z,f(a)\ne 0$，则有 $f(1)=1$。** 证明：$\because \gcd(1,a)=1$，$\therefore f(1\times a)=f(a)f(1)$，$f(1)=\frac{f(a)}{f(a)}=1$。 **性质：若 $f(x)$，$g(x)$ 是积性函数，则 $f(x^p)$，$f^p(x)$，$f(x)g(x)$，$\sum_{d\mid x} f(d)g(\dfrac{x}{d})$ 都是积性函数。** 证明：前三个显然，这里证第四个。$\forall a,b\in \mathbb Z,(a,b)=1$，有： $$ h(ab)=\sum\limits_{d\mid ab}f(d)g(\dfrac{ab}{d})=\sum\limits_{u\mid a,v\mid b}f(uv)g(\frac{ab}{uv}) $$ $\because (a,b)=1，u\mid a,v\mid b$，$\therefore(u,v)=1$，有： $$ h(ab)=\sum_{u\mid a,v\mid b}f(u)g(\frac{a}{u})\cdot f(v)g(\frac{b}{v})=\sum_{u\mid a}f(u)g(\frac{a}{u}) \cdot\sum_{v\mid b}f(v)g(\frac{b}{v})=h(a)h(b) $$ 总之，对积性函数的证明，可以使用代入定义的方式，裂开枚举的约数 $d$ 进行处理。 **性质：若 $f$ 为积性函数，则有 $f(x)=\prod f(p_i^{k_i})$。若 $f$ 为完全积性函数，则有 $f(x)=\prod f(p_i)^{k_i}$。（其中 $x=\prod p_i^{k_i}$ 为 $x$ 的标准分解）** 证明：由定义显然。 --- ### Dirichlet 卷积 事实上，第四个式子正是 *Dirichlet* 卷积的表达式。 **定义**：若有数论函数 $f$，$g$，$h$ 满足： $$ h(x)=\sum\limits_{d\mid x}f(d)g(\frac{x}{d}) $$ 则称 $h$ 为 $f$，$g$ 的 ***Dirichlet* 卷积**（狄利克雷卷积）。 经常把它变形为： $$ h(n)=\sum_{ab=n}f(a)g(b) $$ 这样就易证 ***Dirichlet* 卷积具有交换律、结合律和分配律**。 **性质：对任意数论函数 $f$，$f=f*\epsilon$。** 证明：直接展开，原式显然成立。因此，我们也称 $\epsilon$ 为**单位元**。 **性质：两个积性函数的卷积为积性函数。** 就是上面的证明。 **性质：若有数论函数 $f$，$g$，$h$，则 $f=g\Leftrightarrow f*h=g*h$。其中 $h(1)\ne 0$。**（等式的性质） 证明：移项，得 $f*h-g*h=0$。由卷积的分配律，$(f-g)*h=0$。 $\because h\ne 0$，$\therefore f-g=0,f=g$。 **性质：$d=1^2$；$\sigma_k(n)=1*Id_k(n)$；$Id=\varphi*1$。** 证明：前两个式子由定义显然。第三个式子证明如下： 原式即证 $n=\sum\limits_{d\mid n} \varphi(d)$。由 $\varphi$ 的组合意义，左边一式可理解为枚举 $d\mid n$，求所有以 $d$ 为分母的不大于 $1$ 的最简分数个数。 也即以 $n$ 为分母的不大于 $1$ 的分数个数，这正是等号右边的值。 具体而严谨的证明请参阅欧拉函数笔记。（咕咕咕） **性质：$\sum\limits_{i=1}^n \left\lfloor\frac{n}{i}\right\rfloor=\sum\limits_{i=1}^nd(i)$**。 证明：打开左式，交换求和次序： $$ \sum\limits_{i=1}^n \left\lfloor\frac{n}{i}\right\rfloor=\sum\limits_{i=1}^n\sum\limits_{j=1}^n[i\mid j]=\sum\limits_{j=1}^n\sum\limits_{i=1}^n[i\mid j]=\sum\limits_{j=1}^nd(j). $$ --- ### 逆元及其性质 **定义**：对任意数论函数 $f(x)\ne 0$，若有数论函数 $g$ 满足 $f*g=\epsilon$，则称 $g$ 为 $f$ 的逆元。 **性质：对确定的数论函数 $f\ne 0$，逆元存在且唯一。** 证明：唯一性通过等式的性质易证，存在性可以通过构造递推式： $$ g(x)=\dfrac{\epsilon(x)-\sum_{d|x,d\ne 1}f(x)g(\dfrac{x}{d})}{f(1)} $$ 实现。（就是把卷积表达式中 $d=1$ 的一项拆开除过去） **性质：$\mu$ 的逆元是 $1$。** 证明请参阅莫比乌斯反演笔记。（咕咕咕） 由此我们可以得到 $Id=\varphi*1\Rightarrow Id*\mu=\varphi*\mu*1\Rightarrow \varphi=Id*\mu$。 **性质：积性函数的逆元还是积性函数。** 证明：设有积性函数 $f$，其逆元为 $g$。原命题即证 $\forall n,m\in \mathbb N,(n,m)=1$，$g(nm)=g(n)g(m)$。 因为 $f$，$g$ 互为逆元，因此 $f(1)=g(1)=1$，考虑归纳。 - $n=1$，$m=1$ 时，有$g(nm)=1=g(n)g(m)$ 成立。 - 对任意 $nm>1,(n,m)=1$，假设对所有的 $x<n$，$y<m$ 且 $(x,y)=1$，都有 $g(xy)=g(x)g(y)$ 成立。 由 $nm>1$ 得 $\epsilon(nm)=0$，又因 $f(1)=1$，代入递推式： $$ g(nm)=-\sum\limits_{d\mid nm,d\ne 1} f(d)g(\dfrac{nm}{d}) $$ 拆开： $$ g(nm)=-\sum\limits_{u\mid n,v\mid m,uv\ne 1} f(uv)g(\dfrac{n}{u}\cdot\dfrac{m}{v}) $$ $$ g(nm)=-\sum\limits_{u\mid n,v\mid m,uv\ne 1} f(u)g(\dfrac{n}{u})\cdot f(v)g(\dfrac{m}{v}) $$ $$ g(nm)=f(1)g(n)f(1)g(m)-\sum\limits_{u\mid n} f(u)g(\dfrac{n}{u})\sum\limits_{v\mid m}f(v)g(\dfrac{m}{v}) $$ $$ g(nm)=g(n)g(m)-\epsilon(n)-\epsilon(m) $$ $$ g(nm)=g(n)g(m) $$ 总之，含函数递推式的证明考虑归纳。 --- ### 线性筛素数 我们从小到大枚举每一个自然数，然后把它乘上一个素数。 注意：这个素数的素因子应当**不大于这个被乘的自然数的最小素因子**。 ```c++ fo(i,2,n) { if(v[i]==0) { v[i]=i; prime[++tot]=i; } fo(j,1,tot) { if(prime[j]>v[i]||(ll)i*prime[j]>n) break; v[i*prime[j]]=prime[j]; } } ``` 上面的代码片段中，$v$ 数组记录每个数的最小素因子，$prime$ 数组记录当前的所有素数。 为什么这样的复杂度是线性的呢？由算术基本定理，每个大于 $1$​ 的自然数有且仅有一种标准分解形式。 比如我们知道 $12=2^2\times 3$，那么在线性筛中 $12$ 只会被 $2\times 3=6$ 筛到，而不会被 $2^2=4$ 筛到。 这样每个数至多被筛一次，复杂度是 $\Theta(n)$ 的。 --- ### 线性筛积性函数 能不能再给力点，筛出积性函数？ 事实上，对任意一个积性函数 $f$，如果我们能在常数时间内算出以下三种值： - $f(1)$ . - $f(p),p\in \mathbb P$ . - $f(p^k),p\in \mathbb P,k\in N^*$ 那么我们就可以用线性筛将其筛出。 比如，我们可以方便地筛出 $\varphi$ 和 $\mu$ 的值。​ ```c++ fo(i,1,n) phi[i]=i-1, mu[i]=1; fo(i,2,n) { if(v[i]==0) { v[i]=i, prime[++tot]=i, mu[i]=-1; } fo(j,1,tot) { if(prime[j]>v[i]||i*prime[j]>n) break; v[i*prime[j]]=prime[j]; if(i%prime[j]==0) phi[i*prime[j]]=phi[i]*prime[j], mu[i*prime[j]]=0; else phi[i*prime[j]]=phi[i]*(prime[j]-1), mu[i*prime[j]]*=-mu[i]; } } ``` 对一般的积性函数，我们还是采取标准分解的形式筛。 一般做法都是这样的： 设 $n=\prod_{i=1}^{s}p_i^{\alpha_i}$ ，其中 $p_1\le p_2\le\cdots\le p_s$。记 $low(n)=p_1^{\alpha_1}$，依赖 $low$​ 进行线性筛。​ ```c++ f[1]=/*the value of f(1)*/; fo(i,2,n) { if(v[i]==0) { v[i]=i, prime[++tot]=i, f[i]=/*the value of f(i)*/; } fo(j,1,tot) { if(prime[j]>v[i]||i*prime[j]>n) break; v[i*prime[j]]=v[i]*prime[j]; if(i%prime[j]==0) { low[i*prime[j]]=low[i]*prime[j]; if (low[i]==i) f[i*prime[j]]=/*the value of f(i*prime[j]), probably can be solved through f(i)*/; else f[i*prime[j]]=f[i/low[i]]*f[low[i]*prime[j]]; //Obviously there's prime[j]<=i/low[i] (or prime[j] can't be the minimum prime factor), //therefore low[i]*prime[j]<=i/low[i]*low[i]=i. //So f[i/low[i]] and f[low[i]*prime[j]] have been sieved before. break; } else { low[i*prime[j]]=prime[j]; f[i*prime[j]]=f[i]*f[prime[j]]; } } ``` ~~上面的英文我自己乱打的，可能有语法错误（（（~~ （我自己瞎搞的，没啥意义）另外，我们也可以一次枚举所有次幂，直接计算。这样可能会更直观一些。 完结撒花~~