0 前言
闲的没事的时候可能会摸鱼写一写，都是些非常基础的东西。
最高大概会写到 exCRT 和 exBSGS 吧，阶和原根往后的我也不会了，但是前面的内容会时不时来补充。
为了方便偷懒，许多定理不会给出证明。
1 基本概念
-
\(\gcd(a,b)\) 或者 \((a,b)\)：\(a,b\) 的最大公约数。
-
\(\rm{lcm}(a,b)\) 或者 \([a,b]\)：\(a,b\) 的最小公倍数。
-
\(a\mid b\)：\(a\) 整除 \(b\)，即 \(b\ {\rm mod}\ a=0\)。
-
\(a\equiv b\pmod m\)，表示 \(a\) 和 \(b\) 在模 \(m\) 意义下相等·，即 \(a\bmod m=b\bmod m\)。
1.1 有点用的小性质
-
\(a\equiv b\pmod m\)，当且仅当 \(m\mid(a-b)\)。
-
\(a\equiv b\pmod n,a\equiv b\pmod m\Rightarrow a\equiv b\pmod {[n,m]}\)。
- 特别情况：如果 \((n,m)=1\)，\(a\equiv b\pmod {nm}\)
-
\(ka\equiv kb\pmod m\Rightarrow a\equiv b\pmod {\frac{m}{(k,m)}}\)。
- 证明：根据第一点可以变形成 \(m\mid (ka-kb)\)，即 \(m\mid k(a-b)\)，两边同时除以一个 \((k,m)\) 得到 \(\frac{m}{(k,m)}\mid\frac{k}{(k,m)}(a-b)\)，而 \(\frac{m}{(k,m)}\) 和 \(\frac{k}{(k,m)}\) 显然互质，因此 \(\frac{m}{(k,m)}\mid (a-b)\)，然后就可以重新变形成上面的式子了。
2 二元一次不定方程
问题描述：
求 \(ax+by=c\) 的所有整数解，其中 \(a,b,c\) 为整数。
前置知识：欧几里得算法求最大公约数，即 \((a,b)=(b,a\bmod b)\)。
2.1 裴蜀定理
对于任意整数 \(a,b,c\)，有
考虑证明，实际上我们只需要证明 \(ax+by=(a,b)\) 一定有解就可以了，这样再给解乘上一个 \(\frac{c}{(a,b)}\) 就能得到上面方程的解了，那就引出了我们接下来的重点——扩展欧几里得算法。
2.2 扩展欧几里得算法（exgcd 算法）
用途：用于求解 \(ax+by=(a,b)\) 的特解。
首先是终止条件，如果 \(b=0\)，显然可以令 \(x=1\)，\(y=0\)。
我们可以考虑下怎么由 \((b,a\bmod\ b)\) 的答案推出 \((a,b)\)，假设我们有
用 \(a-\lfloor\frac{a}{b}\rfloor b\) 代替 \(a\ {\rm mod}\ b\)，然后去括号，得
整理一下，变成上面的形式，得
因此，当求出 \(bx'+(a\bmod b)y'=(b,a\bmod b)\) 的解之后，原方程的解就是 \(x=y'\)，\(y=x'-\lfloor\frac{a}{b}\rfloor y'\)。
归纳证明可得成立。
代码：
void exgcd(int a,int b,int &x,int &y){
if(!b){
x=1,y=0;
return;
}
exgcd(b,a%b,x,y);
int tmp=x;
x=y,y=tmp-(a/b)*y;
}
其实有个更短的：
void exgcd(int a,int b,int &x,int &y){
if(!b) return x=1,y=0,void();
exgcd(b,a%b,y,x);y-=a/b*x;
}
2.3 解系
考虑我们刚刚用 exgcd 求出的只是 \(ax+by=(a,b)\) 的一组特解，现在我们将这组特解记为 \((x_0,y_0)\)。
那么如果我们想要求出这个不定方程的整个解系呢？就是接下来的内容了。
考虑 \(ax+by\) 的和是不变的，因此如果 \(x\) 变大了，那么 \(y\) 显然就需要变小，而且每相邻两组解其对应的 \(x\)，\(y\) 的变化量也会是一定的。现在我们记 \(x\) 的变化量为 \(\Delta x\)，\(y\) 的变化量为 \(\Delta y\)，增减次数为 \(k\)，那么代回原方程后就是
左边把括号拆开，整理一下，变成
显然只有在 \(ak\Delta x=bk\Delta y\) 的时候变化量才会抵消，否则结果就变了。
令 \(\Delta x=\frac{b}{(a,b)},\Delta y=\frac{a}{(a,b)}\)，即可在保证正负抵消的情况下不漏解。
综上所述，求出特解之后，不定方程的整个解系为：
3 一些相关的定理
3.1 费马小定理
结论：对于任意一个整数 \(a\) 和一个质数 \(p\)，都有 \(a^{p-1}\equiv 1\pmod p\)。
典型的应用会放在下面的乘法逆元中。
3.2 欧拉定理
前置知识：欧拉函数 \(\varphi\)，\(\varphi(n)\) 表示 \([1,n]\) 中与 \(n\) 互质的数的个数。
结论：若 \((a,m)=1\)，则 \(a^{\varphi(m)}\equiv 1\pmod m\)。
如果 \(m\) 为质数，那么就有 \(\varphi(m)=m-1\)，上面的式子也就变成了 \(a^{m-1}\equiv m\pmod m\)，也就是费马小定理的形式，因此费马小定理其实是欧拉定理的特殊情况。
我们不妨来看一下欧拉定理的一个典型应用。
问题描述：
求 \(a^b\bmod m\)，保证 \((a,m)=1\)。
\(a,m\le 10^6\)，\(b\le 10^{114514}\)。
结论：\(a^b\equiv a^{b\bmod \varphi(m)}\pmod m\)，也就是说我们可以将指数对 \(\varphi(m)\) 取模。
证明：设 \(b=k\varphi(m)+r\)，其中 \(k\in\Z\)，\(0\le r<\varphi(m)\)，也就是将 \(b\) 写成带余除法的形式。
根据欧拉定理，不难得到
因此，我们其实也可以将 \(\varphi(m)\) 理解成循环节。
3.3 扩展欧拉定理
对于任意整数 \(a,b,m\)，我们有
3.4 威尔逊定理
4 乘法逆元
4.1 基本性质
定义：若 \(ax\equiv 1\pmod m\)，则称 \(x\) 为 \(a\) 在模 \(m\) 意义下的乘法逆元，通常将 \(x\) 记作 \(a^{-1}\)。
注意到 \(x\) 存在的充要条件为 \((a,m)=1\)，也就是 \(a,m\) 互质，下面给出简单的证明：
\(ax\equiv 1\pmod m\) 相当于存在一个整数 \(k\)，满足 \(ax=km+1\)，也就是 \(ax-km=1\)，根据裴蜀定理（注意这里未知的是 \(x\) 和 \(k\)）可知有解的充要条件为 \((a,m)=1\)。
乘法逆元主要的用途是进行模意义下的除法运算，比如要计算 \(\frac{a}{b}\pmod m\) 时，我们其实只需要计算 \(ab^{-1}\pmod m\) 就可以了。
现在开始，为了方便，下文中若无特殊说明，“逆元”均指乘法逆元。
4.2 求单个数的逆元
\(ax\equiv 1\pmod m\) 相当于存在一个整数 \(k\)，满足 \(ax-km=1\)，使用 exgcd 求解即可，时间复杂度为 \(O(\log m)\)。
特别地，也是更通常地，当 \(m\) 为质数时，根据费马小定理有 \(a^{m-1}\equiv 1\pmod m\)，而 \(a^{m-1}=a\times a^{m-2}\)，所以此时 \(a^{-1}\equiv a^{m-2}\pmod m\)，可以使用快速幂同样以 \(O(\log m)\) 的时间复杂度求解。
4.3 线性求多个数的逆元
本段所讲内容的时间复杂度均为线性。
4.3.1 求 \(n\) 以内的阶乘的逆元
不难发现
先求出 \(n!^{-1}\)，然后直接倒着递推即可，时间复杂度 \(O(n)\)。
4.3.2 求任意 \(n\) 个数的逆元
假设我们要求 \(a_1,a_2,...,a_n\) 的逆元，我们考虑搞出一个类似于阶乘的形式，记 \(\text{pre}_i=\prod_{j=1}^i a_j\)，\(\text{ipre}_i=\text{pre}_i^{-1}\)，\(\text{inv}_i=a_i^{-1}\)，不难推出
细节：实际写的时候注意下 \(\text{pre}_0\)，不然可能会出点小锅。
5 线性同余方程组
问题描述：
求解形如下面这种形式的线性同余方程组
\[\begin{cases} x\equiv a_1\pmod {m_1} \\ x\equiv a_2\pmod {m_2} \\ \dots \\ x\equiv a_n\pmod {m_n} \end{cases} \]
5.1 中国剩余定理（CRT）
当模数 \(m_1,m_2,\ldots,m_n\) 之间两两互质时，我们就可以使用 CRT 来求解方程组。
记 \(M=\prod_{i=1}^n m_i\)，设 \(t_i\equiv (\frac{M}{m_i})^{-1}\pmod {m_i}\)，那么有一个通解
最小正整数解对 \(M\) 取余即可。
CRT 的证明是显然的这次是真的显然，直接将上面给出的 \(x\) 回代到每个方程即可。
时间复杂度 \(O(n\log n)\)。
实际上你也可以跳过 CRT，直接学习 exCRT，因为 CRT 能解决的问题 exCRT 也一定能用同样的复杂度解决。
5.2 扩展中国剩余定理（exCRT）
当模数之间不保证两两互质时，我们就需要用到 exCRT 了。
实际上 exCRT 与 CRT 之间并没有任何关联，exCRT 的核心思想是将同余方程两两合并。
假如现在我们有两个同余方程
将它们变变形式，可以得到：
联立之后可以得出
这个可以直接使用 exgcd 解出来 \(k_1,k_2\)，然后我们就可以得到一个满足上述两个方程的特解 \(x_0\)。但是，这有什么用呢？
exCRT 告诉我们，原来的两个方程可以合并为 \(x\equiv x_0\pmod {[m_1,m_2]}\)，这里 \([m_1,m_2]\) 为 \(m_1,m_2\) 的最小公倍数。
这个证明其实也并不复杂，可以直接把 exgcd 的整个解系写出来暴力代入来证，但是我比较懒就不写了。
时间复杂度 \(O(n\log n)\)。
6 离散对数
问题描述：
求一个最小的非负整数 \(x\)，使得 \(a^x\equiv b\pmod m\)。
可以理解为求模 \(m\) 意义下的 \(\log_a b\)。
6.1 大步小步算法（BSGS）
当 \((a,m)=1\)，也就是 \(a,m\) 互质时，我们就可以通过 BSGS 来求解。
设 \(x=kB-c\)，且 \(c\in[0,B-1]\)，那么方程就可以写成 \(a^{kB}\equiv a^cb\pmod m\)。
根据欧拉定理，有意义的 \(k\) 最多只有 \(O(\frac{m}{B})\) 种。先用 \(O(B)\) 的时间复杂度枚举 \(c\)，将所有 \(a^cb\) 塞进哈希表里，然后再枚举 \(k\)，每次检查 \(a^{kB}\) 是否在哈希表中存在即可。
令 \(\frac{m}{B}=B\)，解得 \(B=\sqrt{m}\)，因此最优时间复杂度为 \(O(\sqrt m)\)。
unordered_map<int,int>mp;
int BSGS(int a,int b,int p){
mp.clear();a%=p;b%=p;
int B=sqrt(p)+1,v=b,s=1;
For(i,1,B) mp[v=v*a%p]=i,s=s*a%p;
for(int i=1,v=s;i<=B;i++,v=v*s%p)
if(mp.count(v)) return i*B-mp[v];
return -1;
}
6.2 扩展大步小步算法（exBSGS）
不会，咕咕咕。