数论 学习笔记

约数个数

@Ubospica 对于约数个数上界的估计

$d(n)\le n^{\frac c{\ln\ln n}}$，其中 $c\approx1.066$。当 $n>5000$ 约有 $d(n)<\sqrt n$。

---

质数判定

关于质数判定的一些资料：

• @wangrx 一定范围内的确定性判素
• 知乎 如何编程判断一个数是否是质数？

费马素性检验 / 费马测试

费马小定理的逆否命题：若存在 $1\le a<p$，使得 $a^{p-1}\not\equiv1\pmod p$，则 $p$ 一定不是素数。

多次选取质数 $a\in[1,p)$，使用快速幂检查 $p^{a-1}\bmod p$ 是否为 $1$：若存在快速幂的结果不是 $1$，则 $p$ 一定不是素数；否则 $p$ 大概率是素数。

遗憾的是，费马素性检验存在一个问题：有的合数 $p$ 也满足 $a^{p-1}\equiv1\pmod p$（$1\le a<p$），这样的数被称为卡迈克尔数（Carmichael Number）/ 费马伪素数。例如，$561=3\times11\times17$ 就是一个卡迈克尔数。在 $10^9$ 以内，这样的数有 $646$ 个，显然 $2^{64}$ 以内不能通过打表来满足素性检测的要求。

Miller Rabin 素性检验

二次探测定理：若 $p$ 为奇素数，则 $x^2\equiv1\pmod p$ 的解为 $x\equiv\pm1\pmod p$。

步骤：

• 选择一个质数 $a$，初始化指数 $d=p-1$。
• 快速幂判定 $a^d\bmod p$ 是否为 $1$；若是，重复 $d\leftarrow\frac d2$ 直到 $d$ 为奇数或 $a^d\not\equiv1\pmod p$。

错误率 $4^{-k}$，其中 $k$ 是选取的底数个数。时间复杂度 $O(k^2\log p)$。

关于确定性检验的底数选取：

• 对于 $2^{32}$ 以内的判素，选取 $2,7,61$ 三个底数即可。
• 对于 $2^{64}$ 以内的判素，选取 $2,325,9375,28178,450775,9780504,1795265022$ 七个底数即可。
• 如果是考场上，选取 $2,3,5,7,11,13,17,19,23,29,31,37$（也就是前十二个质数）作为底数即可，它适用于 $2^{78}$ 以内的判素。

---

分解质因数

生日悖论

对于一个值域为 $[1..n]$ 的随机整数生成器，生成 $\sqrt{\frac n{\ln2}}$ 个数期望得到两个数相同。

Pollard Rho [UNFINISHED]

早忘完了。

---

欧几里得算法相关 GCD

裴蜀定理 / 贝祖定理

对于任意的 $a,b,x,y$，有 $\gcd(a,b)\mid ax+by$。即：$ax+by=c$ 有解，当且仅当 $\gcd(a,b)\mid c$。

推广：对于任意整数数列 $\{a_i\},\{k_i\}$，有 $\gcd\{a_i\}\mid\sum a_ik_i$。

扩展欧几里得算法 Ex GCD

用于求解二元一次不定方程 $ax+by=c$，等价于 $ax\equiv c\pmod b$。由裴蜀定理得当且仅当 $\gcd(a,b)\mid c$ 时有解。

$\gcd(a,b)=\gcd(b,a\bmod b)$。$bx_0+(a\bmod b)y_0=k\times\gcd(b,a\bmod b)=k\times\gcd(a,b)=ax+by$，尝试把左边构造成右边的形式。$bx_0+ay_0-\left\lfloor\frac ab\right\rfloor\times by_0=ay_0+b(x_0-\left\lfloor\frac ab\right\rfloor\times y_0)$，所以$\begin{cases}x=y_0\\y=x_0-\left\lfloor\frac ab\right\rfloor\times y_0\end{cases}$。

类欧几里得算法

用于计算：

