Chlience

【算法】积性函数与筛法 (转自annoyrain)
能够线性筛(能够min_25筛)的算术函数必须满足以下特征:对于$n = p^a,a \in \mathbb{N}...
扫描右侧二维码阅读全文
20
2018/12

【算法】积性函数与筛法 (转自annoyrain)

能够线性筛(能够min_25筛)的算术函数必须满足以下特征:

  1. 对于$n = p^a,a \in \mathbb{N}$,$f(n)$能快速求出(一个多项式或者一个常数)。
  2. $f$是一个积性函数。

$(a,b) = 1$时有$f(ab) = f(a)f(b)$,则$f$是一个积性函数;若$\forall a,b,f(ab) = f(a)f(b)$,则$f$是一个完全积性函数。
根据定义可以知道,若$f(p^k) = f^k(p)$,则$f$为一个完全积性函数。

常见的积性函数(前四个为完全积性)有:

$$ \begin{gather*} I(n)=1 &\mbox{恒等函数}\\ id(n)=n &\mbox{单位函数}\\ id^k(n) = n^k &\mbox{幂函数}\\ \epsilon(n)=[n==1] &\mbox{元函数,狄利克雷卷积单位元}\\ \varphi(n)=\prod_{d \mid n}(1-\frac{1}{d}) &\mbox{欧拉函数}\\ \mu(n) &\mbox{莫比乌斯函数,与恒等函数在狄利克雷卷积下互为逆元}\\ \sigma_k(n) = \sum_{d\mid n} d^k &\mbox{除数函数}\\ \tau(n) = \sigma_0(n) = d(n)=\sum_{d\mid n} 1 &\mbox{约数个数函数}\\ \sigma(n)=\sum_{d\mid n} d &\mbox{约数和函数} \end{gather*} $$

此文将对常见的几个积性函数和狄利克雷卷积进行讨论。

狄利克雷卷积

狄利克雷卷积定义:$(f*g)(n) = \sum_{d\mid n} f(d) * g(\frac{n}{d})$。满足交换律、结合律、对加法满足分配率,并且我们可以找到它的单位元$\epsilon(n) = [n = 1]$使得$e * f = f = f * e$(根据卷积的定义,显然)。

可以发现两个积性函数卷积之后还是积性函数。
简单证明一下,当$f,g$是积性函数,$(a,b) = 1$时,$a$的每个因数$k$和$b$的每个因数$d$乘起来就可以不重不漏表示$ab$的每个因数$kd$(显然$(k,d) = 1$):

$$ \begin{eqnarray} (f * g)(ab) &= &\sum_{k\mid a, d\mid b} f(kd) * g(\dfrac{ab}{kd})\\ &= &\sum_{k\mid a, d\mid b} f(k)f(d) * g(\dfrac{a}{k})g(\dfrac{b}{d})\\ &= &\sum_{k\mid a} f(k) * g(\dfrac{a}{k}) * \sum_{d\mid b} f(d) * g(\dfrac{b}{d})\\ &= &(\sum_{k\mid a} f(k) * g(\dfrac{a}{k}) ) \times (\sum_{d\mid b} f(d) * g(\dfrac{b}{d}))\\ &= &(f * g)(a) \times (f * g)(b) \end{eqnarray} $$

(好吧我真啰嗦)

线性筛

线性筛积性函数是建立在线性筛素数的基础上的。
在线性筛中,$n$只会被它的最小质因数$d$筛到。
如果是性质良好的积性函数(可以根据$d$和$n/d$求出的函数),线性筛时套公式即可;如果是对于一般的积性函数,我们可以用$div_n$记录$d^k$,当$div_n = n$时用线性筛的性质$1$求出$f(n)$,否则用$f(n) = f(n/d^k)f(d^k)$。

for (int i = 2; i < n; ++i) {
    if (!is[i]) p[++tot] = i;
    for (int j = 1; i * p[j] < n && j <= tot; ++j) {
        is[i * p[j]] = 1;
        if (i % p[j] == 0) break;
    }
}

欧拉函数

欧拉函数$\phi(n)$表示在$[1,n]$中与$n$互质的数的个数。

