数论学习笔记

BSGS

普通BSGS

求解 $a^x \equiv b \pmod p$ ，其中 $a \perp p$ 。

方程的解满足 $0 \le x < p$ 。

令 $x = A \lceil \sqrt{p} \rceil - B$ ，其中 $0 \le A,B \le \lceil \sqrt{p} \rceil$ ，所以

$$a^{A \lceil \sqrt{p} \rceil} \equiv ba^B \pmod{ p }$$

可以先算出等式右边 $ba^B$ 的所有取值，将其存到一个 hash 表里。
然后计算 $a^{A \lceil \sqrt{p} \rceil}$ 并查表寻找是否有相等值，即可得到$x$。

因为 $A,B \le \sqrt{p}$ ，所以时间复杂度就是 $O(\sqrt{p})$ 。

扩展BSGS

现在 $a$ 与 $p$ 不一定互质。

不互质就硬搞成互质的，设 $d_1 = \gcd(a,p)$ 。

如果 $d_1 \nmid b$ ，则方程无解，否则把方程同时除以 $d_1$ ，得到

$$\frac{a}{d_1} \cdot a^{x-1} \equiv \frac{b}{d_1} \pmod{ \frac{p}{d_1} }$$

若 $p$ 和 $d_1$ 不互质就再除，直到 $a \perp \frac{p}{d_1 d_2 \cdots d_k}$ 。

记 $D = \prod _{ i=1 } ^{k} d_i$ ，所以我们得到了

$$\frac{a^k}{D} \cdot a^{x-k} \equiv \frac{b}{D} \pmod{ \frac{p}{D} }$$

因为 $a \perp \frac{p}{D}$ ，所以 $a^k \perp \frac{p}{D}$ ，现在就是一个普通的BSGS问题了，求解 $x-k$ 再加上 $k$ 即原方程的解。

不排除解小于等于 $k$ 的情况，这时候只要 $O(k)$ 枚举验证一下即可。

杜教筛

用来快速求积性函数前缀和。

设给定的积性函数为 $f(n)$ ，所以我们设 $S(n)$ 为 $f$ 函数的前缀和

$$S(n) = \sum _{i=1} ^{n} f(i)$$

现在的目标就是求出 $S(n)$ 的值

考虑构造一个合适的积性函数 $g(n)$ ，然后求他们卷积 $h(n)$ 的前缀和

$$\sum _{i=1} ^{n} h(i) = \sum _{i=1} ^{n} (f \ast g)(i)$$

由卷积定义得

$$\sum _{i=1} ^{n} h(i) = \sum _{i=1} ^{n} \sum _{d|i} f(\frac{i}{d}) g(d)$$

把 $d$ 和 $g(d)$ 提到前面

$$\sum _{i=1} ^{n} h(i) = \sum _{d=1} ^{n} g(d) \sum _{i=1} ^{\lfloor \frac{n}{d} \rfloor} f(i)$$

后面那个求和就是 $f$ 的前缀和

$$\sum _{i=1} ^{n} h(i) = \sum _{d=1} ^{n} g(d) S(\lfloor \frac{n}{d} \rfloor)$$

因为我们求解的是 $S(n)$ ，所以将 $d=1$ 与 $d>1$ 分开计算

$$\sum _{i=1} ^{n} h(i) = g(1)S(n) + \sum _{d=2} ^{n} g(d) S(\lfloor \frac{n}{d} \rfloor)$$

其中 $g$ 是积性函数，所以 $g(1) = 1$ ，移项得

$$S(n) = \sum _{i=1} ^{n} h(i) - \sum _{d=2} ^{n} g(d) S(\lfloor \frac{n}{d} \rfloor)$$

如果我们可以快速求出 $h(i)$ 和 $g(n)$ 的前缀和，那么问题就可以用整除分块+递归求解了。

常见的积性函数

积性函数: $\operatorname{\varphi}$,$\mu$,$\sigma$,$\operatorname{d}$

完全积性函数: $\operatorname{\varepsilon}$,$\operatorname{I}$,$\operatorname{id}$

其中

$$\begin{aligned} & \operatorname{\varepsilon(n)} = [n=1] \\ & \operatorname{I}(n) = 1 \\ & \operatorname{id_k}(n) = n^k \\ & \sigma _k (n) = \sum _{d|n} d^k \end{aligned}$$

一些常用的卷积性质

$$\begin{aligned} & \mu \ast \operatorname{I} = \operatorname{\varepsilon} \\ & \operatorname{\varphi} \ast \operatorname{I} = \operatorname{id_1} \\ & \mu \ast \operatorname{id_1} = \operatorname{\varphi} \end{aligned}$$