$$\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}^ni\left\lfloor\frac{ai+b}c\right\rfloor\\ h(a,b,c,n)&=\sum_{i=0}^n\left\lfloor\frac{ai+b}c\right\rfloor^2 \end{aligned}$$

该算法多用于解决直线下整点等相关问题。

计算 1 式：$f(a,b,c,n)=\sum_{i=0}^n\left\lfloor\frac{ai+b}c\right\rfloor$

若 $a=0$，则 $f(a,b,c,n)=(n+1)\left\lfloor\frac bc\right\rfloor$。

若 $a\ge c\lor b\ge c$，则：

$$\begin{aligned} f(a,b,c,n)&=\sum_{i=0}^n\left\lfloor\frac{i(a\bmod c)+(b\bmod c)}c\right\rfloor+i\left\lfloor\frac ac\right\rfloor+\left\lfloor\frac bc\right\rfloor\\ &=f(a\bmod c,b\bmod c,c,n)+\frac{n(n+1)}2\left\lfloor\frac ac\right\rfloor+(n+1)\left\lfloor\frac bc\right\rfloor \end{aligned}$$

否则 $a<c\land b<c$，则：

$$\begin{aligned} f(a,b,c,n)&=\sum_{i=0}^n\sum_{j=0}^{\left\lfloor\frac{ai+b}c\right\rfloor-1}1\\ &=\sum_{j=0}^{M-1}\sum_{i=0}^n\left[j<\left\lfloor\frac{ax+b}c\right\rfloor\right]\\ &=\sum_{j=0}^{M-1}\sum_{i=0}^n\left[i>t\right]\\ &=nM-\sum_{j=0}^{M-1}t\\ &=nM-f(c,c-b-1,a,M-1) \end{aligned}$$

上式中 $M=\left\lfloor\frac{an+b}c\right\rfloor$，$t=\left\lfloor\frac{cj+c-b-1}a\right\rfloor$。

计算 2 式：$g(a,b,c,n)=\sum_{i=0}^ni\left\lfloor\frac{ai+b}c\right\rfloor$

若 $a=0$，则 $g(a,b,c,n)=\frac{n(n+1)}2\left\lfloor\frac bc\right\rfloor$。

若 $a\ge c\lor b\ge c$，则：

$$\begin{aligned} g(a,b,c,n)&=\sum_{i=0}^ni\left\lfloor\frac{i(a\bmod c)+(b\bmod c)}c\right\rfloor+i^2\left\lfloor\frac ac\right\rfloor+i\left\lfloor\frac bc\right\rfloor\\ &=g(a\bmod c,b\bmod c,c,n)+\frac{n(n+1)(2n+1)}6\left\lfloor\frac ac\right\rfloor+\frac{n(n+1)}2\left\lfloor\frac bc\right\rfloor \end{aligned}$$

否则 $a<c\land b<c$，则：

$$\begin{aligned} g(a,b,c,n)&=\sum_{i=0}^n\sum_{j=0}^{\left\lfloor\frac{ai+b}c\right\rfloor-1}i\\ &=\sum_{j=0}^{M-1}\sum_{i=0}^n\left[j<\left\lfloor\frac{ax+b}c\right\rfloor\right]i\\ &=\sum_{j=0}^{M-1}\sum_{i=0}^n\left[i>t\right]i\\ &=\frac{n(n+1)}2M-\sum_{j=0}^{M-1}\frac{t(t+1)}2\\ &=\frac12(n(n+1)M-h(c,c-b-1,a,M-1)-f(c,c-b-1,a,M-1)) \end{aligned}$$

上式中 $M=\left\lfloor\frac{an+b}c\right\rfloor$，$t=\left\lfloor\frac{cj+c-b-1}a\right\rfloor$。

计算 3 式：$h(a,b,c,n)=\sum_{i=0}^n\left\lfloor\frac{ai+b}c\right\rfloor^2$

若 $a=0$，则 $h(a,b,c,n)=(n+1)\left\lfloor\frac bc\right\rfloor^2$。