关于欧拉函数是一个积性函数的证明:
$\phi(n)$表示$n$的简化剩余系的大小,比$n$小且与$n$互质的数组成$b$的一个简系(这就是简系和欧拉函数的定义)。
令$a$为$A$的简系,$b$为$B$的简系,只要证明:每个$a_i$和每个$b_j$以某种方式可以组成$AB$的一个简系。根据前辈的博客,我们可以知道这种组成方式是$a_iB + b_jA$。

首先我们证明:$(a_iB + b_jA,AB) = 1$。
根据定义:$(a_i, A) = 1,(a_iB, A) = 1$。
很显然的一条结论是:$(a,n) = d, \Rightarrow (a \% n, n) = d$
证明:$(a = q*d, n = p*d, a - n = (q - p) * d)$。
所以$(a_iB + b_jA, A) = 1$。
同理可以证明$(b_jA + a_iB, B) = 1$。
所以$(a_iB + b_jA, AB) = 1$。

然后我们再证明$a_iB + b_jA$对$AB$两两不同余:
用反证法,假设它不成立,即存在:$a_iB + b_jA \equiv a_kB + b_lA\pmod{AB}$
同样很显然的一条定理是:$a\equiv b\pmod{mn} \Rightarrow a\equiv b\pmod{m}$
证明:$a = q*mn + r, b = p*mn + r, a\bmod{m} = b\bmod{m} = r\bmod{m}$
则:$a_iB + b_jA \equiv a_kB + b_lA\pmod{A}$
等价于:$a_iB \equiv a_kB\pmod{A}$
即:$A\mid a_iB, A\mid a_kB \Rightarrow A\mid (a_i - a_k)B$。且$(A,B) = 1$,所以$A\mid (a_i - a_k)$。
即:$a_i \equiv a_k\pmod{A}$。
根据定义这是不可能的事情。所以证明完啦。

最后我们来证明它的充分性:$AB$的简系$z$中的每个数都可以在$a_iB + b_jA$找到同余的数。
$(A, B) = 1,$所以一定存在$Ax + By = z$(对就是那个扩展欧几里得)
$(z,AB) = 1 \Rightarrow (Ax + By, A) = 1 \Rightarrow (By, A) = 1\Rightarrow (y, A) = 1 \Rightarrow$存在$a_i \equiv y\pmod{A}$。
同理可以证明存在$b_i \equiv x\pmod{B}$。
于是我们证明完了。

于是我们真的证明完了:$\phi(n)$是一个积性函数。

然后考虑$\phi$的取值:

  • 当$n = 1$时,$\phi(n) = 1$
  • 当$n = p^k$时:$[1,n]$中一共有$p^k$个数,由于$n$只有$p$这一个因数,所以所有不与$n$互质的数都可以用$t * p$表示。考虑$t$有多少种取值,显然有$\lfloor \frac{n}{p} \rfloor = p^{k - 1}$种。

所以$\phi(n) = p^k - p^{k - 1} = p^{k - 1}(p - 1)$。
$n = \Pi_{i = 1} ^ m p_i ^ {m_i}$。由于$\phi$是一个积性函数,所以:

$$ \begin{eqnarray} \phi(n) &= &\Pi_{i = 1}^m \phi(p_i ^ {m_i})\\ &= &\Pi_{i = 1}^m p_i^{k_i - 1}(p - 1)\\ &= &\Pi_{i = 1}^m p_i^{k_i}(1 - \frac{1}{p})\\ &= &\Pi_{i = 1}^m p_i^{k_i} \Pi_{i = 1}^m (1-\frac{1}{p_i})\\ &= &n \Pi_{i = 1}^m (1 - \frac{1}{p_i}) \end{eqnarray} $$

这也是欧拉函数通项公式的由来。

考虑当$n$的最小质因子是$d$且$d^2 \mid n$时用$d$和$\frac{n}{d}$求出$\phi(n)$。
其实这是显然的,因为$n$和$\frac{n}{d}$有用相同的质因子,即他们后面那一坨$\Pi (1 - \frac{1}{p})$是相同的,不同的仅仅是$\phi(\frac{n}{d}) = \frac{n}{d} * \Pi (1-\frac{1}{p_i})$,乘上$d$即可。

