数学 - 洛谷保存站

### 费马小定理

$$
a^{p-1}\bmod p=1
$$

用处是乘法逆元，$a^{-1}\bmod p=a^{p-2}\bmod p$。

### 欧拉定理 / 欧拉函数

欧拉函数性质：

* $\varphi(x)=\sum_{i=1}^n[\gcd(i,x)=1]$
  
* $x\in P$ 时有 $\varphi(x)=x-1$
  
* 是积性函数
  
* $n=\sum_{d|n}\varphi(d)$
  
* $\forall p\in P$ 有 $\varphi(p^k)=p^k-p^{k-1}$
  
* $\varphi(n)=n\sum_i(1-\frac{1}{p_i})$

线性筛，考虑使用积性函数方式。如果 $p|x$ 有 $\varphi(px)=p\cdot\varphi(x)$，否则乘起来。

欧拉定理：

$$
\forall\gcd(x,m),x^{\varphi(m)}\bmod m=1
$$

### 威尔逊定理

$$
(p-1)!\bmod p=p-1
$$

### 裴蜀定理

对于任意整数 $x,y$ 有 $\gcd(a,b)|ax+by$ 且存在 $x,y$ 使得 $ax+by=\gcd(a,b)$

### 欧几里得和拓展欧几里得

$\gcd(x,y)=\gcd(y,x\bmod y)=\gcd(y,x-y\left\lfloor\frac{y}{x}\right\rfloor)$

原因是 $x$ 和 $\left\lfloor\frac{y}{x}\right\rfloor$ 均为 $\gcd(x,y)$ 的倍数，所以限制是不变的。

拓展欧几里得则是在这个的基础上找出 $ax+by=\gcd(a,b)$ 的一组解。

$$
\begin{gather*}
ax_1+by_1=\gcd(a,b)=\gcd(b,a\bmod b)=bx_2+(a\bmod b)y_2=bx_2+(a-b\left\lfloor\frac{a}{b}\right\rfloor)y_2 \\
ax_1+by_1=ay_2+b(x_2-\left\lfloor\frac{a}{b}\right\rfloor y_2) \\
\begin{cases}
x_1=y_2 \\
y_1=x_2-\left\lfloor\frac{a}{b}\right\rfloor y_2
\end{cases}
\end{gather*}
$$

求 $\gcd$ 时维护一下即可。

### 线性同余方程

求 $ax\equiv b \pmod m$ 即 $ax\bmod m=b$ 的一组解。

则有 $ax-km=b$，根据**裴蜀定理**，首先 $\gcd(a,m)|b$

然后先求出 $ax-km=\gcd(a,m)$ 的一组解，将其乘上 $\frac{b}{\gcd(a,m)}$ 即可得到解。

假设找到了 $ax+by=c$，那么有 $a(x+\frac{bk}{g})+b(y-\frac{ak}{g})=c\ \ \ (\gcd(a,b)=g)$

### 中国剩余定理

求解以下形式的线性同余方程组。

$$
\begin{cases}
x\bmod m_1=a_1 \\
x\bmod m_2=a_2 \\
\cdots \\
x\bmod m_n=a_n \\
\end{cases}
$$

其中 $m_1,m_2,\cdots,m_n$ 两两互质。

首先计算 $M=\prod m$

对于每个方程分别计算其它的模数积 $v_i=\frac{M}{m_i}$

计算 $v_i$ 在模 $m_i$ 下的逆元 $v_i^{-1}$（拓欧）

最后答案即为 $\sum a_iv_iv_i^{-1}\bmod M$

原因是对于 $m_i$，其它项由于 $v_j\bmod m_i=0$ 被消掉，而变成 $0$，当前这项的 $v_iv_i^{-1}=1$，所以最后只剩下了 $a_i$。

正在渲染内容...