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)}\)。
标签：primitive,inverse,frac,Lucas,pmod,bmod,varphi,leq,equiv From： https://www.cnblogs.com/caijianhong/p/17589598.html