$\text{JK_Lover}$ 大帝亲自辅导。
Exgcd
给定 $a,b$ ，求解不定方程 $ax+by=\gcd(a,b)$ 的整数解的算法。已知，当 $ax+by=c$ 有解时，当且仅当 $\gcd(a,b)|c$ 满足时。
我们通过 $bx’+(a\%b)y’=\gcd(b,a\%b)$ 来求解该方程，这个过程与求 $\gcd(a,b)$ 是类似的。而在 $b=0$ 的时候，明显有一组解为 $x=1,y=0$ 。那么，我们从 $bx’+(a\%b)y’=\gcd(b,a\%b)$ 的解 $x=x’,y=y’$ 来递归求解，将 $a\%b$ 展开为 $a-b\times \lfloor \frac{a}{b}\rfloor$ ，将该式带回原式，整理出 $a$ 和 $b$ 的系数，得到 $ay’+b(x’-\lfloor\frac{a}{b}\rfloor\times y’)=\gcd(b,a\%b)=\gcd(a,b)$ ，从而得到 $x=y’,y=x’-\lfloor\frac{a}{b}\rfloor\times y’$ 。
而对于一般解 $ax+by=c$ 的方程，有 $k=\frac{c}{\gcd(a,b)}$ ，则用 $\text{exgcd}$ 求出一组解之后再将 $x,y$ 扩大 $k$ 倍即可。
时间复杂度同 $\gcd(a,b)$ 为 $\mathcal O(\log \min(a,b))$ 。
逆元
如果有 $ax\equiv 1 \pmod m$ 成立，则 $a$ 是 $x$ 在模 $m$ 意义下的逆元。记作 $x^{-1}$ ，后也记作 $inv(x)$ 。
模数为质数的求法
有费马小定理：$x^{m-1}\equiv 1\pmod m$ ，而显然， $x^{m-2}\times x^{1}\equiv 1\pmod m$ ，那么， $x^{x-2}$ 就是 $x$ 在模 $m$ 意义下的逆元。在使用快速幂的前提下的时间复杂度为 $\mathcal O(\log m)$ 。
线性递推式
首先有 $inv(1)=1$ ，对于 $x>1$ 有 $\lfloor\frac{m}{x}\rfloor\times x+(m\%x)\equiv 0\pmod m$ ，然后得到式子 $(m\%x)\equiv m-\lfloor\frac{m}{x}\rfloor\times x\pmod m$ ，然后在式子两端同时乘上 $inv(x)\times inv(m\%x)$ 得到：
$inv(x)\equiv inv(m\%i)\times (m-\lfloor\frac{m}{i}\rfloor)\pmod m$
这样就得出了逆元的线性递推式。这种方法只能用于 $m$ 是质数的情况，且限制情况较多。
此情况的时间复杂度是 $\mathcal O(n)$ 。
CRT
中国剩余定理（$\text{Chinese Remainder Theorem}$），用于求解满足：
其中 $m_1,m_2…m_k$ 两两互质（但不一定是质数），的最小的 $x$ 值。
设 $M=\prod m_i$ ，利用 $\text{exgcd}$ 求出 $\frac{M}{m_i}$ 的逆元，记为 $p_i$ ，求出一个数 $x_i=\frac{M}{m_i}\times p_i$ ，所以有 $x_i\times a_i\equiv 1\pmod{m_i}$ 且 $x_i\times a_i\equiv 0\pmod{m_j},i\ne j$ ，此时构造出的 $X_i=x_i\times a_i$ 满足了第 $i$ 个方程的限制，且不影响其他方程。那么合并方程解得到 $x=\sum x_i\times a_i\pmod M$ 即可。
$\text{CRT}$ 的时间复杂度为 $\mathcal O(n\log M)$ 。
EXCRT
扩展中国剩余定理，与 $\text{CRT}$ 求解一样的同余方程组，但 $m_1,m_2…m_k$ 不要求两两互质。
不断将两个同余方程合并为一个等价的同余方程：
对于 $x\equiv a_1\pmod{m_1},x\equiv a_2\pmod{m_2}$ ，将同余方程转化成不定方程，变成 $x=a_1+k_1\times m_1=a_2+k_2\times m_2$ ，得到 $k_2m_2-k_1m_1=a_1-a_2$ ，通过 $\text{Exgcd}$ 求得 $k_1,k_2$ ，然后代入求得 $x\equiv a_1+k_1m_1\pmod{\text{lcm}(m_1,m_2)}$ ，这就是合并的结果。最后得到一个方程时得到通解。
$\text{ExCrt}$ 的时间复杂度也是 $\mathcal O(n\log M)$ 。
模板
AC Code
1 | ll N,px[MAXN],bx[MAXN]; |
例题
在这道题中 $m_i$ 是固定的。
对于每一次选用的剑，我们可以用 multiset 预处理出来。
对于每条龙的恢复力 $p_i$ ，我们在砍完之后需要让龙的血量为 $p_i$ 的负 $k$ 倍。则在每次攻击的时候，我们需要满足 $atk_i\times x\ge a_i,atk_i\times x\equiv a_i\pmod{p_i}$ 。
这道题有一个特性，要么满足 $p_i=1$ ，要么满足 $a_i\le p_i$ 。所以需要分情况讨论。
对于满足特性 $1$ 的情况：
对于 $atk_i\times x\ge a_i$ 且 $p_i=1$ 时，只需求出将每只龙的生命值打到非正数的次数，取最大值即可，即 $\max(\frac{a_i}{atk_i})$ ，容易处理。
对于满足 $a_i\le p_i$ ，我们用 $\text{ExCrt}$ 来解：
同余式是 $atk_i\times x\equiv a_i\pmod{p_i}$ ，化成单式得到 $x\equiv a_i\times atk_i^{-1}\pmod{p_i}$ ，根据同余的消去律，我们先同时除以 $\gcd(atk_i,a_i,p_i)$ ，此时，如果 $atk_i,p_i$ 不互质，则无解；否则，转化完之后直接套板子求就完事了。
对于大数据 long long x long long 的情况，则会爆 $1e18$ ，所以使用龟速乘优化模数以免出错。也可以使用 long double 来存储，实现 $\mathcal O(1)$ 快速乘，但出错率较大。
1 | typedef long long LoveLive; |
此定义 typedef 源于 $\text{JK_Lover}$ 大帝。
BSGS
大步小步算法（$\text{Baby Step,Giant Step}$），用于求解离散对数问题，求解同余方程 $a^x\equiv b\pmod p$ ，的解 $x$ ，其中 $a,p$ 互质。
记有 $m=\sqrt p$ ，对于任意的 $x$ ，将 $x$ 写成 $x=im-j(0\le j<m)$ ，则存在一个式子 $a^{i\times m}\equiv b\times a^j\pmod p$ ，则枚举 $j$ ，将 $b\times a^j$ 存到 $\text{hash}$ 表中，第二次枚举 $i$ ，在 $\text{hash}$ 表中查询与 $a^{i\times m}$ 相等的 $b\times a^j$ ，则一对 $i,j$ 确定一个解 $x$ 。如果求取最大或者最小解的话，则安排枚举顺序即可。
时间复杂度为 $\mathcal O(\sqrt p\times t)$ 。其中 $t$ 表示 $\text{hash}$ 表使用的时间。
对于最小解，我们首先使 $i$ 尽量小，然后使 $j$ 尽量大。因为有 $0\le j <m$ ，所以 $j$ 对答案的影响没有 $i$ 大。所以我们首先枚举 $a^{im}\equiv ba^j\pmod p$ ，对应出 $h[i]=j$ ，然后从小到大枚举 $i$ 找到与最小的 $i$ 对应的 $j$ ，就是最小解。
而对于 $a,p$ 互质的使用，则在于将 $a^{im-j}\equiv b\pmod p$ 转化为 $a^{im}\equiv b\times a^j\pmod p$ 时，使用了 $a^j$ 的逆元。
P3846 [TJOI2007] 可爱的质数/【模板】BSGS
AC Code
1 | ll A,B,P; |
EXBSGS
用于求解 $a,p$ 不一定互质的 $a^x\equiv b\pmod p$ 方程。
令 $d=\gcd(a,p)$ ，显然，在 $d=1$ 时，用 $\text{BSGS}$ 求解即可。
如果有 $d\not\mid b$ ，则有 $a^{x-1}\times\frac{a}{d}\equiv \frac{b}{d}\pmod {\frac{p}{d}}$ 重复该操作直到 $d=1$ ，得到 $a^{x-k}\times \frac{a}{\prod d}\equiv \frac{b}{\prod d}\pmod{\frac{p}{\prod d}}$ ，此时 $\gcd(a,\frac{p}{\prod d})=1$ ，转化成普通的 $\text{BSGS}$ 问题求解即可。
还需要判断 $x<k$ 的情况是否有解。此时也是可能有解的，直接枚举$x$ 从 $0\sim k$ ，暴力判断 $a^{x-k}$ 是否同余 $b$ 即可。
$k$ 是 $\mathcal O(\log p)$ 级的，所以时间复杂度是 $\mathcal O(\sqrt p)$ 。
数据各有卡点，挺离谱的。
AC Code
1 |
|
原根
定义一个 $g$ 满足 $g^1,g^2,g^3…g^{\phi(p)}$ 在模 $p$ 的意义下两两不相等，则 $g$ 是 $p$ 的原根。其中 $\phi(p)$ 表示与 $p$ 互质的数的个数。
对于一个质数 $p$ ，当 $g^i\not\equiv g^j\pmod p,i\ne j,i,j\in [0,p-1]$ 成立时， $g$ 是 $p$ 的原根。
原根存在条件
- 奇质数一定存在原根；
- 如果 $g$ 是 $p$ 的原根，则 $g+p$ 或 $g$ 是 $p^2$ 的原根。
- 只有 $2,4,p^k,2\times p^k$ 的数存在原根，其中 $p$ 为奇质数，$k$ 为正整数。
- 若 $p$ 存在原根，则 $p$ 的原根个数为 $\phi(\phi(p))$ 个。
查找原根
检验原根，则是枚举 $g$ 的质因数 $x$ ，并验证 $g^{\frac{\phi(p)}{x}}=1$ 是否成立，如果成立，则 $g$ 不是 $p$ 的原根。
因为有欧拉定理：$a^{\phi(p)}\equiv 1\pmod p$ ，所以如果上述式子提前成立，则证明其循环节不超过 $p-1$ ，则 $g$ 不是 $p$ 的原根。
经数学家证明，一个数如果存在原根，其最小原根是较小的，因此可以用枚举找原根。
阶
对于两个数 $a,m\in\mathbb N_+$ ，有 $a\perp m$ （$a$ 与 $m$ 互质），使 $a^x\equiv 1\pmod m$ 成立的最小正整数 $x $ ，被称为 $a$ 模 $m$ 的阶，记作 $\operatorname{ord}_ma$ 。
阶的性质
- $a^n\equiv 1\pmod m$ 的充要条件是 $\operatorname{ord}_ma\mid n$ 。
- $\operatorname{ord}_ma\mid\varphi(m)$ 。
- 若 $a\equiv b\pmod m$ ，则 $\operatorname{ord}_ma=\operatorname{ord}_mb$ 。
二次剩余 - Cipolla
用于在模奇质数 $p$ 意义下开根号，即求方程 $x^2\equiv n\pmod p$ 的解 $x$ 。
勒让德符号
定义 $(\frac{n}{p})=n^{\frac{p-1}{2}}$ 称为勒让德符号。
根据欧拉准则：
- 当 $(\frac{n}{p})\equiv 1\pmod p$ 时，$n$ 是 $p$ 的二次剩余，原方程有解；
- 当 $(\frac{n}{p})\equiv -1\pmod p$ 时， $n$ 不是 $p$ 二次剩余，原方程无解；
- 当 $(\frac{n}{p})\equiv 0\pmod p$ 时，$n\equiv 0\pmod p$ 。
求解二次剩余
对于 $n$ 是 $p$ 的二次剩余，我们随机值一个 $a$ ，使 $a^2-n$ 不为 $p$ 的二次剩余。（期望步数为 $2$ ）记一个 $\omega=\sqrt{a^2-n}$ ，类似于复数的定义，定义一个新数域 $z=x+y\times\omega(x,y\in\mathbb N)$ ，可以得到 $x\equiv \pm(a+\omega)^{\frac{p+1}{2}}\pmod p$ 为原方程的解。
简单证明：（省略 $\pmod p$ 的书写）
由 $x\equiv \pm(a+\omega)^{\frac{p+1}{2}}$ 得到：$x^2\equiv(a+\omega)^p(a+\omega)$ ，由二项式定理展开得到：
$(a+\omega)^p\equiv\sum^p_{i=0}(^p_i)a^i\omega^{p-i}$
然后根据 $\text{Lucas}$ 定理得到当且仅当 $i=\{0,p\}$ 时， $(^p_i)$ 模 $p$ 不为 $0$ 。从而得到：
$(a+\omega)^p\equiv a^p+\omega^p$ 。又有 $a^p\equiv a$ ，则 $\omega^p\equiv \omega\times(\omega^2)^{\frac{p-1}{2}}\equiv-\omega$ 。
则：
$x^2\equiv (a-\omega)(a+\omega)\equiv a^2-\omega^2\equiv n$
证毕。
所谓使用的 $\text{Lucas}$ 定理，则是由 $\binom{p}{i}=\frac{p^{\underline{i}}}{i!}$ ，而 $\binom{p}{i}$ 在模 $p$ 意义下当且仅当 $i=\{0,p\}$ 成立时不为 $0$ 。
斐波那契数列循环
可以证明，在模 $p$ 意义下，斐波那契数列有循环节，且循环节长度上界是 $6p$ ，即在至多 $6p$ 的情况下，模 $p$ 的斐波那契会进入循环。
生日悖论与指针扫描
随机取出两个 $pos$ 并检验以 $pos$ 为起始的两位是否出现过。由生日悖论可以得到期望下，只要 $\mathcal O(\sqrt p)$ 次即可得到一个循环节，但不一定最小。然后枚举因数验证。
矩阵大步小步
对矩阵进行 $\text{BSGS}$ ，令转移矩阵为 $A$ ，则有 $A^k=I$ ，由斐波那契定义得到 $A$ 一定存在逆。
结论法
- 当 $p$ 十分小的时候，可以直接开摆；
- 若 $p$ 为奇质数：
- 若 $5$ 是模 $p$ 意义下的二次剩余，循环节长度一定是 $p - 1$ 的约数；
- 否则，循环节长度一定是 $2p + 2$ 的约数；
- 否则， $p$ 是合数，也有结论，但不可用。