算法 - ACM 数论大礼包

Posted on Edited on In Disqus:

数论也是很重要的！

线性筛

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 (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}
$$

参考资料