若 $a\ge c\lor b\ge c$，则：

$$\begin{aligned} h(a,b,c,n)=&~h(a\bmod c,b\bmod c,c,n)+2\cdot f(a\bmod c,b\bmod c,c,n)\left\lfloor\frac bc\right\rfloor\\ &+2\cdot g(a\bmod c,b\bmod c,c,n)\left\lfloor\frac ac\right\rfloor+\frac{n(n+1)(2n+1)}6\left\lfloor\frac ac\right\rfloor^2\\ &+(n+1)\left\lfloor\frac bc\right\rfloor^2+n(n+1)\left\lfloor\frac ac\right\rfloor\left\lfloor\frac bc\right\rfloor \end{aligned}$$

否则 $a<c\land b<c$。因为 $p^2=2\cdot\frac{p(p+1)}2-p=\left(2\sum_{i=1}^pi\right)-p$，所以：

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

上式中 $M=\left\lfloor\frac{an+b}c\right\rfloor$，$t=\left\lfloor\frac{cj+c-b-1}a\right\rfloor$。

---

同余相关

欧拉函数 Euler

• 唯一分解 $n=\prod\limits_{i=1}^kp_i^{a_i}$，有 $\varphi(n)=n\prod\limits_{i=1}^k\left(1-\frac{1}{p_i}\right)$。
• 质数 $p$ 满足 $\varphi(p)=p-1$，$\varphi(p^n)=p^{n-1}(p-1)$。
• 当 $a,b$ 互质时有 $\varphi(ab)=\varphi(a)\varphi(b)$。
• 若 $a\mid p$，则有 $\varphi(ap)=a\cdot\varphi(p)$。

费马小定理 Fermat

若 $p$ 是质数且 $a,p$ 互质，则 $a^{p-1}\equiv1\pmod p$。等价于 $a^p\equiv a\pmod p$。

应用：求模质数意义下的乘法逆元；简化模意义下乘方运算的指数，即 $a^b\equiv a^{b\bmod(p-1)}\pmod p$。

欧拉定理 Euler

若 $a,p$ 互质，则有 $a^{\varphi(p)}\equiv1\pmod p$。当 $p$ 为质数时 $\varphi(p)=p-1$，同费马小定理。故欧拉定理是费马小定理的扩展。

扩展欧拉定理 Ex Euler

若 $b\ge\varphi(p)$ ，则 $a^b\equiv a^{b\bmod\varphi(p)+\varphi(p)}\pmod p$，其中 $a,p$ 可以不互质。

卢卡斯定理 Lucas

$C_n^m\equiv C_{\left\lfloor n/p\right\rfloor}^{\left\lfloor m/p\right\rfloor}\times C_{n\bmod p}^{m\bmod p}\pmod p$，要求 $p$ 是质数。

扩展卢卡斯定理 Ex Lucas [UNFINISHED]

$\frac{n!}{(n-m)!m!}\bmod a^b\leftarrow n!\bmod a^b$。

$$\begin{aligned} 9!\bmod 2^2&=(2\times4\times6\times8)\times(1\times3)\times(5\times7)\times9\bmod2^2\\ &=2^4\times4!\times(1\times3)^2\times9\bmod2^2\\ n!\bmod p^c&=p^{\lfloor n/p\rfloor}\times\lfloor n/p\rfloor!\times\left(\prod_{i=1\land in}\right)^{\lfloor n/p^c\rfloor} \end{aligned}$$

线性求乘法逆元

依据：

• $\prod\limits_{i=1}^na_i^{-1}\equiv\left(\prod\limits_{i=1}^na_i\right)^{-1}\pmod p$ ，即积的逆元同余逆元的积。
• $\prod\limits_{i=1}^na_i^{-1}\times a_n\equiv\prod\limits_{i=1}^{n-1}a_i^{-1}\pmod p$。

中国剩余定理 CRT

若数列 $\{m_i\}$ 互质，则线性同余方程组

