算法 - ACM 数论大礼包

Posted on Edited on In Comments:

数论也是很重要的！

线性筛

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=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\) 为素数，\(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} \]

参考资料