前置提醒：该笔记比较潦草，主要是记录数论的学习的，所以会出现不少直接引用文献的地方；如果只是不知道如何复习，可以直接跳转到每次复习的参考文献。
2023.02.02 扩展欧几里得与线性同余方程
线性同余方程的简要定义
形如
$$
ax \equiv b\space (mod \space n) \tag{1}
$$
的方程称为线性同余方程。
逆元求解的主要思路
以下情况没带“ $’$ ”的表示$a,n$不互素。
设$g = gcd(a,n)$，这里$g$值大于1。若$g \nmid b$，则无解。
疑难点： 对于任意的 $x$，方程 $ax\equiv b\pmod n$ 的左侧始终可被 $g$ 整除，而右侧不可被 $g$ 整除，因此无解。
如果$g \mid b$，那太好了！根据同余的性质：
若 $a,b\in\mathbf{Z},d,m\in\mathbf{N}^*,d\mid a,d\mid b,d\mid m$，则当 $a\equiv b\pmod m$ 成立时，有 $\dfrac{a}{d}\equiv\dfrac{b}{d}\left(\bmod\;{\dfrac{m}{d}}\right)$。
有
$$
a’x \equiv b’\space (mod \space n’) \tag{2}
$$
（其中$a’ = \frac{a}{g}$，$b’,n’$同）
将$(2)$式两边乘上$a^{-1}$，得到方程的一个解：
$$
x \equiv b’ \cdot a’^{-1}\space \pmod {n’} \tag{3}
$$
由于$g \gt 1$，会有不止一个解，则有：
$$
x_i\equiv (x^{‘} + i\cdot n^{‘}) \pmod n \quad \text{for } i = 0 \ldots g-1
$$
（如何求逆元？扩展欧几里得法……属实是头尾衔接的很好）
前置知识：扩展欧几里得算法
OIer wiki将其放在了最大公约数章节。
设
$$
\begin{aligned}
ax_1+by_1 & = \gcd(a,b)
\
bx_2+(a\bmod b)y_2 & = \gcd(b,a\bmod b)
\end{aligned}
$$
由欧几里得定理可知：
$$
\begin{aligned}
\gcd(a,b) & = \gcd(b,a\bmod b) \
\Rightarrow ax_1+by_1 & = bx_2+(a\bmod b)y_2
\end{aligned}
$$
$$
\begin{aligned}
a\bmod b &= a-(\lfloor\frac{a}{b}\rfloor\times b) \
\Rightarrow ax_1+by_1 &= bx_2+(a-(\lfloor\frac{a}{b}\rfloor\times b))y_2
\end{aligned}
$$
将其带入原式，有：
$$
ax_1+by_1=ay_2+bx_2-\lfloor\frac{a}{b}\rfloor\times by_2=ay_2+b(x_2-\lfloor\frac{a}{b}\rfloor y_2)
$$
因为 $a=a,b=b$，所以整理得到：
$$
x_1=y_2,y_1=x_2-\lfloor\frac{a}{b}\rfloor y_2
$$
将
OIerwiki的代码实现：
int Exgcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1;
y = 0;
return a;
}
int d = Exgcd(b, a % b, x, y);
int t = x;
x = y;
y = t - (a / b) * y;
return d;
}求解的具体实现——扩展欧几里得
定理 1： 线性同余方程 $ax\equiv b \pmod n$ 可以改写为如下线性不定方程：
$$
ax + nk = b
$$
其中 $x$ 和 $k$ 是未知数。这两个方程是等价的，有整数解的充要条件为 $\gcd(a,n) \mid b$。
根据定理 1，对于线性不定方程 $ax+nk=b$，可以先用扩展欧几里得算法求出一组 $x_0,k_0$，也就是 $ax_0+nk_0=\gcd(a,n)$（这是exgcd的标准形式），然后两边乘上$\frac{b}{\gcd(a,n)}$，就可以得到标准方程了：
$$
a\dfrac{b}{\gcd(a,n)}x_0+n\dfrac{b}{\gcd(a,n)}k_0=b
$$
于是找到方程的一个解。
定理 2： 若 $\gcd(a,n)=1$，且 $x_0$、$k_0$ 为方程 $ax+nk=b$ 的一组解，则该方程的任意解可表示为：
$$
x=x_0+nt
\
k=k_0-at
$$
并且对任意整数 $t$ 都成立。
最小整数解：
$$
x=(x \bmod t+t) \bmod t
$$
其中有
$$
t=\dfrac{n}{\gcd(a,n)}
$$
（2023.05.21）Fixed（经典推完了，写代码还是一脸懵逼）
LL exgcd(LL a,LL n,LL& x,LL& k){
if(!n){
x=1;k=0;return a;
}
LL gcd = exgcd(n,a%n,x,k);
// x1 = y2 , y1 = x2 - (a/b) * y2
LL tmp = x; x = k; k = tmp - (a/n) * k;
return gcd;
}
LL liEu(LL a,LL n,LL b,LL& x,LL& k){
LL gcd = exgcd(a,n,x,k); // 求扩展exgcd，试图得出一个基础解
if (b % gcd) return false; // 判断有解的条件
LL t = b / gcd;
x *= t; k *= t; // 由gcd解转化为方程解，在欧几里得求线性同余中，k不重要。
//可选：求x的最小解，此时把k舍去
x = (x % (n / gcd) + (n / gcd)) % (n / gcd);
return true;
}
