关于数论

· · 个人记录

以前学了很多数论内容，却都缺少了一个严谨的定义或是证明，这里将作一个补充。

基础

欧几里得算法

\text{Theorem 1.1}:\gcd(a,b)=\gcd(b,a\bmod b)

求解众所周知的 \gcd(a,b) 。

证明：注意到 a \bmod b=a-kb ，那么令 g=gcd(a,b) ，则 g\mid a 且 g\mid b ，显然 g\mid a-kb 。

令 a=pg ， b=qg ，则有 p\bot q 。那么目标转为证明 q \bot p-kq ，即：

\text{Lemma 1.1}:q \bot p-q

不妨假设 \gcd(q,p-q)=d\neq 1 。那么有 d \mid p-q 且 d \mid q ，则 d \mid p ，即 gcd(p,q)\neq 1 ，与 p\bot q 冲突，那么假设不成立。

定理得证。

乘法逆元

a\times a^{-1} \equiv 1 \pmod {p}

则称 a^{-1} 是 a 在 \bmod p 意义下的乘法逆元。

注意到前提条件是 \gcd(a,p)=1 。

证明：原式等价于 ax+kp=1 ，而显然 \gcd(a,p)\mid ax+kp ，那么 \gcd(a,p)\mid 1 ，即 \gcd(a,p)=1 。

严谨的定义可能需要用到域。

显然我们可以使用扩展欧几里得算法或费马小定理来获取逆元，但这里还有一种线性递推求解的方式。考虑：

p=ak+r

即：

r\equiv p \pmod a

我们有 r < a 。

那么：

\begin{aligned} ak+r &\equiv 0 \pmod p\\ r^{-1}\times k+a^{-1} &\equiv 0 \pmod p\\ a^{-1} &\equiv kr^{-1} \pmod p\\ \end{aligned}

费马小定理

\text{Theorem 1.2}:a^{p-1}\equiv 1 \pmod {p}

其中 a\nmid p ， p 为一个素数。

证明：注意到 a,2a,3a,\dots (p-1)a 在 \bmod p 意义下是互不相同的。

假设存在 x,y<p ， 使得 ax\equiv ay \pmod p 。而 a\bot p ，则有 x\equiv y \pmod p ，与定义不符。

那么有：

\begin{aligned} \prod_{k=1}^{p-1} ka&\equiv(p-1)!\pmod p\\ a^{p-1}\times (p-1)!&\equiv(p-1)!\pmod p\\ a^{p-1}&\equiv 1 \pmod p \end{aligned}

定理得证。

注意到证明过程中我们要求 \forall a<p ， a^{-1}\pmod p 存在。

欧拉函数

\varphi(n)=\sum_{k=1}^n[k\bot n]

其中 \varphi(n) 称欧拉函数，是积性函数。

考虑如何快速求取单个 \varphi(n) ，我们有：

\varphi(n)=n\times \prod_{p \mid n}\frac {p-1}p

其中 p 是一个素数。

考虑 n 的唯一分解形式：

n=\prod_{i=1}^m p_i^{k_i}

则有：

\begin{aligned} \varphi(n)&=\prod_{i=1}^m \varphi(p_i^{k_i})\\ &=\prod_{i=1}^m p_i^{k_i}-p_i^{k_i-1}\\ &=\prod_{i=1}^mp_i^{k_i}\times (1-\frac 1{p_i})\\ &=n\times \prod_{p \mid n}\frac {p-1}p \end{aligned}

另外注意到：

n=\sum_{d\mid n} \varphi(d)

对于 k\in [1,n] ，若 \gcd(n,k)=d ，则 \gcd(\dfrac nd,\dfrac kd)=1 ，那么 \varphi(\dfrac nd) 就对所有这样的 k 计数。且注意到每个 k 唯一对应一个 d ，那么每个 k 仅会被计数一次。因此我们枚举 n 的所有因子，也就不重不漏的考虑了所有 k\in[1,n] 。

欧拉定理

\text{Theorem 1.3}:a^{\varphi(m)}\equiv 1 \pmod{m}

其中 a\bot m 。

证明：仿照费马小定理的证明方式，我们注意到 ak_1,ak_2,\dots ak_{\varphi(m)} 在 \bmod m 意义下是互不相同的，且根据引理1.1它们都与 m 互素。其中 \{k_{\varphi(m)}\} 构成了 \bmod m 意义下的缩系。

那么有：

