算法 - 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 中的最小素因子 ⇔ p 不超过 q 中的最小素因子。于是证明了每个合数会被筛去且仅会被筛去一次。

狄利克雷卷积

$$ (f*g)(n)=\sum_{d|n}f(d)g(\frac{n}{d}) $$

运算满足交换律、结合律、分配律。

单位函数为 ϵ(n) = [n = 1] （方括号为艾佛森括号），即 ϵ * f = f。

两个积性函数的卷积也为积性函数。

一些积性函数

  • σk(n) = ∑d|ndk
  • $\varphi(n)=\sum_{i=1}^n [(n,i)=1]$，具有性质 φ * 1 = id
  • 1 表示值恒为 1 的函数
  • idk(n) = nk
  • ϵ(n) = [n = 1]
  • $\begin{eqnarray}\mu(n) = \begin{cases} 1 & (n=1) \\(-1)^k & (n \ 为\ k\ 个不同素数之积) \\0 & (n\ 有平方因子)\end{cases}\end{eqnarray}$，具有性质 μ * 1 = ϵ。

莫比乌斯反演

形式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=f*1 \\ \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，那么由 $(f*g)(n)=\sum_{d|n}f(d)g(\frac{n}{d})$，得到 $f(n)=(f*g)(n)-\sum_{d|n,d<n}f(d)g(\frac{n}{d})$。 $$ \begin{eqnarray} g(1)S(n)&=&\sum_{i=1}^n (f*g)(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 为素数，pi 为第 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) $$ 那么最后要求的就是 gn, −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} $$ 为了求出 ∑pk < pi ≤ nf(pi)，需要处理出 f(pi) 的前缀和。由于 f(pi) 是关于 pi 的低阶多项式，那么 f(pi) 可以表示为完全积性函数 f′(pi) = piα 的倍数的和，可以对于每一项分别计算后合成。

令 $$ h_{n,k}=\sum_{\substack{i=2 \\ i \text{ 为素数或不含 } \le p_k \text{ 的素因子}}}^n f'(i) $$

这个式子相当于只考虑使用埃氏筛的时候处理到 pk 然后还没有被标记为合数的数。

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

  • hn, 0 就是一个等幂求和
  • pk2 > n 时有 hn, k = hn, k − 1
  • 需要的 hn, k 以及 gn, 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′(pi) 的前缀和
  • $\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(玄学) ，但是在正常的数据范围内（如 1013 内），还是优于 h 的。更加详细的复杂度证明还是参考论文吧。

一些积性函数求前缀和的例子

$S(n)=\sum_{i=1}^n \mu(i)$

使用杜教筛，配的积性函数是 1 * μ = ϵ。那么由 [n = 1] = ∑d|nμ(d)，得到 μ(n) = [n = 1] − ∑d|n, d < nμ(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)$

利用恒等式 μ2(n) = ∑d2|nμ(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} $$

其中 id2 * μ 是积性函数，复杂度 O(n)

离散对数与原根

暂且不讨论 p 为合数的情况。

离散对数

已知 a, b, p，定义 ax ≡ b (mod  p) 的解为 logab。

BSGS

设 $m = \lceil \sqrt p \rceil$，那么对于解 x 一定能表示成 im + j (j < m)。根据费马小定理，如果有解（p 为素数时一定有），那么 x mod  (p − 1) 一定也是解，所以令 x < p − 1。

那么只需要求 aim ≡ b ⋅ a−j (mod  p) 的解，等式两边取值个数不超过 m，中间相遇即可。

原根

在(a, m) = 1时，定义 a 对模 m 的指数 δm(a) 为使 ad ≡ 1 (mod  m)成立的最小的正整数 d。若 δm(a) = φ(m)，则称 a 是模 m 的原根。

模 m 有原根的充要条件是 m = 2, 4, pn, 2pn，其中 p 是奇素数，n 是任意正整数。原根个数为 φ(φ(m))。

如果 g 是模 p 的一个原根，那么所有原根可以表示为 {gk|(k, p − 1) = 1}。

指标

对于模 p 的原根 g，定义 I(a) 为使得 gd ≡ a (mod  m) 成立的最小的 d。 $$ I(ab) \equiv I(a) + I(b) \pmod {p-1} \\ I(a^k) \equiv kI(a) \pmod {p-1} $$

参考资料