7.29 数论 WIP

$a\equiv b\pmod p\Rightarrow \frac{a}{d}\equiv \frac{b}{d}\pmod{\frac{p}{d}},d=\gcd(a,b,p)$。

exGCD

若 $(a,b)=1$，则 $0\leq x<b$，$ax\bmod b$ 互不相同，有一个是 $1$。证明：$ax_1\equiv ax_2\pmod b$ 则 $(x_1-x_2)a|b$，因为 $(a,b)=1$，所以 $(x_1-x_2)|b$，但是 $x_1-x_2\neq 0\land -b<x_1-x_2<b$。
推论：若 $(a,b)=1$，则存在 $ax+by=1$。
裴局定理：$ax+by=(a,b)$ 有解（两边同除 $(a,b)$，推论）
$a>b\to a\bmod b\leq a/2$。$O(\log a)$ 轮跑完的 $\gcd$。
$a\bmod b=a-\left\lfloor\frac{a}{b}\right\rfloor b$ 就是写成了 $a,b$ 的线性组合（如果 $\left\lfloor\frac{a}{b}\right\rfloor$ 是常数）

欲求 $ax+by=(a,b)$ 的解，首先求 $(b,a\bmod b)$ 的解，然后将 $a\bmod b$ 换成关于 $a,b$ 的线性组合，这样就能搞出新的 $x,y$。

$bx+(a\bmod b)y=bx+(a-\left\lfloor\frac{a}{b}\right\rfloor b)y$，令 $t=\left\lfloor\frac{a}{b}\right\rfloor $，则 $bx+ay-tby=ay+b(x-ty)$。

为什么不会爆 int？$|x|\leq b,|y|\leq a$。注意边界必须是 $x=1,y=0$，这是归纳基石。假设已求 $bx+(a\bmod b)y$，那么新的解 $x'=x,y'=y-tx$（swap），前一个明显，后一个 $|y'|=|y|+|tx|\leq |a\bmod b|+|\left\lfloor\frac{a}{b}\right\rfloor b|\leq |a|$。反正就是对的（）

解出来的特解 $(x_0,y_0)$，那么解集恰好就是 $\{(x_0+tb,y-ta)|t\in\bf Z\}$。

exCRT

解集一定是 $\pmod{\text{lcm}}$ 意义下同余某个数的集合。

考虑增量，我们合并两个线性同余方程组。

\[\begin{cases} x\equiv a_1\pmod{p_1}\\ x\equiv a_2\pmod{p_2} \end{cases} \Rightarrow x=a_1+m_1p_1=a_2+m_2p_2 \]

所以解方程 $m_1p_1-m_2p_2=a_2-a_1$，根据裴局定理 $(p_1,p_2)|(a_2-a_1)$ 时有解，新的方程为 $x\equiv a_3\pmod{\text{lcm}}$。（为什么是 $lcm$，因为模出来会有一个循环节，把两个循环周期合并就是 $lcm$）

例题：https://www.luogu.com.cn/problem/P4774

因为 $\text{lcm}(\{p_i\})\leq 10^{12}$，我们要解决若干个形如 $a_i-xb_i\equiv 0\pmod{p_i}$ 其中 $b_i$ 是本轮的攻击力，然后解出最小的 $x$。一个一个合并，与下界取 $\max$ 即可。

乘法逆元

$ax\equiv 1\pmod p$，那么 $x$ 和 $a$ 互为逆元。$x=a^{-1}$。

威尔逊定理：$(P-1)!\equiv-1\pmod P$，$P$ 为质数（$P=2$ 特判）。证明：$[1,P-1]$ 中的每个数都有自己的逆元，两两配对，除了 $\pm 1$ 的逆元为自己，那么答案是 $-1$。

求法：exGCD 或者费马小定理（$P$ 为质数，$a^{P-2}$）。

费马小定理：质数 $P$ 和非 $0$ 整数 $a$，$a^{P-1}\equiv 1\pmod P$。考虑 $(P-1)!a^{P-1}\equiv(a)(2a)(3a)\cdots((P-1)a)$，根据刚才那个互不相同（exGCD #1），又因为这里不能有 $0$，所以这玩意恰好等于 $(P-1)!$。因为 $(P-1)!\neq 0$，所以 $a^{P-1}$ 就只能是 $1$。

欧拉定理：对于 $(a,P)=1$，$a^{\varphi(P)}\equiv 1\pmod P$。考虑构造 $A$ 表示 $[1,P]$ 中与 $P$ 互质的数的乘积，再次证明 $A\times a^{\varphi(P)}\equiv A$。继续进行配对（上面能找到下面，下面能找到上面，就相等了，或者扩展一下 exGCD#1 的证明）。

例题：给定质数 $P$，多次询问 $\binom n m\bmod P$，$n,m\leq 10^6,P\leq 10^9$。预处理阶乘逆元即可。

例题：给 $10^7$ 个数，求它们对 $P=998244353$ 的逆元。注意到 $\frac{1}{x}=\frac{(x-1)!}{x!}$。类似的定义，做前缀积和前缀积逆元。$O(n+\log p)$ 只用求最后一项前缀积的逆元。

Lucas

\[\binom n m\equiv \binom{n/P}{m/P}\binom{n\bmod P}{m\bmod P}\pmod P \]

质数 $P$。$n/P$ 向下取整。就是把 $n,m$ 看成 $P$ 进制，每一位的组合数结果的乘积。如果有上面的小于下面的，整个就是 $0$ 了。

生成函数证明：$\binom n m=[x^m](1+x)^n$，右边的等于 $(1+x)^{n\bmod P}[(1+x)^P]^{n/P}$。注意到 $(1+x)^P\equiv 1+x^P\pmod P$，这是因为除了 $i\in\{0,P\}$ 外，$\binom P i$ 的展开，上面有 $P$，下面没有，那么它是 $0$。所以 $[x^m](1+x)^{n\bmod P}(1+x^P)^{n/P}$ 就等于原式。

$\binom n m\equiv$ (n&m)==m $\pmod 2$。或者认为是 $m\subseteq n$。

例题：https://www.luogu.com.cn/problem/solution/P2480 对 $P-1$ 分解质因数之后逐个 Lucas 之后 (ex)CRT 合并。

BSGS

离散对数问题：$a,b,P$，求 $a^t\equiv b\pmod P$，或者说 $t\equiv\log_a b\pmod P$。

当 $P$ 为质数时 BSGS（根号分治）即可。好像任意模数直接做到 $2\varphi(P)$ 就行。这里略过了。本质是对数位两半 meet in the middle。

阶与原根

$x$ 模 $m$ 的阶：最小的 $t$ 使得 $x^t=1\pmod m$（一个周期，循环节长度）

模 $m$ 的原根：模 $m$ 的阶为 $\varphi(m)$ 的数。设为 $g$。$m$ 是质数时，$g^t$ 和 $[1,m-1]$ 形成双射。$\log ab=\log a+\log b$。所以可以取对数了，乘法变加法。

一个数 $m$ 存在原根当且仅当 $m=2,4,p^a,2p^a$，最小原根的大小为 $O(m^{\frac{1}{4}})$。

引理：一个数模 $m$ 的阶存在，那么它一定是 $\varphi(m)$ 的约数。因为阶就是循环节。证明：$x=g^t,g^{\varphi(m)}=1,x^a=g^{ta}=1$ 时，$\varphi(m)|ta$ 即 $a|\varphi(m)$。此时 $a=\frac{\varphi(m)}{\gcd(\varphi(m),t)}$。