0%

算法 - ACM 数论大礼包

数论也是很重要的!

线性筛

1
2
3
4
5
6
7
8
9
10
11
12
13
const LL p_max = 1E6 + 100;
LL prime[p_max], p_sz;
void get_prime() {
static bool vis[p_max];
FOR (i, 2, p_max) {
if (!vis[i]) prime[p_sz++] = i;
FOR (j, 0, p_sz) {
if (prime[j] * i >= p_max) break;
vis[prime[j] * i] = 1;
if (i % prime[j] == 0) break;
}
}
}

设 $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 (f
g)(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}
$$

参考资料