\begin{aligned} \prod_{i=1}^{\varphi(m)}ak_i&\equiv \prod_{i=1}^{\varphi(m)} k_i \pmod m\\ a^{\varphi(m)}\times \prod_{i=1}^{\varphi(m)} k_i &\equiv \prod_{i=1}^{\varphi(m)} k_i \pmod m\\ a^{\varphi(m)}&\equiv 1 \pmod m\\ \end{aligned}

注意到以上的推导要求 a 和 \{k_{\varphi(m)}\} 与 m 互素。

杂项

中国剩余定理

\begin{cases} x\equiv a_1 \pmod {m_1}\\ x\equiv a_2 \pmod {m_2}\\ \cdots\\ x\equiv a_n \pmod {m_n}\\ \end{cases}

求解 x ，其中 m_1,m_2,\dots m_n 互素。

\text{Theorem 2.1}:x=\sum_{i=1}^nai\prod_{j\neq i}^n m_j\times\left(\left(\prod_{j\neq i}^n m_j\right)^{-1}\pmod{m_i}\right)

证明：其实这个定理来源于构造。

观察式子，不难发现在每个同余式中，除对应 a_i 项以外的系数均为 0 ，且 a_i 项的系数为 1 ，那么其必然满足约束。

且注意到若给 x 加上若干个 \prod_{i=1}^nm_i ，同余方程组仍然成立，即我们构造出的这个解是在 \bmod \prod_{i=1}^nm_i 意义下的。

而我们以上的推导均是在 \left(\prod_{j\neq i}^n m_j\right)^{-1}\pmod{m_i} 存在的前提下进行的，也就是说这里需要用到 m_1,m_2,\dots m_n 互素的条件。

扩展中国剩余定理

用于求解同余方程组的模数并不互素的情况。

我们考虑如何合并两个同余式：

\begin{cases} x \equiv a_1 \pmod {m_1}\\ x \equiv a_2 \pmod {m_2}\\ \end{cases}

显然其等价于：

\begin{cases} x = a_1 + k_1\times m_1\\ x = a_2 + k_2\times m_2\\ \end{cases}

联立可得：

k_1m_1-k_2m_2=a_2-a_1

我们解这个方程即可得出当前的解 x_0 。且注意到我们若给 x_0 加上若干个 \operatorname{lcm}(m_1,m_2) ，上式仍然成立，即当前的解是在 \bmod \operatorname{lcm}(m_1,m_2) 意义下的。这样我们得出新的同余式：

x\equiv x_0 \pmod {\operatorname{lcm}(m_1,m_2)}

与其它式子继续合并即可。

卢卡斯定理

\text{Theorem 2.2}:\binom{n}{m}=\binom{n\bmod p}{m\bmod p}\times \binom{\lfloor n \div p \rfloor}{\lfloor m \div p \rfloor} \pmod {p}

其中 p 为一个素数。

证明：首先我们需要证明这样一个引理：

\text{Lemma 2.1}:(a+b)^p\equiv a^p+b^p \pmod {p}

考虑 \large\binom{p}{m} 的形式，即 \dfrac{p^{\underline{m}}}{m!} 。那么由于 p 是一个素数，只有当 m 为 0 或是 p 时，其不含 p 这个因子，否则 {\large\binom {p}{m}}\equiv 0 \pmod p 。则式 (a+b)^p 在 \bmod p 意义下展开后只会包含 0 次和 p 次项，引理得证。

接下来我们考虑式 (1+x)^n ，有：

\begin{aligned} (1+x)^n &\equiv (1+x)^{p\times \lfloor n\div p\rfloor} \times (1+x)^{n \bmod p} \pmod p\\ (1+x)^n &\equiv (1+x^p)^{\lfloor n\div p\rfloor} \times (1+x)^{n \bmod p} \pmod p\\ \end{aligned}

考虑恒等号右边两式的卷积，式 (1+x^p)^{\lfloor n\div p\rfloor} 只具有 p 的倍数次项，式 (1+x)^{n \bmod p} 的次数小于 p ，那么对于结果中任意的一项 x^m ，其系数仅来源于 {\large\binom{\lfloor n\div p\rfloor}{\lfloor m\div p\rfloor}}\times {\large\binom{n \bmod p}{m \bmod p}} 这一种方式，对应到左式，即有 {\large\binom{n}{m}}={\large\binom{n\bmod p}{m\bmod p}}\times {\large\binom{\lfloor n \div p \rfloor}{\lfloor m \div p \rfloor}} \pmod {p} ，定理得证。

其实可以看出这是一种生成函数的证法。

扩展卢卡斯定理

其实就是模意义下快速阶乘算法。

目标是在模意义下快速计算组合数，但是此时我们不能保证模数 p 为一个素数。