$$\begin{cases} x\equiv a_1\mod m_1\\ x\equiv a_2\mod m_2\\ \dots\\ x\equiv a_n\mod m_n\\ \end{cases}$$

有整数解；且在模 $M=\prod\limits_{i=1}^nm_i$ 意义下有唯一整数解，为 $\sum\limits_{i=1}^na_i\cdot\text{inv}_i\cdot\frac M{m_i}$。其中 $\text{inv}_i=\left(\frac M{m_i}\right)^{-1}\pmod{m_i}$（$m_i$ 不保证为质数就用 Ex GCD 求）。

阶

定义：由欧拉定理「若 $a\perp p$ 则 $a^{\varphi(p)}\equiv1\pmod p$」，记 $a$ 模 $p$ 意义下的阶 $\delta_p(a)$ 为最小的正整数 $n$，满足 $a^n\equiv1\pmod p$。

性质：

• $a,a^2,\cdots,a^{\delta_p(a)}$ 模 $p$ 两两不同余。
• 所有 $\delta_p(a)$ 的倍数 $n$，均满足 $a^n\equiv1\pmod p$。
  • 更进一步地，$a^n\equiv a^m\pmod p$ 与 $n\equiv m\pmod{\delta_p(a)}$ 等价。
• 若 $a\perp p$ 且 $b\perp p$，则 $\delta_p(ab)=\delta_p(a)\delta_p(b)$ 等价于 $\delta_p(a)\perp\delta_p(b)$。

原根

定义：若 $a\perp p$ 且 $\delta_p(a)=\varphi(p)$，则称 $a$ 为 $p$ 的原根。

判定定理：若 $a\perp p$ 且 $p\ge3$，则 $a$ 是 $p$ 的原根的充要条件是，对于所有素数 $k\mid\varphi(p)$，都有 $a^{\frac{\varphi(p)}k}\not\equiv1\pmod p$。

存在定理：$p$ 有原根，当且仅当 $p=2,4,k^x,2k^x$，其中 $k$ 为奇素数，$x$ 为正整数。

个数定理：若 $p$ 有原根，那么它的原根个数为 $\varphi(\varphi(p))$。

离散对数

定义：若 $p$ 有原根 $g$，且 $g^k\equiv a\pmod p$，那么 $k\equiv\text{Ind}_ga\pmod{\varphi(p)}$。

性质：

• $\text{Ind}_gab\equiv\text{Ind}_ga+\text{Ind}_gb\pmod{\varphi(p)}$。
• $\text{Ind}_ga^b\equiv b~\text{Ind}_ga\pmod{\varphi(p)}$。

大步小步算法 BSGS

求解 $a^x\equiv b\pmod p$，使得 $0\le x<p$。其中 $a\perp p$。

设 $x=A\lfloor\sqrt p\rfloor-B$，移项，有 $x^{A\sqrt p}\equiv ba^B\pmod p$。

像折半一样搜，$O(\sqrt p)$ 或 $O(\sqrt p\log p)$。

扩展大步小步算法 Ex BSGS [UNFINISHED]

早忘完了。

---

莫比乌斯反演 Mobius

数论函数

$f(n)$ 满足 $n\in\bold N,f(n)\in\bold Z$。

e.g. $I_k(n)=n^k$，$d(n)=\sum_{p\mid n}1$，$\sigma(n)=\sum_{p\mid n}p$。

积性函数

$\forall a\perp b$，$f(a)f(b)=f(ab)$。

完全积性函数：$\forall a,b$，$f(a)f(b)=f(ab)$。

数论分块 / 整除分块

$\lfloor\frac nd\rfloor$ 只有 $O(\sqrt n)$ 种取值。

莫比乌斯函数

若唯一分解 $n=\prod\limits_{i=1}^kp_i^{c_i}$，则 $\mu(n)=\begin{cases}1,&n=1\\0,&\exist i,c_i>1\\ (-1)^k,&\forall i,c_i=1\end{cases}$。