Min_25筛

求积性函数 $f(x)$ 前缀和，其中 $f(p^k), p \in Prime$ 可快速求出。

下面式子中设 $p$ 为一个质数， $p_x$ 为第 $x$ 个质数

一、设完全积性函数 $g(x)$ ，且 $g(p) = f(p), p \in Prime$

二、设 $G(n,x)$ 为 $[1,n]$ 中质数或最小质因子大于等于 $p_x$ 的和数的 $g$ 值的和，所以有递推式:

$$G(n,x+1) = G(n,x) - g(p_x) \left( G(\lfloor \frac{n}{p_x}, x \rfloor) - \sum _{p \in Prime} ^{p \le p_{x-1}} g(p) \right)$$

三、设 $S(n,x)$ 为 $[1,n]$ 中最小质因子大于等于 $p_x$ 的合数的 $f$ 值的和， $tot$ 为 $[1,n]$ 中质数的个数，递推式:

$$S(n,x) = S(n,x+1) + \sum _{i=1} ^{p_x^{i+1} \le n} \left( f(p_x^{i+1}) + f(p_x^i) \cdot \left( G(\lfloor \frac{n}{p_x^i} \rfloor, tot+1) - \sum _{p \in Prime} ^{p \le p_{x}} f(p) + S(\lfloor \frac{n}{p_x^i} \rfloor, x+1) \right) \right)$$

类欧几里得算法

用来求一些奇奇怪怪的式子

$$\begin{aligned} & f(a,b,c,n) = \sum _{i=0} ^n \left\lfloor \frac{ai+b}{c} \right\rfloor \\ & g(a,b,c,n) = \sum _{i=0} ^n \left\lfloor \frac{ai+b}{c} \right\rfloor i \\ & h(a,b,c,n) = \sum _{i=0} ^n \left\lfloor \frac{ai+b}{c} \right\rfloor ^2 \end{aligned}$$

无特殊说明，以下数学公式中以 $\%$ 代替 $\bmod$ 。

函数 f(a,b,c,n)

分两种情况:

当 $a \ge c \space or \space b \ge c$ 时:

$$\begin{aligned} f(a,b,c,n) & = \sum _{i=0} ^{n} \small\left\lfloor \frac { (\lfloor a/c \rfloor c - a\%c)i + (\lfloor b/c \rfloor c - b\%c) } {c} \right\rfloor \\ & = \sum _{i=0} ^{n} \left( \lfloor a/c \rfloor i + \lfloor b/c \rfloor \right) + \sum _{i=0} ^{n} \left\lfloor \frac{ (a\%c)i + (b\%c) }{c} \right\rfloor \\ & = \frac{(n+1)(n+2)}{2} \lfloor a/c \rfloor + (n+1) \lfloor b/c \rfloor + f(a\%c, b\%c, c, n) \end{aligned}$$

这样我们就能把 $a$ 和 $b$ 缩小范围了。

当 $a < c \space and \space b < c$ 时:

$$\begin{aligned} f(a,b,c,n) & = \sum _{i=0} ^{n} \sum _{j=0} ^{ \lfloor \frac{ai+b}{c} \rfloor } 1 \\ & = \sum _{i=0} ^{n} \sum _{j=0} ^{ \lfloor \frac{an+b}{c} \rfloor } \left[ j < \left\lfloor \frac{ai+b}{c} \right\rfloor \right] \\ \end{aligned}$$

记 $m = \lfloor \frac{an+b}{c} \rfloor$ ， 所以有

$$\begin{aligned} f(a,b,c,d) & = \sum _{i=0} ^{n} \sum _{j=0} ^{m-1} \left[ j+1 \le \frac{ai+b}{c} \right] \\ & = \sum _{i=0} ^{n} \sum _{j=0} ^{m-1} \left[ \frac{cj+c-b}{a} \le i \right] \\ & = \sum _{i=0} ^{n} \sum _{j=0} ^{m-1} \left[ \frac{cj+c-b-1}{a} < i \right] \\ & = \sum _{j=0} ^{m-1} \sum _{i=0} ^{n} \left[ i > \frac{cj+c-b-1}{a} \right] \\ & = \sum _{j=0} ^{m-1} \left( n - \left\lfloor \frac{cj+c-b-1}{a} \right\rfloor \right) \\ & = mn - \sum _{i=0} ^{m-1} \left\lfloor \frac{cj+c-b-1}{a} \right\rfloor \\ & = mn - f(c,c-b-1,a,m-1) \end{aligned}$$