为了使得逆元存在，我们不妨把 p 唯一分解，最后再用中国剩余定理合并答案即可。

考虑：

\binom{n}{m}=\frac{n!}{m!(n-m)!}=\frac{\frac{n!}{p^x}}{\frac{m!}{p^y}\frac{(n-m)!}{p^z}} \times p^{x-y-z}

现在的问题是快速计算：

\frac{n!}{p^x}\pmod {p^t}

考虑 n! ，我们有：

\begin{aligned} n!&\equiv\prod_{k=1}^n k \pmod {p^t}\\ &\equiv\prod_{p\mid k}^nk\times\prod_{p\nmid k}^n k \pmod {p^t}\\ &\equiv p^{\lfloor n\div p\rfloor}\times \left(\left\lfloor\frac{n}{p}\right\rfloor!\right)\times\left(\prod_{p\nmid k}^{p^t}k\right)^{\lfloor n\div p^t\rfloor} \times \left(\prod_{p\nmid k}^{n\bmod p^t} k\right) \pmod {p^t} \end{aligned}

而对于 \dfrac{n!}{p^x} ， p^{\lfloor n\div p\rfloor} 项是会被约掉的。但是 \left\lfloor\dfrac{n}{p}\right\rfloor! 项中仍可能包因子 p ，所以我们不妨定义函数 f(n)=\dfrac{n!}{p^x} ，则有：

f(n)\equiv f(\left\lfloor\dfrac{n}{p}\right\rfloor)\times\left(\prod_{p\nmid k}^{p^t}k\right)^{\lfloor n\div p^t\rfloor} \times \left(\prod_{p\nmid k}^{n\bmod p^t} k\right) \pmod {p^t}

这样我们便有：

\binom{n}{m}\equiv\frac{f(n)}{f(m)\times f(n-m)} \times p^{x-y-z} \pmod {p^t}

扩展欧拉定理

\text{Theorem 2.3}:a^b \equiv \begin{cases} a^b &(b<\varphi(m))\\ a^{b\bmod \varphi(m)+\varphi(m)} &(b\geq \varphi(m))\\ \end{cases} \pmod m

证明：当 b<\varphi(m) ，显然。

当 b\geq \varphi(m) ，我们考虑先把 m 唯一分解为 p_1^{k_1}\times p_2^{k_2}\times \dots \times p_3^{k_3} 的形式，然后我们对于每个 p_i^{k_i} 分别证明：

a^b \equiv a^{b \bmod \varphi(m)+\varphi(m)} \pmod {p_i^{k_i}}

即可使用以下引理合并答案：

\text{Lemma 2.2}: \text{If } \begin{cases} x \equiv y \pmod {m_1}\\ x \equiv y \pmod {m_2}\\ \end{cases} \text{ , then } x\equiv y \pmod {m_1m_2}

其中 m_1\bot m_2 。

考虑原式等价于

\begin{cases} x=y+k_1m_1\\ x=y+k_2m_2\\ \end{cases}

则 k_1m_1=k_2m_2 。因为 m_1\bot m_2 ，那么 m_2\mid k_1 且 m_1\mid k_2 ，则我们有 x=y+k_3m_1m_2 ，即：

x=y \pmod{m_1m_2}

若 \gcd(a,p_i^{k_i})=1 ，那么由于欧拉函数具有积性， a^{\varphi(m)}=1\pmod {p_i^{k_i}} ，则上式成立。

否则 p\mid a ，我们有：

b\geq \varphi(m)\geq \varphi(p_i^{k_i})\geq k_i

因为若把 p_i^{k_i} 按照 p_i 分为 k_i 段，则每段大小至少为 2 ，且仅含一个数不与 p_i^{k_i} 互素，且欧拉函数具有积性。

那么 p_i^{k_i} \mid a^b ，我们有：

a^b \equiv a^{b \bmod \varphi(m)+\varphi(m)} \equiv 0 \pmod {p_i^{k_i}}

根据引理2.2，定理得证。

阶

对于 a \bot m ，满足式 a^n\equiv 1 \pmod m 的最小正整数 n 存在，称其为 a 模 m 的阶，记作 \delta_m(a) 。

注意到 \delta_m(a)\mid \varphi(m) 。考虑若 \delta_m(a)\nmid \varphi(m) ，则有 \varphi(m)=k\delta_m(a)+r ，其中 r<\delta_m(a) ，那么：

\begin{aligned} a^{k\delta_m(a)+r} &\equiv 1 \pmod m\\ (a^{\delta_m(a)})^k\times a^r &\equiv 1 \pmod m\\ a^r &\equiv 1 \pmod m \end{aligned}