欧拉定理:当$(a,m) = 1$时,$a^{\phi(m)} \equiv 1\pmod{m}$
证明:$\phi(n)$个数构成$n$的简系$c$。$\forall i \ne j, c_i \not\equiv c_j\pmod{m}$。
对于集合$ac$,显然有$(ac_i, m) = 1$。
考虑是否有$ac_i \equiv ac_j\pmod{m}$。使用反证法,若成立,则$m \mid a(c_i - c_j)$。
由于$(a,m) = 1, m\nmid (c_i - c_j)$,所以此条件不成立。
所以$ac$是$m$的另一个简系。
所以$\Pi ac_i \equiv \Pi c_i\pmod{m}$,$a^{\phi(m)} \Pi c_i = \Pi c_i\pmod{m}$
由于$(\Pi c_i, m) = 1,$所以$a^{\phi(m)} \equiv 1\pmod{m}$。

欧拉函数的另一个性质:$n = \sum_{d\mid n} \phi(d)$。写出$\frac{i}{n} (i \in [1,n])$,化成最简分式$\frac{i / d_i}{n / d_i}(d_i = (i,n))$。可以发现此时会穷举与$n / d_i$互质的数。
顺便还可以得出,$(i, n) = d$的$i$共有$\phi(\frac{n}{d})$个。

莫比乌斯函数

莫比乌斯函数其实是根据卷积来定义的。
$F = f * I$,$F(n) = \sum_{d \mid n} f(d)$
我们考虑能否找到一个函数$\mu$,使得$\mu * F = f,$即$f(n) = \sum_{d\mid n}\mu(d) * F(\frac{n}{d})$。即找到函数$\mu * I = e$。
也就是使这个函数满足:

$$ \begin{eqnarray} &\sum_{d|n} I(d) * \mu(\frac{n}{d}) = e(n)\\ &\Downarrow\\ &\sum_{d|n} \mu(\frac{n}{d}) = \begin{cases} 1 &n = 1\\ 0 &n > 1 \end{cases} \end{eqnarray} $$

现在我们考虑怎么构造这个函数。

不难通过数学归纳法构造:

$$ \begin{eqnarray} \mu(1) &= &1\\ \mu(n) &= &-\sum_{d\mid n, d\neq n} \mu(\frac{n}{d}) \end{eqnarray} $$

当$n = p$时,$\mu(n) = -\mu(1) = -1$。
当$n = p^2$时,$\mu(n) = -(\mu(1) + \mu(p)) = 0$。
不难发现,当$n = p^k (k > 1)$时,$\mu(n) = -(\mu(1) + \mu(p) + \sum_{i = 2}^k \mu(k)) = 0$。
当$n = p_1p_2$时,$\mu(n) = -(\mu(1) + \mu(p_1) + \mu(p_2)) = 1$。
当$n = \Pi_{i = 1}^k p_i$时,$\mu(n) = -(\mu(1) + \sum_{i = 1}^k \mu(p_i) + \sum_{i, j \in[1,k] \&\& i \ne j}) \mu(p_ip_j).....)$
即$\mu(n) = -(\dbinom{k}{0} - \dbinom{k}{1} + \dbinom{k}{2}..... + (-1)^k\dbinom{k}{k}) =-(-1)^k$
当$n = p_1^2p_2$时,$\mu(n) = -(\mu(1) + \mu(p_1) + \mu(p_2) + \mu(p_1p_2)) = -(-\mu(p_1p_2) + \mu(p_1p_2)) = 0$。
当$n = \Pi_{i = 1}^m p_i ^ {k_i}$时,$\mu(n) = -(-\mu(\dfrac{\Pi_{i = 1}^m p_i^{k_i}}{p_i(i \in[1,m])}) + \mu(\dfrac{\Pi_{i = 1}^m p_i^{k_i}}{p_i(i \in[1,m])})) = 0$。
其实也可以将$\mu$看做容斥的系数。也就是说:

$$ \begin{eqnarray} \mu(n) = \begin{cases} 1 &n = 1\\ (-1)^k &n = \Pi_{i = 1}^k p_i\\ 0 &\mbox{others} \end{cases} \end{eqnarray} $$

所以莫比乌斯反演的证明就是$\mu$的定义。
或者我们也可以直接推导(其实这也是$\mu$的定义):

$$ \sum_{d\mid n} \mu(d) * F(\frac{n}{d}) = \sum_{d\mid n} \mu(d) * \sum_{k\mid \frac{n}{d}}f(k) = \sum_{d\mid n}\sum_{k\mid \frac{n}{d}}f(k) * \mu(d) = \sum_{k\mid n}f(k) * \sum_{d\mid n,k\mid \frac{n}{d}} \mu(d) = \sum_{k\mid n}f(k) * \sum_{d \mid \frac{n}{k}} \mu(d) $$

