介绍了不定方程、同余、欧拉函数、逆元、中国剩余定理的相关知识

不定方程

形如 $ax + by = c$，其中 $a$, $b$, $c$ 是已知数的方程被称为二元一次不定方程。它有解当且仅当 $gcd(a,b)mid c$

我们可以通过扩展欧几里得算法求不定方程：

1
2
3
4
5
6
7
8
9

void exgcd(int a, int b, int &x, int &y) {
  if (a {a638d642d867b568c1aede4e6cc48965ba83a47abef8f643eb9348429a71096e} b == 0) {
    x = 0;
    y = 1;
  } else {
    exgcd(b, a {a638d642d867b568c1aede4e6cc48965ba83a47abef8f643eb9348429a71096e} b, y, x);
    y -= a / b * x;
  }
}

同余

这是一个同余式：

$$a equiv b pmod p$$

同余式两侧可以加减乘但不能直接除

威尔逊定理

正整数 $p$ 是质数的充要条件为 $(p-1)!equiv-1pmod p$

欧拉函数

欧拉函数 $varphi(n)$ 表示小于 $n$ 的数中与 $n$ 互质的数的个数

特别地 $varphi(1)=1$

欧拉函数有：

• 积性 如果 $gcd(a,b)=1$，$varphi(a times b)=varphi(a)times varphi(b)$
• 欧拉反演 ???
• 对于质数 $p$，$varphi(p^k)=p^k-p^{k-1}$ (只有 $p$ , $2p$ 至 $p^{k-1}p$ 共 $p^{k-1}$ 个数与 $p^k$ 不互质)

你设 $n$ 的唯一分解式为 $n=p_1^{k_1} p_2^{k_2}ldots p_s^{k_s}$，则根据积性算出 $varphi(n)=Pi_{i=1}^s varphi(p_i^{k_i})$，而 $varphi(p_i^{k_i})$ 是可根据上面第三条推算出的

逆元

同余式可以加减乘但不能直接除，所以我们希望得到一个数 $x^{-1}$ 使得任何数除 $x$ 等价于乘 $x^{-1}$

$x$ 的逆元表示为 $x^{-1}$。逆元满足

$$xtimes x^{-1}equiv 1 pmod p$$

1. $x$ 在模 $p$ 同余下存在逆元当且仅当 $gcd(x,p)=1$

2. 在模 $p$ 同余下，$x$ 的逆元若存在则唯一

3. 一个数的逆元的逆元等于它本身

4. 在模质数 $p$ 同余下，$[1,p-1]$中所有整数的逆元互不相同

那怎么求呢

费马小定理

在模 $p$ 同余下，$x$ 的逆元为 $x^{p-2}$

线性求

$inv_i$ 表示 $i$ 的逆元

$$inv_i=-lfloor frac{p}{i} rfloor times inv_{p mod i} pmod p$$

1
2
3

inv[1] = 1;
for (int i = 2; i <= n; ++i) {
  inv[i] = (1ll * (p - (p / i)) * inv[p {a638d642d867b568c1aede4e6cc48965ba83a47abef8f643eb9348429a71096e} i]) {a638d642d867b568c1aede4e6cc48965ba83a47abef8f643eb9348429a71096e} p;

用exgcd

由于 $xtimes x^{-1}equiv 1 pmod p$ 它等价于 $xx^{-1}=kp+1leftrightarrow xx^{-1}+kp=1$ 其中 $x$、$p$ 是已知量，$x^{-1}$、$k$是未知量，带入exgcd exgcd(x,p,ans,y) 即可

中国剩余定理 CRT

$$quad left{ begin{matrix} x equiv a_1 pmod {m_1} \ x equiv a_2 pmod {m_2} \ vdots qquadqquadqquad \ x equiv a_n pmod {m_n} end{matrix} right.$$

保证 $m$ 中数互质

$t_i$ 是 $M_i$ 模下 $m_i$的逆元；$M=Pi m_i$；$M_i=M div m_i$

$$xequiv sum a_i t_i M_i pmod M$$

模板题：P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪。结合exgcd求逆元：

1
2
3
4
5

int inv(int a, int d) {
  int x, y;
  exgcd(a, d, x, y);
  return (d + x {a638d642d867b568c1aede4e6cc48965ba83a47abef8f643eb9348429a71096e} d) {a638d642d867b568c1aede4e6cc48965ba83a47abef8f643eb9348429a71096e} d;
}