这与 \delta_m(a) 的定义矛盾，则这样的 r 不存在。

原根

对于 a \bot m ，若 \delta_m(a)=\varphi(m) ，则称 a 为模 m 的原根。

注意到 a 为模 m 的原根当且仅当 a^0,a^1,\dots a^{\varphi(m)-1} 两两不同。

考虑若存在 x\neq y 且 x,y < \varphi(m) ，使得 a^x\equiv a^y ，那么显然的 a^{|x-y|}\equiv 1\pmod m ，其中 |x-y|<\varphi(m) ，与原根的定义矛盾。

且模 n 存在原根当且仅当 n=1,2,4,p^k,2p^k ，其中 p 为一个素数。

离散对数

令 g 为模 m 的原根，则 \forall a\bot m ，均存在 k 使得 g^k\equiv a\pmod m 。

因为目前没有见过围绕原根的题目，而且本人也不会阶、原根和离散对数的诸多性质与其证明，所以这里暂且略过这个部分。

二次剩余

即求解同余方程：

x^2\equiv n \pmod p

若解存在，则称 n 为二次剩余，否则称其为非二次剩余。

这里仅讨论 p 为奇素数的情况。

解的数量

不妨假设原方程存在多个解，即存在 x_0\neq x_1 ，使得 x_0^2\equiv x_1^2 \pmod p ，那么：

(x_0-x_1)\times (x_0+x_1)\equiv 0 \pmod p

显然 x_0+x_1\equiv 0 \pmod p ，即 x_0 与 x_1 是一对在 \bmod p 意义下的相反数。那么对于二次剩余 n\neq 0 ，我们可以断言其必然有且仅有两个不同的合法解 x_0 和 x_1 。

而在 \bmod p 的意义下，x_0 和 x_1 的奇偶性必然是不同的，且 x_0 和 x_1 是一一对应的，其同样唯一决定了一个二次剩余 n 。那么显然 \bmod p 意义下的一对相反数 x_0 和 x_1 和二次剩余 n 是双射关系。

到这里我们可以断言 \bmod p 意义下非 0 二次剩余的数量恰为相反数的对数 \dfrac {p-1}2 ，而其它的非 0 数均为非二次剩余，数量也恰为 \dfrac {p-1}2 。

欧拉准则

\text{Theorem 2.4}:n\text{ 是}\bmod p \text{ 意义下的二次剩余，当且仅当 }n^{\frac {p-1}2}\equiv 1 \pmod p\text{ 。}

先证充分性：令 g 为 \bmod p 意义下的原根，则 n=g^k\pmod p 。

若 n^{\frac {p-1}2}\equiv 1 \pmod p ，则 g^{k\times \frac {p-1}2}\equiv 1 \pmod p 。注意到 p-1\mid k\times \dfrac {p-1}2 ，则必然有 2 \mid k 。那么 g^{\frac k2} 即为二次剩余 n 的解，n 是 \bmod p 意义下的二次剩余。

再证必要性：观察费马小定理，我们可以得到 n^{2\times \frac {p-1}2}\equiv 1\pmod p ，也就是说 n^{\frac {p-1}2} 是二次剩余 1 的解，则有以下引理：

\text{Lemma 2.3}:n^{\frac {p-1}2}\equiv \pm 1\pmod p

若 n 为二次剩余，则 n^{\frac {p-1}2}\equiv(x^2)^{\frac {p-1}2}\equiv x^{p-1}\equiv 1\pmod p 。

那么定理成立。

二次探测定理

\text{Theorem 2.5}:\text{If } x^2 \equiv 1 \pmod p\text{ , then }x\equiv \pm 1 \pmod p

其中 p 为一个素数。

证明：对原式做变换：

\begin{aligned} x^2 &\equiv 1 \pmod p\\ (x+1)(x-1) &\equiv 0 \pmod p\\ \end{aligned}

因为 p 为素数，则 p\mid x-1 或 p\mid x+1 ，即 x=\pm 1 \pmod p 。

筛法

由于这一类实在太大所以单独列出来。

数论函数

定义域为正整数，值域是复数的子集的函数称为数论函数。

积性函数

对于数论函数 f ，若 \forall a\bot b ，有 f(a\times b)=f(a)\times f(b) ，则称 f 是积性函数。

若 \forall a,b \in \mathbb {N^*} ，有 f(a\times b)=f(a)\times f(b) ，则称 f 是完全积性函数。

对于积性函数 f ，我们通常研究其在素数和素数的幂上的取值。

一些函数

单位函数

\epsilon(n)=[n=1]

