积性函数

定义

如果 $n$ , $m$ ， $gcd(n,m)=1$ ，有 $f(n)\times f(m)=f(n\times m)$

如果 $gcd(n,m)\ne 1$ 时也有 $f(n)\times f(m)=f(n\times m)$ ，则称 $f$ 是完全积性的。

性质

• $f(1)=1$
• 设 $n=\prod p_i^{q_i}$ ，则 $f(n)=f(\prod p_i^{q_i})=\prod f(p_i^{q_i})$

若 $f(n)$ 完全积性，则 $\prod f(p_i^{q_i})=\prod f(p_i)^{q_i}$

常见积性函数

欧拉函数 $\varphi(n)$ ：与 $n$ 互质的正整数数目。 $\varphi(n)=n\prod(1-\frac 1 {p_i})$

莫比乌斯函数 $\mu(n)$ ：若 $n$ 有平方因子，则 $\mu(n)=0$ ，否则 $\mu(n)=(-1)^r$ ， $r$ 是 $n$ 的质因子数目。

$n$ 的正因子数目 $d(n)$

除数函数 $\sigma_x(n)$ ： $n$ 的所有因子的 $x$ 次方之和。

$1$ 函数： $1(n)=1$ （完全积性）

单位函数 $Id(n)=n$ ，（完全积性）

狄利克雷卷积单位元函数 $\varepsilon(n)$ ：当 $n=1$ 时 $\varepsilon(1)=1$ ，对于 $n\ne1$ 有 $\varepsilon(n)=0$ 。

积性函数的积

函数相乘。

乘积： $(f\times g)(n)=f(n)\times g(n)$

狄利克雷卷积： $\begin{align}(f\times g)(n)=\sum_{d|n}f(d)\times g(\frac n d)\end{align}$

狄利克雷卷积的性质：

1、结合律： $\forall f,g,j\in I\ (f\times g)\times h=f\times (g\times h)$

2、交换律： $\forall f,g\in I\ f\times g=g\times f$

3、逆元： $\forall f\in I,\exists f^{-1}\in I\ f\times f^{-1}=\varepsilon$

4、单位元： $\forall f\in I\ f\times \varepsilon=\varepsilon \times f=f$

5、封闭性： $\forall f,g\in I\ f\times g \in I$

若 $f,g$ 均积性，则他们的两个乘积也积性，若均完全积性，则乘积也完全积性。

乘积满足交换律和结合律。

一些结论

$\mu \times 1=\varepsilon$

当 $n=1$ 时显然成立，当 $n\ne1$ 时， $\begin{align}\mu\times 1=\sum_{d|n}\mu(d)\end{align}$

若 $d$ 有完全平方因子，则 $\mu(d)=0$ ，设约数个数为 $k$ ，则有： $$ \sum_{d | n}\mu(d)=\sum_{i=0}^kC_k^i(-1)^i $$ 根据二项式定理： $$ (x+y)^k=\sum_{i=0}^kC_k^ix^iy^{k-i} $$ 设 $x=1,y=-1$ 得： $$ (1+(-1))^k=\sum_{i=0}^kC_k^i1^{k-i}(-1)^i=\sum_{i=0}^kC_k^i(-1)^i=0 $$

$\varphi\times 1=Id$

若 $n$ 为质数， $\varphi\times1=\varphi(1)+\varphi(n)=1+(n-1)=n$

若 $n$ 不为质数，由积性函数性质得 $\varphi(n)\times1=\Pi\varphi(p_i^{q_i})\times1$

$$ \varphi(p_i^{q_i})\times1=\sum_{k=0}^{q_i}\varphi(p_i^k)=\sum_{k=1}^{q_i}p_i^k(1-\frac 1 {p_i})+1=p_i\times\frac{p_i^{q_i}-1}{p_i-1}\times \frac{p_i-1}{p_i}+1=p_i^{q_i} $$ 所以 $\varphi\times1=Id$