所以我们得到了 $f$ 的递归解法，递归过程就像是欧几里得算法求 $\gcd$ 一样，所以是类欧几里得算法

$$\begin{aligned} f(a,b,c,n) = \begin{cases} \frac{n(n+1)}{2} \lfloor a/c \rfloor + (n+1) \lfloor b/c \rfloor + f(a\%c, b\%c, c, n) & , a \ge c \space or \space b \ge c \\ mn - f(c,c-b-1,a,m-1) & , a < c \space and \space b < c \end{cases} \end{aligned}$$

函数 g(a,b,c,n)

还是相同的分情况方法:

当 $a > c \space or \space b > c$ 时:

$$\begin{aligned} g(a,b,c,n) & = \sum _{i=0} ^n \left\lfloor \frac{ (\lfloor a/c \rfloor c + a\%c)i + (\lfloor b/c \rfloor c + b\%c) }{c} \right\rfloor i \\ & = \sum _{i=0} ^n \lfloor a/c \rfloor i^2 + \sum _{i=0} ^n \lfloor b/c \rfloor i + \sum _{i=0} ^n \left\lfloor \frac{(a\%c)i + b\%c}{c} \right\rfloor i \\ & = \frac{n(n+1)(2n+1)}{6} \lfloor a/c \rfloor + \frac{n(n+1)}{2} \lfloor b/c \rfloor + g(a\%c, b\%c, c, n) \end{aligned}$$

当 $a<c \space and \space b<c$ 时:

$$\begin{aligned} g(a,b,c,d) & = \sum _{i=0} ^n i \sum _{j=0} ^m \left[ j < \lfloor \frac{ai+b}{c} \rfloor \right] \\ & = \sum _{i=0} ^n i \sum _{j=0} ^{m-1} \left[ j+1 \le \frac{ai+b}{c} \right] \\ & = \sum _{i=0} ^n i \sum _{j=0} ^{m-1} \left[ \frac{cj+c-b}{a} \le i \right] \\ & = \sum _{i=0} ^n i \sum _{j=0} ^{m-1} \left[ \left\lfloor \frac{cj+c-b-1}{a} \right\rfloor < i \right] \end{aligned}$$

设 $A = \lfloor \frac{cj+c-b-1}{a} \rfloor$ ，则

$$\begin{aligned} g(a,b,c,d) & = \sum _{i=0} ^n i \sum _{j=0} ^{m-1} [ i > A ] \\ & = \sum _{j=0} ^{m-1} \sum _{i=0} ^n i [i > A] \\ & = \sum _{j=0} ^{m-1} \sum _{i=A+1} ^{n} \\ & = \frac{1}{2} \sum _{j=0} ^{m-1} (n+A+1)(n-A) \\ & = \frac{1}{2} \sum _{j=0} ^{m-1} (n^2 + n - A^2 - A) \\ & = \frac{1}{2} \left( n^2 m + nm - \sum _{j=0} ^{m-1} \left\lfloor \frac{cj+c-b-1}{a} \right\rfloor ^2 - \sum _{j=0} ^{m-1} \left\lfloor \frac{cj+c-b-1}{a} \right\rfloor \right) \\ & = \frac{1}{2} \left( n(n+1)m - h(c,c-b-1,a,m-1) - f(c,c-b-1,a,m-1) \right) \end{aligned}$$

所以

$$\begin{aligned} g(a,b,c,n) = \begin{cases} \frac{n(n+1)(2n+1)}{6} \lfloor a/c \rfloor + \frac{n(n+1)}{2} \lfloor b/c \rfloor + g(a\%c, b\%c, c, n) & , a > c \space or \space b > c \\ \frac{1}{2} \left( n(n+1)m - h(c,c-b-1,a,m-1) - f(c,c-b-1,a,m-1) \right) & , a < c \space and \space b < c \end{cases} \end{aligned}$$

函数 h(a,b,c,n)

仍然分两种情况:

当 $a > c \space or \space b > c$ 时:

$$\begin{aligned} h(a,b,c,n) & = \sum _{i=0} ^n \left\lfloor \frac{ai+b}{c} \right\rfloor ^2 \\ & = \sum _{i=0} ^n \left\lfloor \frac{\lfloor a/c \rfloor ci + \lfloor b/c \rfloor c }{c} + \frac{(a\%c)i + (b\%c)}{c} \right\rfloor ^2 \\ & = \sum _{i=0} ^n \left( \lfloor a/c \rfloor i + \lfloor b/c \rfloor + \left\lfloor \frac{(a\%c)i + (b\%c)}{c} \right\rfloor \right) ^2 \end{aligned}$$