性质：

1. $\sum_{d\mid n}\mu(d)=[n=1]$。
   唯一分解 $n=\prod p_i^{c_i}$，那么等式左边相当于 $\sum_{p_i}(-1)^{\sum p_i}$。若 $n\ne1$，则 $=0$。
2. 莫比乌斯反演：若 $\forall n,f(n)=\sum_{d\mid n}g(d)$，则 $g(n)=\sum_{d\mid n}\mu(d)f\left(\frac nd\right)$。
3. 莫比乌斯函数 $\mu(n)$ 是积性函数。

狄利克雷卷积 Dirichlet

狄利克雷卷积是建立在群 $(G,*)$ 上的运算，其中 $G$ 是数论函数集合，定义如：

$$(f*g)(n)=\sum_{d\mid n}f(d)g\left(\frac nd\right)$$

狄利克雷卷积的单位元函数 $\epsilon(n)=[n=1]$。

运算律：

• 交换律：$f*g=g*f$
• 结合律：$f*(g*h)=(f*g)*h$
• 分配律：$f*(g+h)=f*g+f*h$

性质：

• 莫比乌斯函数 性质 1：$\mu*I_0=\epsilon$
• 莫比乌斯反演：若 $f=g*I_0$，则 $g=\mu*f$
• $\mu*I_1=\varphi$
• $\varphi*I_0=I_1$

---

筛法

杜教筛

求 $S(n)=\sum_{i=1}^nf(i)$，其中 $f$ 是积性函数。下面 $g$ 也是积性函数。

$$\sum_{i=1}^n(f*g)(i)=\sum_{d=1}^ng(d)S\left(\left\lfloor\frac nd\right\rfloor\right)$$

$*$ 是狄利克雷卷积，这是莫反基本操作。

$$\begin{aligned} g(1)S(n)&=\sum_{d=1}^ng(d)S\left(\left\lfloor\frac nd\right\rfloor\right)-\sum_{d=2}^ng(d)S\left(\left\lfloor\frac nd\right\rfloor\right)\\ &=\sum_{i=1}^n(f*g)(i)-\sum_{d=2}^ng(d)S\left(\left\lfloor\frac nd\right\rfloor\right)\\ \end{aligned}$$

只要我们能快速求出 $\sum_{i=1}^n(f*g)(i)$ 和 $g$ 的前缀和，就可以整除分块了。

不预处理是 $O(n^{\frac34})$，线性筛预处理前 $O(n^{\frac23})$ 项优化成 $O(n^{\frac23})$。

洲阁筛

求 $S(n)=\sum_{i=1}^nf(i)$，其中 $f$ 是积性函数。用于解决杜教筛求不了的函数。

我们把 $S(n)$ 分成两部分，第一部分是 $i$ 有 $>\sqrt n$ 的质因子的，第二部分是剩下的。

第一部分

DP。设 $g(x,y)$ 表示 $1\sim y$ 中与前 $x$ 个质数互质的 $i$ 的 $f(i)$ 之和，有：

$$g(x,y)=g(x-1,y)+f(p_x)\cdot g\left(x-1,\left\lfloor\frac y{p_x}\right\rfloor\right)$$

可惜复杂度是 $O\left(\frac{\sqrt n}{\ln\sqrt n}\cdot\sqrt n\right)=O\left(\frac n{\log n}\right)$ 的。

注意到当 $p_x>\sqrt y$ 时，$g(x,y)=g(x-1,y)-f(p_x)$。

所以一旦发现 $p_x^2>y$ 则停止转移，记此时的 $x$ 为 $t(y)$，那么 $\forall x>t(y)$，$g(x,y)=g(x-1,y)-\sum_{i=t(y)}^{x-1}f(p_i)$。答案就是 $\sum_{i=1}^{\sqrt n}f(i)\cdot g\left(m,\left\lfloor\frac ni\right\rfloor\right)$。

第二部分 [UNFINISHED]