exgcd
\(ax + by = c\)
- 裴蜀定理：\(\exist x,y ,ax + by = gcd(a,b)\)
证明简单，那么必然满足 \(gcd(a,b)|c\)
然后只需要求出 \(ax + by = gcd(a,b)\) 的一组解即可
在欧几里得算法进行的过程中，最后一步结果取 \(x=0,y=1\) 就是满足的
\(xb+y(a\%b) = gcd(a,b)\)
\(xb+y(a\%b) = xb+y(a-b\lfloor{\frac{a}{b}}\rfloor) = ya + (x-\lfloor{\frac{a}{b}}\rfloor)b\)
那么可以迭代求解
中国剩余定理
\(\begin{equation}\begin{cases}x \equiv a_1 \pmod{p_1}\\x \equiv a_2 \pmod{p_2} \\ \dots \\ x \equiv a_n \pmod{p_n} \end{cases}\end{equation}\)
对于 \(p_1 \dots p_n\) 两两互质的情况
我们令 \(M = \prod\limits_{i=1}^{n}p_i\)
令 \(t_i\frac{M}{p_i} \equiv 1 \pmod{p_i}\)
那么容易验证一个解就是 \(\prod\limits_{i=1}^{n}\frac{M}{p_i}t_i\)
但是倘若 \(p\) 不两两互质，这个做法就会出问题，那么考虑每次合并两个同余式为一个新的同余式
\(x \equiv a_1 \pmod{p_1}\\x \equiv a_2 \pmod{p_2}\)
令 \(t = gcd(p_1,p_2)\)
考虑在模 \(\frac{p_1p_2}{t}\) 意义下，相当于式子
\(a_1 + k_1\frac{p_2}{t} = a_2 + k_2\frac{p_1}{t}\)
的一组解 \(k_1,k_2\)，而这个是一个 exgcd 的形式
那么可以将两式合并为
\(x \equiv a_1 + k_1\frac{p_2}{t} \pmod{\frac{p_1p_2}{t}}\)
最后剩下的问题是，为什么 \(\frac{p_1p_2}{t}\) 中只存在一组解
对于两个解，一个是 \(x_1\) ，一个是 \(x_2\)
那么 \(x_2 = x_1+k_1p_1,x_2 = x_1 + k_2p_2\)
不难发现 \(k_1p_1 = k_2p_2\)，那么 \(\frac{p_1p_2}{t} | k_1p_1\)
BSGS
\(a^x \equiv b \pmod{p}\)
当 \(gcd(a,p) = 1\) 时
由欧拉定理 \(x \le \varphi(p)\)
我们注意到每个 \(x\) 都能表示成 \(kB+b\)
那么预处理出前 \(B\) 个然后枚举 \(k\) 在 map 里查询即可
复杂度 \(O(B+\frac{\varphi(p)}{B})\)
而对于 \(gcd(a,p) \neq 1\) 的情况
令 \(t = gcd(a,p)\)
则 \(\frac{a}{t}a^{x-1} \equiv \frac{b}{t} \pmod{\frac{p}{t}}\)
注意到若 \(t \nmid b\) 则无解
然后迭代直至 \(gcd(a,\frac{p}{t_1 \dots t_k}) = 1\)
N次剩余
\(x^a \equiv b \pmod{p}\)
首先将 \(p\) 拆分为 \(p = \prod\limits_{}p_i^{q_i}\)
对于每一个 \(p_i^{q_i}\) 求解，然后中国剩余定理合并即可
\(x^a \equiv b \pmod{p^q}\)
- \(p^q | b\)
\(x^a \equiv 0 \pmod{p^q}\)，只要满足 \(p^{\lceil\frac{q}{a}\rceil}|x\) 即可
-
\(p \neq 2\)
令 \(t = gcd(p^q,b)\)
\(\frac{x^a}{t} \equiv \frac{b}{t} \pmod{\frac{p^q}{t}}\)
那么只需要保证 \(x\) 是某个最小的数 \(m\) 满足 \(t|m^a\) 的倍数即可
接下来就变为 \(gcd(p^q,b) = 1\) 的情况了
此时找到 \(p^q\) 的一个原根 \(g\)
那么 \(\frac{b}{t}\) 能表示成 \(g^{b_0}\)，两边以 \(g\) 为底取对数
\(xa \equiv b_0 \pmod{\varphi(\frac{p^q}{t})}\)
当然我们可以用 exgcd 找出通解 \(x_0+k\frac{\varphi(\frac{p^q}{t})}{gcd(a,\varphi(\frac{p^q}{t}))}\)
然后看有多少是 \(m\) 的倍数，因为 \(m\) 必然也是 \(p\) 的次幂，这一点好做到
-
\(p=2^p\)
\(2^q\) 没有原根，因此需要特殊处理
然后我们考虑对于每个 \(k\) 算出 \(x^a \equiv b \pmod{2^k}\) 的解
能够发现，对于 \(k+1\) 处的解必然形如 \(x\) 或 \(x+2^k\)，那么暴力即可
但是具体复杂度没法证明