$\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$ 是合数,也有结论,但不可用。