设 $A = \lfloor a/c \rfloor i + \lfloor b/c \rfloor$,$B = \left\lfloor \frac{(a\%c)i + (b\%c)}{c} \right\rfloor$ ， 所以

$$\begin{aligned} h(a,b,c,n) & = \sum _{i=0} ^n \left( A+B \right) ^2 \\ & = \sum _{i=0} ^n \left( A^2 + 2AB + B^2 \right) \\ & = \sum _{i=0} ^n A^2 + 2 \sum _{i=0} ^n AB + \sum _{i=0} ^n B^2 \\ \sum _{i=0} ^n A^2 & = \sum _{i=0} ^{n} \left( \lfloor a/c \rfloor i + \lfloor b/c \rfloor \right) ^2 \\ & = \sum _{i=0} ^n \lfloor a/c \rfloor ^2 i^2 + 2 \sum _{i=0} ^n \lfloor a/c \rfloor \lfloor b/c \rfloor i + \sum _{i=0} ^n \lfloor b/c \rfloor ^2 \\ & = \frac{n(n+1)(2n+1)}{6} \lfloor a/c \rfloor ^2 + n(n+1) \lfloor a/c \rfloor \lfloor b/c \rfloor + (n+1) \lfloor b/c \rfloor ^2 \\ 2 \sum _{i=0} ^n AB & = 2 \sum _{i=0} ^n \left( \lfloor a/c \rfloor i + \lfloor b/c \rfloor \right) \left\lfloor \frac{(a\%c)i + (b\%c)}{c} \right\rfloor \\ & = 2 \sum _{i=0} ^n \lfloor a/c \rfloor i \left\lfloor \frac{(a\%c)i+(b\%c)}{c} \right\rfloor + 2 \sum _{i=0} ^n \lfloor b/c \rfloor \left\lfloor \frac{(a\%c)i+(b\%c)}{c} \right\rfloor \\ & = 2 \lfloor a/c \rfloor g(a\%c, b\%c, c, n) + 2 \lfloor b/c \rfloor f(a\%c, b\%c, c, n) \\ \sum _{i=0} ^n B^2 & = h(a\%c, b\%c, c, n) \\ h(a,b,c,n) & = \frac{n(n+1)(2n+1)}{6} \lfloor a/c \rfloor ^2 + n(n+1) \lfloor a/c \rfloor \lfloor b/c \rfloor + (n+1) \lfloor b/c \rfloor ^2 + 2 \lfloor a/c \rfloor g(a\%c, b\%c, c, n) + 2 \lfloor b/c \rfloor f(a\%c, b\%c, c, n) + h(a\%c, b\%c, c, n) \end{aligned}$$

当 $a < c \space and \space b < c$ 时:

$$\begin{aligned} h(a,b,c,n) & = \sum _{i=0} ^n \left\lfloor \frac{ai+b}{c} \right\rfloor ^2 \\ & = \sum _{i=0} ^n \left( 2 \sum _{j=1} ^{ \lfloor \frac{ai+b}{c} \rfloor } j + \left\lfloor \frac{ai+b}{c} \right\rfloor \right) \\ & = 2 \sum _{i=0} ^n \sum _{j=1} ^{ \lfloor \frac{ai+b}{c} \rfloor } j + \sum _{i=0} ^n \left\lfloor \frac{ai+b}{c} \right\rfloor \\ & = 2 \sum _{i=0} ^n \sum _{j=0} ^{m-1} (j+1) \left[ j < \left\lfloor \frac{ai+b}{c} \right\rfloor \right] - f(a,b,c,n) \\ & = 2 \sum _{i=0} ^n \sum _{j=0} ^{m-1} (j+1) \left[ \left\lfloor \frac{cj+c-b-1}{a} \right\rfloor < i \right] - f(a,b,c,n) \\ & = 2 \sum _{j=0} ^{m-1} (j+1) \sum _{i=0} ^n \left[ i > \left\lfloor \frac{cj+c-b-1}{a} \right\rfloor \right] - f(a,b,c,n) \\ & = 2 \sum _{j=0} ^{m-1} (j+1) \left( n - \left\lfloor \frac{cj+c-b-1}{a} \right\rfloor \right) - f(a,b,c,n) \\ & = 2n \sum _{j=0} ^{m-1} (j+1) - 2 \sum _{j=0} ^{m-1} j \left\lfloor \frac{cj+c-b-1}{a} \right\rfloor - 2 \sum _{j=0} ^{m-1} \left\lfloor \frac{cj+c-b-1}{a} \right\rfloor - f(a,b,c,n) \\ & = nm(m+1) - 2g(c, c-b-1, a, n) - 2f(c, c-b-1, a, n) - f(a, b, c, n) \end{aligned}$$