$\varphi(n)=\sum\varepsilon(gcd(i,n))$

欧拉函数定义。

$\mu\times Id=\varphi$

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

交换求和号 ： $$ 原式=\sum_{d|n}\mu(d)\sum_{d|i}^n 1=\sum_{d|n}\mu(d)\lfloor\frac n d\rfloor $$

莫比乌斯反演

$f\times1=g\Leftrightarrow g\times\mu=f$

证明

从左到右：

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

交换求和号：

$$ 原式=\sum_{d'|n}f(d') \sum_{d'|\frac n d}\mu(d)=\sum_{d'|n}f(d')\varepsilon(\frac n {d'})=f(n) $$

从右到左：

$$ f\times 1=\mu\times g\times 1=\sum_{d|n}(\mu\times g)(d)=\sum_{d|n}\sum_{d'|d}\mu(\frac d{d'})g(d')=\sum_{d'|n}g(d')\sum_{d|n,d'|d}\mu(\frac {d}{d'}) $$

由于 ${d|n}\Rightarrow\frac{d}{d'}|\frac{n}{d'}$ ， $$ 原式=\sum_{d'|n}g(d')\sum_{d''|\frac{n}{d'}}\mu(d'')=\sum_{d'|n}g(d')\varepsilon(\frac n {d'}) $$

当且仅当 $d'=n$ 时 $\varepsilon(\frac n{d'})$ 为 $1$ ，所以 $f\times 1=g$

解题思路

四个结论： $\mu\times 1=\varepsilon\ \ \varepsilon\times 1=1\ \ \varphi\times 1=Id\ \ Id\times \mu = \varphi$

除法分块：

$\lfloor\frac n d\rfloor$ 至多只有 $\sqrt n$ 种取值。

一般用于函数求和。

一维除法分块：

for(int l = 1,r;l <= n;l = r + 1)

{

    r = n / (n / l);

    //do something

}

设 $sum[x]$ 为函数 $f(x)$ 前缀和，要求 $\sum f(d)g(\lfloor\frac n d\rfloor)g(\lfloor\frac m d\rfloor)$

二维除法分块：

for(int l = 1,r = 0;l <= n;l = r + 1)

{

    r = min(n / (n / l),m / (m / l));

    ans += (sum[r] - sum[l - 1]) * g[n / l] * g[m / l];

}

大概就是每次在 $n$ 和 $m$ 里找一个较小的右边界，则左右边界内 $\lfloor\frac n d\rfloor$ （和 $\lfloor\frac m d\rfloor$ ）的值相同。

$\frac{i\times j} {gcd(i,j)}=lcm(i,j)$

分块套分块

交换求和号

注意下标的转化。

预处理积性函数值及前缀和

线性筛 $\&$ 杜教筛

$\begin{align}d(nm)=\sum[i|n]\sum[j|m][gcd(i,j)==1]\end{align}$

证明：

设 $nm=p_1^{q_1}p_2^{q_2}\cdots p_k^{q_k}\ n=p_1^{x_1}p_2^{x_2}\cdots p_k^{x_k}\ m=p_1^{y_1}p_2^{y_2}\cdots p_k^{y_k}$ 。

其中 $x_1+y_1=q_1$ 。

每个质因子次数都可以在 $[0,q_i]$ 内取值，所以 $d(nm)=\prod(q_i+1)$ 。

设 $i=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}\ j=p_1^{b_1}p_2^{b_2}\cdots p_k^{b_k}$

要想 $gcd(i,j)==1$ ， $a_i$ 或 $b_i$ 至少有一个为零，

当 $a_i$ 为 $0$ 时， $b_i$ 有 $y_i+1$ 种取值，当 $b_i$ 为 $0$ 时， $a_i$ 有 $x_i+1$ 种取值，在删掉一个两个都为零的情况被统计了两次，对于一个因子共有 $x_i+1+y_i+1-1=q_i+1$ 故： $$ \sum_{j|m}[gcd(i,j)==1]=\prod (q_i+1)=d(nm) $$

