算法 - ACM 数论大礼包
数论也是很重要的!
线性筛
1 | const LL p_max = 1E6 + 100; |
设 $C=pq$ 是一个合数,那么有—— $p$ 是 $C$ 中的最小素因子 $\Leftrightarrow$ $p$ 不超过 $q$ 中的最小素因子。于是证明了每个合数会被筛去且仅会被筛去一次。
狄利克雷卷积
$$
(f*g)(n)=\sum_{d|n}f(d)g(\frac{n}{d})
$$
运算满足交换律、结合律、分配律。
单位函数为 $\epsilon(n)=[n=1]$ (方括号为艾佛森括号),即 $\epsilon*f=f$。
两个积性函数的卷积也为积性函数。
一些积性函数
- $\sigma_k(n)=\sum_{d|n} d^k$
- $\varphi(n)=\sum_{i=1}^n [(n,i)=1]$,具有性质 $\varphi * 1=id$
- $1$ 表示值恒为 1 的函数
- $id_k(n)=n^k$
- $\epsilon(n)=[n=1]$
- $\begin{eqnarray}\mu(n) = \begin{cases} 1 & (n=1) \(-1)^k & (n \ 为\ k\ 个不同素数之积) \0 & (n\ 有平方因子)\end{cases}\end{eqnarray}$,具有性质 $\mu*1=\epsilon$。
莫比乌斯反演
形式1
$$
g(n) = \sum_{d|n} f(d) \Leftrightarrow f(n) = \sum_{d|n} \mu (d) g( \frac{n}{d}) \
g=f*1 \Leftrightarrow f=\mu * g
$$
简单证明
$$
g=f1 \
\mu * g = f*1 \mu = f * \epsilon = f
$$
形式2
$$
f(n)=\sum_{n|d}g(d) \Leftrightarrow g(n)=\sum_{n|d} \mu(\frac{d}{n}) f(d)
$$
简单证明
$$
\begin{eqnarray}
\sum_{n|d} \mu(\frac{d}{n}) f(d)
&=& \sum_{n|d}\mu(\frac{d}{n}) \sum_{d|t}g(t) \
&=& \sum_{n|t}g(t) \sum_{x|\frac{t}{n}}\mu(x) \
&=& \sum_{n|t}g(t)[n=t] \
&=& g(n)
\end{eqnarray}
$$
杜教筛
求 $S(n)=\sum_{i=1}^n f(i)$,其中 $f$ 是一个积性函数。
构造一个积性函数 $g$,那么由 $(fg)(n)=\sum_{d|n}f(d)g(\frac{n}{d})$,得到 $f(n)=(fg)(n)-\sum_{d|n,d<n}f(d)g(\frac{n}{d})$。
$$
\begin{eqnarray}
g(1)S(n)&=&\sum_{i=1}^n (fg)(i)-\sum_{i= 1}^{n}\sum_{d|i,d<i}f(d)g(\frac{n}{d}) \
&\overset{t=\frac{i}{d}}{=}& \sum_{i=1}^n (fg)(i)-\sum_{t=2}^{n} g(t) S(\lfloor \frac{n}{t} \rfloor)
\end{eqnarray}
$$
当然,要能够由此计算 $S(n)$,会对 $f,g$ 提出一些要求:
- $f*g$ 要能够快速求前缀和。
- $g$ 要能够快速求分段和(前缀和)。
- 对于正常的积性函数 $g(1)=1$,所以不会有什么问题。
在预处理 $S(n)$ 前 $n^{\frac{2}{3}}$ 项的情况下复杂度是 $O(n^{\frac{2}{3}})$。
Min_25 筛
如果问 Min_25 筛能否完全替代洲阁筛,那么答案是——是的。
求 $\sum_{i=1}^n f(i)$,其中 $f$ 是一个积性函数,而且 $f(p)$ 是一个关于素数 $p$ 的低阶多项式。
考虑像线性筛一样枚举 $i$ 的最小素因子:(公式中的 $p$ 为素数,$p_i$ 为第 $i$ 个素数,下标从 $0$ 开始)
$$
\begin{eqnarray}
\sum_{i=1}^n f(i)&=&1+
\sum_{\substack{2 \le p \le n}}
\sum_{\substack{2\le x\le n \ x \text{ 的最小素因子为 }p}}
f(x) \
&=&1+\sum_{2\leq p^e \leq n, e\geq1}
(1+\sum_{\substack{2\le x\le \lfloor \frac{n}{p^e} \rfloor \ x \text{ 不含有 } \le p \text{ 的素因子}}}f(x)) \
&=&1+\sum_{\substack{2\leq p^e \leq n, e\geq1 \ 2\le p \le \sqrt n}}
(1+\sum_{\substack{2\le x\le \lfloor \frac{n}{p^e} \rfloor \ x \text{ 不含有 } \le p \text{ 的素因子}}}f(x))
- \sum_{\sqrt n \le p \le n} f(p)\
\end{eqnarray}
$$
令
$$
g_{n,k}=\sum_{\substack{2\le x\le n \ x \text{ 不含 } \le p_k \text{ 的素因子}}} f(x)
$$
那么最后要求的就是 $g_{n,-1}+1$,根据之前的式子,有
$$
\begin{eqnarray}
g_{n,k}&=&\sum_{\substack{2\le x\le n \ x \text{ 不含 } \le p_k \text{ 的素因子}}} f(x) \
&=&
\sum_{\substack{p_k \lt p_i \le \sqrt n \ e \ge 1,p_i^e \le n}}
f(p_i^e) (1+\sum_{\substack{2\le x\le \lfloor \frac{n}{p_i^e} \rfloor \x \text{ 不含 } \le p_i \text{ 的素因子} }}) - \sum_{\sqrt n \lt p_i\le n} f(p_i) \
&=&
\sum_{p_k \lt p_i \le \sqrt n}(-f(p_i)+
\sum_{ e \ge 1,p_i^e \le n}f(p_i^e)(1+g_{\lfloor \frac{n}{p_i^e} \rfloor,i})) - \sum_{p_k \lt p_i\le n} f(p_i) \
\end{eqnarray}
$$
为了求出 $\sum_{p_k \lt p_i\le n} f(p_i)$,需要处理出 $f(p_i)$ 的前缀和。由于 $f(p_i)$ 是关于 $p_i$ 的低阶多项式,那么 $f(p_i)$ 可以表示为完全积性函数 $f’(p_i)=p_i^\alpha$ 的倍数的和,可以对于每一项分别计算后合成。
令
$$
h_{n,k}=\sum_{\substack{i=2 \ i \text{ 为素数或不含 } \le p_k \text{ 的素因子}}}^n f’(i)
$$
这个式子相当于只考虑使用埃氏筛的时候处理到 $p_k$ 然后还没有被标记为合数的数。
$$
\begin{eqnarray}
h_{n,k}&=&h_{n,k-1}- \sum_{\substack{i=2 \ i \text{ 为合数且最小素因子为 } p_k}}^n f’(i) \
&=&h_{n,k-1}-p_k^\alpha(h_{\lfloor \frac{n}{p_k} \rfloor,k-1}-h_{p_k-1,k-1}) \
&=&h_{n,k-1}-p_k^\alpha(h_{\lfloor \frac{n}{p_k} \rfloor,k-1}-\sum_{i=0}^{k-1} f’(p_i))
\end{eqnarray}
$$
- $h_{n,0}$ 就是一个等幂求和
- $p_k^2>n$ 时有 $h_{n,k}=h_{n,k-1}$
- 需要的 $h_{n,k}$ 以及 $g_{n,k}$ 中的 $n$ 的取值不会太多($\lfloor \frac{n}{ab} \rfloor = \lfloor \frac{\lfloor \frac{n}{a} \rfloor}{b} \rfloor$,$\lfloor \frac{n}{i} \rfloor$ 取值个数不超过 $2\sqrt n$)
- $n$ 需要离散化
- 只需要计算到 $p_k=\sqrt n$ 就能获得 $f’(p_i)$ 的前缀和
- $\sum_{i=0}^{k-1} f’(p_i)$ 可以在筛素数的时候顺便处理出来
- $h_{_,k}$ 只会由 $h_{_,k-1}$ 转移而来,按 $n$ 从大到小转移即可。
- 计算 $g$ 的过程中不记忆化(或者说不计算所有可能用到的值)效果会更好。
- 计算 $h$ 的复杂度 $O(\frac{n^\frac{3}{4}}{\log n})$,$g$ 的复杂度 $O(玄学)$ ,但是在正常的数据范围内(如 $10^{13}$ 内),还是优于 $h$ 的。更加详细的复杂度证明还是参考论文吧。
一些积性函数求前缀和的例子
$S(n)=\sum_{i=1}^n \mu(i)$
使用杜教筛,配的积性函数是 $1 *\mu =\epsilon$。那么由 $[n=1]=\sum_{d|n} \mu(d)$,得到 $\mu(n)=[n=1]-\sum_{d|n,d<n}\mu(d)$。
$$
\begin{eqnarray}
S(n) &=& \sum_{i=1}^n \mu(i) \
&=& 1 - \sum_{i=1}^n \sum_{d|i,d<i} \mu(d) \
&=& 1 - \sum_{t=2}^n S(\lfloor \frac n t \rfloor)
\end{eqnarray}
$$
$S(n)=\sum_{i=1}^n \mu^2(i)$
利用恒等式 $\mu^2(n)=\sum_{d^2|n} \mu(d)$(证明只需对 $n$ 有无平方因子分别验证),对式子进行变形计算。
$$
\begin{eqnarray}
S(n)&=&\sum_{i=1}^n \mu^2(i) \
&=& \sum_{i=1}^n \sum_{d^2|n} \mu(d) \
&=& \sum_{d=1}^\sqrt n \lfloor \frac n {d^2} \rfloor \mu(d)
\end{eqnarray}
$$
$S(n)=\sum_{i=1}^n\sum_{j=1}^m gcd(i,j)$
$$
\begin{eqnarray}
S(n) &=& \sum_{i=1}^n \sum_{j=1}^m gcd(i, j) \
&=& \sum_{i=1}^n \sum_{j=1}^m \sum_{d|gcd(i,j)} \varphi(d) \
&=& \sum_{d|i} \sum_{d|j} \varphi(d) \
&=& \sum_{d} \varphi(d) \lfloor \frac nd \rfloor \lfloor \frac md \rfloor
\end{eqnarray}
$$
$S(n)=\sum_{i=1}^n \sum_{j=1}^n gcd^2(i, j)$
$$
\begin{eqnarray}
S(n) &=& \sum_{i=1}^n \sum_{j=1}^n gcd^2(i, j) \
&=& \sum_{d} d^2 \sum_{i=1}^{\lfloor \frac nd \rfloor} \sum_{j=1}^{\lfloor \frac nd \rfloor} [i\perp j] \
&=& \sum_{d} d^2 \sum_{t} \mu(t) \lfloor \frac n{dt} \rfloor ^2 \
&\overset{x=dt}{=}& \sum_{x} \lfloor \frac nx \rfloor ^ 2 \sum_{d|x} d^2 \mu(\frac tx)
\end{eqnarray}
$$
其中 $id^2*\mu$ 是积性函数,复杂度 $O(n)$
离散对数与原根
暂且不讨论 $p$ 为合数的情况。
离散对数
已知 $a, b, p$,定义 $a^x \equiv b \pmod p$ 的解为 $\log_a b$。
BSGS
设 $m = \lceil \sqrt p \rceil$,那么对于解 $x$ 一定能表示成 $im+j\ (j < m)$。根据费马小定理,如果有解($p$ 为素数时一定有),那么 $x \bmod (p-1)$ 一定也是解,所以令 $x < p-1$。
那么只需要求 $a^{im} \equiv b \cdot a^{-j} \pmod p$ 的解,等式两边取值个数不超过 $m$,中间相遇即可。
原根
在$(a,m)=1$时,定义 $a$ 对模 $m$ 的指数 $\delta m(a)$ 为使 $a^d\equiv 1 \pmod m$成立的最小的正整数 $d$。若 $\delta m(a) = \varphi (m)$,则称 $a$ 是模 $m$ 的原根。
模 $m$ 有原根的充要条件是 $m=2,4,p^n,2p^n$,其中 $p$ 是奇素数,$n$ 是任意正整数。原根个数为 $\varphi(\varphi(m))$。
如果 $g$ 是模 $p$ 的一个原根,那么所有原根可以表示为 ${g^k | (k,p-1)=1}$。
指标
对于模 $p$ 的原根 $g$,定义 $I(a)$ 为使得 $g^d \equiv a \pmod m$ 成立的最小的 $d$。
$$
I(ab) \equiv I(a) + I(b) \pmod {p-1} \
I(a^k) \equiv kI(a) \pmod {p-1}
$$
参考资料
- 浅谈一类积性函数的前缀和
- 国家集训队 2016 论文《积性函数求和的几种方法》任之洲
- [min25筛学习小记]LOJ6053
- Min_25筛学习小记
- 国家集训队 2018 论文《一些特殊的数论函数求和问题》 朱震霆
- https://zh.wikipedia.org/wiki/%E5%8E%9F%E6%A0%B9
- https://zh.wikipedia.org/wiki/%E7%A6%BB%E6%95%A3%E5%AF%B9%E6%95%B0
- http://nanoape.is-programmer.com/posts/192658.html