概念不说了。

同余方程

同余方程基本形式：\(ax\equiv c(\text{mod}\space b)\)。

\(ax\equiv c(\text{mod}\space b)\Longleftrightarrow \exists y\in \mathbb{Z},s.t. ax+by=c\)

\(ax+by=c\) 就可以用扩展欧几里得来求。

代码：

int exgcd (int a, int b, int& x, int& y) {
  if (!b) {
    x = 1, y = 0;
    return a;
  }
  int d = exgcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}

乘法逆元

若 \(ax\equiv 1(\text{mod} p)\)，并且 \((a,p)=1\)，则称 \(a\) 与 \(x\) 在 \(\text{mod} p\) 下互为逆元，\(x=\text{inv}(a)\)。

求解乘法逆元的方法：

1. 扩欧，适合求某一个数的逆元。
2. 费马小定理，若 \(p\) 是质数，且 \((a,p)=1\)，则 \(a^{p-1}\equiv 1(\text{mod} p)\)，那么 \(\text{inv}(a)=a^{p-2}\)。适用于 \(p\) 为质数的情况。
3. 线性递推求逆元，适合求 \(1\sim n\) 的逆元。

\[设\space p=aq+r,q=\bigg\lfloor\dfrac{p}{a}\bigg\rfloor，r=p\bmod a\\ \begin{aligned} aq+r&\equiv 0(\text{mod}\space p)\\ aq&\equiv -r(\text{mod}\space p)\\ a&\equiv -r\cdot \text{inv}(q)(\text{mod}\space p)\\ \text{inv}(a)&\equiv -q\cdot \text{inv}(r)(\text{mod}\space p)\\ \end{aligned}\\ 那么\space \text{inv}[a]=-\bigg\lfloor\dfrac{p}{a}\bigg\rfloor\cdot \text{inv}[p\bmod a] \]