当$\frac{n}{k} > 1$时,$\sum_{d\mid \frac{n}{k}} \mu(d) = 0$。
当$\frac{n}{k} = 1, k = n$时,$\sum_{d\mid \frac{n}{k}} \mu(d) = 1$。
所以$$\sum_{k\mid n} f(k) * \sum_{d\mid \frac{n}{k}} \mu(d) = f(n)$$
相似的,我们可以推导莫比乌斯反演的第二种形式:

$$ F(n) = \sum_{n \mid d} f(d) \Rightarrow f(n) = \sum_{n \mid d}\mu(\dfrac{d}{n}) F(d) $$

令$t = \dfrac{d}{n},$则:

$$ \sum_{t} \mu(t) * F(nt) = \sum_{t} \mu(t) * (\sum_{nt \mid k} f(k)) = \sum_{n \mid k} f(k) * (\sum_{t \mid \frac{k}{n}} \mu(t)) $$

显然只有$\dfrac{k}{n} = 1, k = n$时$\sum_{t\mid \frac{k}{n}}\mu(t) = 1$,否则这一坨就是$0$。
由此我们可以知道:推公式的关键是灵活转换下标。
(所以我当时为什么会觉得莫比乌斯反演很难啊摔)

所以莫比乌斯函数的线性筛更加简单,任何$d^2\mid n$的$\mu(n) = 0$。

约数个数函数

首先它是一个积性函数。
显然,当$(a,b) = 1$时,$a$的任意一个因数乘以$b$的任意一个因数都可以为$ab$贡献一个因数。
好那么我们考虑,线性筛筛到$n$时有它的最小质因数$p$。
$p^2 \nmid n:$直接算。
$p^2 \mid n:$令$n = a * p^k, g = a * p^{k - 1}$。考虑这里$p$乘进去后对$i$的因数的贡献。
$n$的因数中不能被$p$整除的有$d_1, d_2, ..., d_m$(即$a$的因数),则:当$r \in [0, k - 2]$时,$p$不会对$d_i * p^r(i\in [1,m])$做出贡献(因为$d_i * p^{r + 1}$已经是$g$的因数)。所以$p$只能对$d_i * p^{k - 1}(i\in [1,m])$有贡献。
从$k - 1 = 0$开始,每加入一个$p$对因数产生$m$的贡献;那么加入了$k - 1$个$p$时因数个数就是$k * m$,再加入一个$p$因数个数就成了$(k + 1) * m$。
所以记录$k$,$d(n) = \dfrac{d(g)}{k} \times (k + 1)$。

约数和函数

首先它还是一个积性函数(不然线性筛个g啊)。
当$(a,b) = 1$,$a$的每一个因数和$b$的每一个因数乘起来都是$ab$的一个因数,而且不重不漏(非常显然),而显然$\sum \sum xy = \sum x * \sum y$,所以$\sigma(ab) = \sigma(a)\sigma(b)$。
然后我们再次考虑这玩意儿有没有什么简单的方式用$p$($n$的最小质因数)来计算$n$。
同样令$n = a * p^k, g = a * p^{k - 1}$,令$s = \sigma(a)$,$a$的因数分别为$d_i\ (i\in [1,m])$。
第$k$个加入的$p$只会对$d_i * p^{k - 1}\ (i \in [1,m])$产生贡献,也就是带来$d_i * p^k\ (i\in [1,m])$的贡献,即$p^k * s$的贡献。
于是乎,$n$的约数和就是:$s * (1 + p + p ^ 2 + p ^ 3 + ... + p^k)$。
其实这一步已经得到解法了,就是直接记录$p ^ k$和$sum(n) = (1 + p + p ^ 2 ... + p^k)$。
但是如果我们用一下等比数列求和,就会得到:
$\sigma(g) = s \dfrac{p^k - 1}{p - 1}, \sigma(n) = s \dfrac{p^{k + 1} - 1}{p - 1},$即$\sigma(n) = \dfrac{\sigma(g)}{p^k - 1} * (p ^ {k + 1} - 1)$。
可以简化掉一个小常数(^_^)。

Last modification:December 21st, 2018 at 09:20 pm

Leave a Comment