所以

$$\begin{aligned} h(a,b,c,n) = \begin{cases} \frac{n(n+1)(2n+1)}{6} \lfloor a/c \rfloor ^2 + n(n+1) \lfloor a/c \rfloor \lfloor b/c \rfloor + (n+1) \lfloor b/c \rfloor ^2 + 2 \lfloor a/c \rfloor g(a\%c, b\%c, c, n) + 2 \lfloor b/c \rfloor f(a\%c, b\%c, c, n) + h(a\%c, b\%c, c, n) & , a > c \space or \space b > c \\ nm(m+1) - 2g(c, c-b-1, a, n) - 2f(c, c-b-1, a, n) - f(a, b, c, n) & , a < c \space and \space b < c \end{cases} \end{aligned}$$

生成函数

普通生成函数(OGF)

对于一个序列 $a$ ，它的普通生成函数定义为形式幂级数: $F(x) = \sum _{i} a_i x^i$

也就是将 $a$ 中每一项作为多项式的系数。

基本运算

设两个序列 $a,b$ 的生成函数分别为 $F(x), G(x)$ ，则有

$$F(x) \pm G(x) = \sum _{i} (a_i \pm b_i)x^i$$

也就是序列 $\langle a_i \pm b_i \rangle$ 的生成函数为 $F(x) \pm G(x)$ 。

考虑乘法运算，也就是多项式卷积

$$F(x)G(x) = \sum _i \left( \sum _{j=0} ^{i} a_j b_{i-j} \right) x^i$$

所以 $\langle \sum\limits \_{i=0} ^n a\_i b \_{n-i} \rangle$ 的生成函数就是 $F(x)G(x)$

封闭形式

形式幂级数的形式无法快速进行乘法运算，所以需要转化为封闭形式简化运算。

例如 $\langle 1,1, \cdots \rangle$ 的普通生成函数为 $F(x) = \sum _i x^i$ 。

可以发现 $F(x) = xF(x) + 1$ ，解方程得到 $F(x) = \large\frac{1}{1-x}$ 。

这就是函数 $F(x) = \sum _i x^i$ 的封闭形式。

等比数列 $\langle 1, p, p^2, p^3, \cdots \rangle$ 的生成函数 $F(x) = \sum _i p^i x^i$ ， 有

$$\begin{aligned} & F(x) = pxF(x)+1 \\ & F(x) = \frac{1}{1-px} \end{aligned}$$

等比数列的封闭形式与展开形式之间的转化是常用的化简方法。

牛顿二项式定理

重新定义组合数:

$$C_n^m = \frac{n^{\underline{m}}}{m!} \quad (n \in \mathbf{C}, k \in \mathbf{n})$$

在这种情况下，对于 $a \in \mathbf{C}$ ，二项式定理为

$$(x+1)^a = \sum _{i \ge 0} C_a^i \space x^i$$

这样我们就可以通过牛顿二项式定理由封闭形式求某一项的系数了。

指数型生成函数（EGF)

序列 $a$ 的指数生成函数定义为形式幂级数:

$$\hat F(x) = \sum _i a_i \frac{x^i}{i!}$$

基本运算

加减法还是一样，就是系数相加。

乘法不太一样，对于两个序列 $a,b$ ，设它们的指数生成函数分别为 $\hat F(x) \hat G(x)$ ，则

$$\begin{aligned} F(x)G(x) & = \sum _{i \ge 0} a_i \frac{x^i}{i!} \sum _{j \ge 0} b_j \frac{x^j}{j!} \\ & = \sum _{n \ge 0} i^n \sum _{j=0} ^n a_i b_{n-i} \frac{1}{i!(n-i)!} \\ & = \sum _{n \ge 0} \frac{x^n}{n!} \sum _{i=0} ^n C_n^i a_i b_{n-i} \end{aligned}$$

所以序列 $\langle \sum \_{i=0} ^{n} C\_n^i a\_i b\_{n-i} \rangle$的指数生成函数为$\hat F(x) \hat G(x)$ 。

封闭形式

同样考虑封闭形式简化运算。

序列 $\langle 1, 1, \cdots \rangle$ 的指数生成函数是 $\sum _{n \ge 0} \frac{x^n}{n!} = e^x$ 。

类似地，等比数列 $\langle 1, p, p^2, \cdots \rangle$ 的指数生成函数是 $\sum \_{n \ge 0} \frac{p^n x^n}{n!} = e^{px}$