$[1,n]$ 内与 $n$ 互质的数的和为 $\frac n 2\times \varphi+\varepsilon$

证明：

$$ \begin{align}&\sum_{i=1}^ni\times\varepsilon(gcd(i,n)) =&\sum_{i=1}^ni\sum_{d|gcd(i,n)}\mu(d)\end{align} $$

交换求和号，得：

$$  \begin{align}&=\sum_{d|n}\mu(d)\sum_{i=1,d|i}^n i\\ &=\sum_{d|n}\mu(d)\sum_{i=1}^{\frac n d} i\times d\\ &=\sum_{d|n}\mu(d)\frac{1+\frac n d}{2}\times \frac n d\times d\\ &=\frac n 2\times((\mu\times Id)(n)+(\mu\times1)(n))\\ &=\frac {n\times \varphi(n)+\varepsilon(n)}2 \end{align} $$

放缩

一些常用方法：

$$ \sum_{d|n}\sum_{i=1}^{n}\frac n d=\sum_{d|n}\sum_{i=1}^{\frac n d}i $$

$$ \sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)==d]=\sum_{i=1}^{\lfloor\frac n d\rfloor}\sum_{j=1}^{\lfloor\frac m d\rfloor}[gcd(i,j)==1] $$

枚举

对于求 $lcm$ 的题，可以转化为： $$ \sum_{d|n}\sum_{i=1}^N\sum_{j=1}^M [gcd(i,j)==1] $$

设一些东西

如果看到了 $\lfloor\frac n{dk}\rfloor$ 就设一个 $T=dk$ ，再外层枚举 $T$ 。

$gcd$ 的处理方法

1、放缩化成 $\varepsilon(gcd(i,j))$ 再反演成 $\begin{align}\sum_{k|i,k|j}\mu(k)\end{align}$

2、直接由 $\varphi\times1=id$ 化成 $\begin{align}\sum_{k|i,k|j}\varphi(k)\end{align}$

$\begin{align}\sigma_1(n\times m)=\sum[i|n]\sum[j|m]i\times \frac m j[gcd(i,j)==1]\end{align}$

$\begin{align}\sum_{i=1}^ni\times[gcd(i,n)==1]=\frac {n\times \varphi(n)+\varepsilon(n)}2\end{align}$

都代表小于等于 $n$ 的数中与 $n$ 互质的数的和。

$\lfloor\lfloor n / i\rfloor/j\rfloor=\lfloor n/(ij)\rfloor$

$\begin{align}\sum_{d|n}f(d)\end{align}$ 可以通过枚举 $d$ 的倍数 $nlogn$ 预处理出所有值。

这个操作对于求狄利克雷卷积前 $n$ 项时也可以用。

$\begin{align}(f(n)\times g(n))\cdot Id=(f(n)\cdot Id)\times(g(n)\cdot Id))\end{align}$

$\begin{align}\sum_{i=1}^n\sum_{j=1}^m\sigma_0(ij)=\sum_{a=1}^n\sum_{b=1}[\gcd(a,b)=1]\lfloor\frac n a\rfloor\lfloor\frac m b\rfloor\end{align}$

注意

线性筛的时候 $if(i \% prime[j]==0)$ 不要写成 $if(i\%prime[j])$

$\mu(1)=\varphi(1)=1$

除法分块用的是前缀和

为了不出事等所有函数值求完了再求前缀和

除法分块时 $n$ 是较小的那个。

注意做反演题不能一条路走到黑，要及时停下来，这就要求在每一步都观察这个式子是不是已经可做了。

有些时候 $\varphi$ 可以解决一些求和式，达到简化复杂度的作用。

如果求和式是一个比较经典的模型，但是有一小部分很难处理，那大概率是先处理经典的部分，然后再看特殊情况怎么处理。