其中 \epsilon(n) 称单位函数，[\text{conditon}] 为艾弗森记号。

#### 除数函数 $$ \sigma_k(n)=\sum_{d\mid n}d^k $$ 其中 $\sigma_k(n)$ 称除数函数，即 $n$ 的因子的 $k$ 次方之和。 $\sigma_0(n)$ 常记作 $d(n)$ ，$\sigma_1(n)$ 常记作 $\sigma(n)$ 。 $\sigma_k(n)$ 是积性函数。 #### 幂函数 $$ {\rm Id}_k(n)=n^k $$ 其中 ${\rm Id}_k(n)$ 称幂函数，是积性函数。 ${\rm Id}_1$ 记作 ${\rm Id}$ 。 #### 欧拉函数 见上文。 #### 莫比乌斯函数 $$ \mu(n)= \begin{cases} 1 &(n=1)\\ (-1)^k & (n=p_1p_2\dots p_k)\\ 0& ({\rm otherwise}) \end{cases} $$ 其中 $\mu(n)$ 称欧拉函数，是积性函数。 $p_i$ 是素数。 $\mu$ 具有如下的最重要的性质： $$ \sum_{d\mid n}\mu(d)=\epsilon(n) $$ 当 $n=1$ 时显然。 而当 $n\neq 1$ 时，设 $n$ 的唯一分解具有 $k$ 个不同的素因子，否则 $\mu(n)=0$ ，那么： $$ \sum_{d\mid n} \mu(n)=\sum_{i=0}^k (-1)^k\binom ki=(1-1)^k=0 $$ 另有莫比乌斯反演定理，其指出： $$ g(n)=\sum_{d\mid n}f(d) $$ 成立，当且仅当： $$ f(n)=\sum_{d\mid n}\mu(\frac nd)g(d) $$ 称 $g$ 为 $f$ 的莫比乌斯变换， $f$ 为 $g$ 的莫比乌斯逆变换。 证明则非常简洁： $$ g=f*1\Leftrightarrow f=f*\epsilon=f*1*\mu=g*\mu $$ ### 线性筛 常见的用法是筛素数。 但实际上对于任意一个积性函数，若其在素数处的取值可以被快速计算，那么我们就可以在线性的时间复杂度内筛出其某个前缀范围内的值。因为在线性筛的过程中我们可以求出每个数的最小素因子及其幂次。 ### 埃氏筛 即枚举每个素数，并筛掉它们的倍数，时间复杂度是 $O(n\log \log n)$ 的。 ### 整除分块 筛法的基石之一。 对于形如： $$ \sum_{i=1}^n\left\lfloor\frac ni\right\rfloor $$ 的式子，我们可以通过同时考虑 $\left\lfloor\dfrac ni\right\rfloor$ 相等的 $i$ 而在 $O(\sqrt n)$ 的时间复杂度内计算。 实际上其基于这样的事实：一个数的因数个数是 $O(\sqrt n)$ 级别的，因此我们最多也只会分出 $O(\sqrt n)$ 个不同的块来。 ### 迪利克雷卷积 $$ h(n)=\sum_{d\mid n} f(d)\times g(\frac nd) $$ 称 $h$ 为 $f$ 和 $g$ 的迪利克雷卷积，记作 $h=f*g$ 。 其实其等价于乘法卷积。 迪利克雷卷积具有单位元，是 $\epsilon$ ，即 $f*\epsilon=f$ 。其同样具有交换律和结合律。 另外若 $f$ ，$g$ 都为积性函数，则 $f*g$ 同为积性函数。 ### 杜教筛 实际上是利用迪利克雷卷积来构造递推式，从而对一些积性函数快速求和的方法。 我们现在考虑求取积性函数 $f$ 的前缀和 $F$ 。设存在函数 $g$ ，使得 $f*g$ 的前缀和可以被快速计算，那么： $$ \begin{aligned} \sum_{k=1}^n(f*g)(k) &=\sum_{k=1}^n\sum_{d\mid k}f(\frac kd)\times g(d)\\ &=\sum_{d=1}^n\sum_{k=1}^{\lfloor n\div d \rfloor} f(k) \times g(d)\\ &=\sum_{d=1}^ng(d)\times F(\left\lfloor\frac nd\right\rfloor)\\ &=\sum_{d=2}^ng(d)\times F(\left\lfloor\frac nd\right\rfloor)+g(1)\times F(n)\\ \end{aligned} $$ 则： $$ F(n)=\left(\sum_{k=1}^n(f*g)(k)-\sum_{d=2}^ng(d)\times F(\left\lfloor\frac nd\right\rfloor)\right)\div g(1) $$ 若 $f*g$ 的前缀和可以被快速计算，我们就可以使用整除分块，从而把 $F(n)$ 划分为若干个子问题。 注意到实际上我们只会计算 $n$ 的所有因子处的 $F$ 的值，那么我们可以估计杜教筛的时间复杂度 $T(n)$ ： $$ T(n)=\sum_{k=1}^{\sqrt{n}} O(\sqrt{k})+\sum_{k=1}^{\sqrt{n}}O\left(\sqrt{\left\lfloor\frac nk\right\rfloor}\right) $$ 对于渐进意义较大的第二项，我们使用积分估计： $$ \sum_{k=1}^{\sqrt{n}}O\left(\sqrt{\left\lfloor\frac nk\right\rfloor}\right)=O\left(\int_1^{\sqrt{n}}\sqrt{\frac nx}\ {\rm d}x\right)=O(n^{\frac 34}) $$ 实际上我们可以使用线性筛来预处理 $F$ 的前 $n^{\frac 23}$ 项，这样杜教筛的时间复杂度降至 $O(n^{\frac 23})$ 。 ### Min-25 筛 Min-25 筛本质上是对埃氏筛进行了扩展，用于求解积性函数的前缀和，要求其在质数与质数的次幂处的取值可以被快速计算。 下面对 Min-25 筛的运行过程做一个简要的推导： 记 $\mathbb P$ 中的数为 $p$ ，$p_k$ 为 $\mathbb P$ 中第 $k$ 小的数，${\rm lpf}(n)$（ $\rm lowest\ prime\ factor$ ）为 $n$ 的最小素因子，$F(n)=\sum_{p\le n}f(p)$ ，$F_k(n)=\sum_{i=2}^n[p_k\le{\rm lpf}(i)]f(i)$ ，不难发现答案即为 $F_1(n)+1$ 。 考虑在 $F_k$ 与 $F$ 之间建立递推关系，从素因子的角度出发，并应用积性函数的性质，我们有： $$ \begin{aligned} F_k(n)&=\sum_{i=1}^n[{\rm lpf}(i)\ge k]f(i) \\ &=\sum_{i\ge k,p_i^2\le n}\sum_{c\ge 1,p_i^c\le n} f(p_i^c)\times([c>1]+F_{k+1}(n/p_i^c))+F(n)-F(p_{k-1})\\ \end{aligned} $$ 现在的问题在于如何快速求取 $F$ 。首先可以注意到只有 $O(\sqrt n)$ 处的 $F_k$ 和 $F$ 的取值对我们来说是有用的，这一点保障了我们的计算复杂度。现在我们只关注 $f$ 在质数处的取值，在具体的问题中，这一部分往往可以被表示为一个低次多项式，因此我们可以考虑分别计算每一项的贡献，最后再把它们加起来。也就是说现在我们只需要求 $g(n)=n^s$ 在只考虑素数处的取值的情况下的前缀和。注意到 $g$ 具有非常优美的性质，其是一个完全积性函数，因此我们考虑构造 $G_k(n)=\sum_{i=2}^n[{\rm lpf}(i)>p_k \or i \in {\mathbb P}]g(i)$ ，即埃氏筛第 $k$ 轮以后剩下的数处的 $g$ 的取值之和。从埃氏筛的过程入手，我们考虑如何递推求解 $G_k(n)$ ，即： 1. 对于 $p_k^2>n$ ，显然，所有满足的条件的数都会是素数，因此 $G_k(n)=G_{k-1}(n)$ 。 2. 否则我们希望去除掉所有 ${\rm lpf}$ 为 $p_k$ 的合数处的取值，即减去 $g(p_k)G_{k-1}(n/p_k)$ 。 3. 在第 $2$ 步中会多减一部分，这部分均仅含一个小于 $p_k$ 的素因子，因此我们加上 $g(p_k)G_{k-1}(p_{k-1})$ 。 概括一下，我们有： $$ G_k(n)=G_{k-1}(n)-[p_k^2\le n]g(p_k)(G_{k-1}(n/p_k)-G_{k-1}(p_{k-1})) $$ 为了分析 Min-25 筛的时间复杂度，我们将其分为两部分看待。第一部分，即通过构造完全积性函数来获取 $F$ ，的时间复杂度是 $O(\dfrac {n^{3/4}}{\log n})$ ；而第 $2$ 部分，即通过 $F$ 来递推获取 $F_k$ ，存在两种实现方法。若直接按照递推式来暴力计算，时间复杂度为 $O(n^{1-\epsilon})$ ；或者我们可以选择从大到小枚举 $p$ 来转移，并使用后缀和优化，时间复杂度为 $O(\dfrac {n^{3/4}}{\log n})$ 。一般认为第一种更易于实现，且在数据规模较小时的表现往往要优于后者，因此 Min-25 筛的时间复杂度可以认为是 $O(\dfrac {n^{3/4}}{\log n}+n^{1-\epsilon})$ 。 ## 算法 ### 扩展欧几里得算法 用于求解线性方程组： $$ ax+by=\gcd(a,b) $$ 考虑朴素欧几里得算法的过程，最后一步必然 $a=g$ 且 $b=1$ ，那么此时 $x=1$ 且 $y=0$ 是合法的。 那么到上一步，我们获得了方程 $bx+(a\bmod b)y=g$ 的解。考虑做一下变换： $$ \begin{aligned} bx+(a\bmod b)\times y&=g\\ bx+(a-b\times \left\lfloor\frac ab\right\rfloor)\times y&=g\\ ay+b(x-\left\lfloor\frac ab\right\rfloor y)&=g\\ \end{aligned} $$ 那么我们就可以递归的求解这个方程了。 #### 一般线性方程组及其解的结构 即求解线性方程组： $$ ax+by=c $$ 显然其存在解当且仅当 $\gcd(a,b) \mid c$ ，这也就是斐蜀定理。 那么我们解方程： $$ ax'+by'=\gcd(a,b) $$ 再在上式左右同乘 $\dfrac c{\gcd(a,b)}$ 即可。 但这样得出的解并不一定是最小非负整数解。我们知道： $$ \begin{aligned} ax+by+kd-kd&=c\\ a\times (x+k\times \frac da)+b\times (y+k\times \frac db) &=c\\ \end{aligned} $$ 当方程的解为整数，显然 ${\rm lcm}(a,b)\mid d$ 。而我们期望找到一个最小的满足条件的 $d$ ，也就是说 $d={\rm lcm}(a,b)$ 。那么方程的通解就是 $x+k\times \dfrac b{\gcd(a,b)}$ 和 $y-k\times \dfrac a{\gcd(a,b)}$ 。 ### 大步小步算法 用于求解同余方程： $$ a^b\equiv x \pmod p $$ 其中$a$ ， $x$ 已知， $p$ 是一个素数。 由费马小定理我们有 $a^0=a^{p-1}$ ，也就是说若解存在，则其必然小于 $p-1$ 。 我们考虑将 $b$ 表示为 $kq+r$ 的形式，其中 $r<q$ 。那么我们可以通过预处理用哈希表来保存 $a^r$ ，并枚举 $k$ ，同时查表来遍历所有小于 $p-1$ 的指数，以获取合法的最小解。时间复杂度 $O(\dfrac pq+q)$ ，当 $q=\sqrt{p}$ 时，其达到最小值 $O(\sqrt{p})$ 。 ### 扩展大步小步算法 用于求解同余方程： $$ a^b\equiv x \pmod p $$ 其中$a$ ， $x$ 和 $p$ 已知。 观察到在以前的步骤中，我们要求 $a$ 在 $\bmod p$ 意义下存在逆元。我们设 $g=gcd(a,p)$ ，那么： $$ \begin{aligned} a^{b-1}\times \frac ag &\equiv \frac xg \pmod {\frac pg}\\ a^{b-1} &\equiv \frac xg\times \left(\frac ag\right)^{-1} \pmod {\frac pg}\\ \end{aligned} $$ 这和我们的目标是相同的形式。所以我们考虑递归的求解这个问题，直到 $a\bot p$ 。此时我们可以套用大步小步算法。 ### Cipolla 算法 用于求解同余方程： $$ x^2\equiv n \pmod p $$ 其中 $p$ 是一个奇素数。 我们考虑找到一个数 $a$ 满足 $a^2-n$ 是非二次剩余。由于非二次剩余的数量为 $\dfrac {p-1}2$ ，通过随机的方式我们可以快速找到这样一个 $a$ 。 接下来我们定义 $i^2=a^2-n$ ，然而 $a^2-n$ 并不是二次剩余，也就是说在目前的数域上我们找不到这样一个 $i$ 。 类比实数域到负数域的推广，我们不妨考虑将 $\bmod p$ 意义下的所有数表示为 $a+bi$ 的形式，这样我们就得到了一个对复数的离散模拟。 那么有结论： $$ \text{Theorem 3.1}:(a+i)^{p+1}\equiv n \pmod p $$ 我们先考虑这样一个引理： $$ \text{Lemma 3.1}:i^p\equiv -i \pmod p $$ 证明：按定义：$i^p \equiv i\times (i^2)^{\frac {p-1}2}\equiv i\times (a^2-n)^{\frac {p-1}2}$ 。 那么根据引理2.3，有 $i^p\equiv -i \pmod p$ ，引理得证。 再考虑引理2.1，我们有： $$ \begin{aligned} (a+i)^{p+1} &\equiv (a^p+i^p)\times (a+i) \pmod p\\ &\equiv (a-i)\times (a+i) \pmod p\\ &\equiv a^2-i^2 \pmod p\\ &\equiv n \pmod p\\ \end{aligned} $$ 至此定理得证。 那么我们知道 $(a+i)^{\frac {p+1}2}$ 即是二次剩余 $n$ 的一个解，其相反数为另一个解。 然而我们仍然无法确定数 $(a+i)^{\frac {p+1}2}$ 是否存在虚部。 不妨假设存在数 $a+bi$ 使得 $(a+bi)^2\equiv n \pmod p$ ，其中 $b\neq 0$ 。那么有： $$ \begin{aligned} a^2+b^2i^2+2abi &\equiv n \pmod p\\ a^2+b^2(a^2-n)+n& \equiv -2abi \pmod p\\ \end{aligned} $$ 注意到左式不存在虚部，那么有 $ab\equiv 0 \pmod p$ ，即 $a\equiv 0\pmod p$ 。则 $b^2i^2\equiv n\pmod p$ ，$i^2\equiv n\times b^{-2}\pmod p$ 。 而 $n$ 和 $b^{-2}$ 均为二次剩余，也就是说 $n\times b^{-2}$ 和 $i^2$ 都是二次剩余，这与 $i$ 的定义冲突。则数 $a+bi$ 必然不存在虚部。 ### Miller-Rabin 素性测试算法 基于二次探测定理和费马小定理的素性测试算法。 目标是测试数 $p$ 是否为素数。 我们先把 $p-1$ 分解为 $2^k\times t$ 的形式，然后随机一个底数 $a$ 计算 $a^t$ 。然后我们不断对其乘方，并使用二次探测定理判断，若其到达 $a^{p-1}$ 的上界，使用费马小定理判断。 若 $p$ 通过一轮测试，则 $p$ 为合数的概率为 $\dfrac 14$ ，那么经过 $k$ 轮测试，概率为 $\dfrac 1{4^k}$ 。 若广义黎曼猜想成立，那么可以通过选取少量底数使得 Miller-Rabin 素性测试算法成为确定性算法。 对于 $p<2^{32}$ ，选取 $2,7,61$ 共 $3$ 个底数可以确定 $p$ 是否为素数。 而对于 $p < 2^{64}$ ，选取 $2,325,9375,28178,450775,9780504,1795265022$ 共 $7$ 个底数就可以做到这一点。 ### Pollard-Rho 大数分解算法 基于 Miller-Rabin 素性测试算法的随机算法。 我们的目标是对数 $n$ 质因数分解。 考虑若存在 $k$ ，使得 $\gcd(n,k)\neq 1$ ，那么我们就找到了一个 $n$ 的因子。 考虑随机的寻找这个 $k$ 。为了使得找到 $k$ 的概率更大，我们引入生日悖论。具体的，我们随机出一个数列 $\{a_m\}$ 使用其中两数作差结果作为 $k$ 来计算最大公约数。 需要注意的是我们所使用的伪随机数生成方式非常特殊。若当前我们获取了数列 $\{a_m\}$ 的前 $i-1$ 项，那么我们通过把 $a_{i-1}$ 带入式 $f(x)=x^2+t \pmod n$ 来获取 $a_i$ 项，其中 $t$ 是一个随机数。显然其在模意义下是具有循环节的，我们需要在遍历循环节后退出这个过程，这样需要一个判圈算法，可以使用 Floyd 判圈算法，不过这里使用倍增算法实现。 若一轮分解失败，我们更换 $t$ 进行下一轮分解。 另外我们求取最大公约数的过程是可以优化的。注意到在 Pollard-Rho 算法的运行过程中求取最大公约数的次数非常的多，且我们并不需要精确的获取每一项最大公约数，那么可以考虑乘法累积最大公约数再一次计算，在倍增算法的过程中非常自然。 根据定理1.1，我们可以在 $\bmod n$ 的意义下计算，其不会影响最大公约数。 那么每当完成一次分解，我们重复这个过程，并不断使用 Miller-Rabin 素性测试算法来判断我们是否获取了一个素因子即可。 可以发现算法的关键其实是这个伪随机数生成方式，可惜我仍没有理解为什么这个数列如此有效。