数论学习

发表于 | 更新于 | 阅读次数：

这里会简单记录我学习的基础数论。这里的证明可能都不大严谨，仅供参考。

欧几里得算法

如果我们想要求 $gcd(a,b)$ ，最简单的方式便是枚举，但这太慢了。

于是我们有了我们的辗转相除法，也就是欧几里得算法，它可以在 $O(log(a+b))$ 的复杂度内求出 $gcd(a,b)$ 。

$$\forall a,b \in \mathbb{N}, b \not = 0,\quad gcd(a,b) = gcd(b,a\bmod b)$$

证明

$a < b$ 时

$gcd(b,a \bmod b)=gcd(b,a)=gcd(a,b)$

$a \geq b$ 时

设 $r=a\bmod b$ ，$d$ 为 $a,\,b$ 任意一个公约数。

则 $a=kb+r,\;a\equiv b\equiv 0 \pmod{d}$

$\therefore a-kb\equiv r \equiv 0 \pmod{d}$

$\therefore d\,|\,b,\,d\,|\,a\bmod b$

所以 $a,b$ 和 $b, a \bmod b$ 的公约数集合是相同的，它们的最大公约数必然也相等。

$\therefore gcd(a,b)=gcd(b, a \bmod b)$

要注意边界：$b = 0$ 时，$gcd(a,b) = a$

代码

1
2
3
4
int gcd(int a, int b)
{
	return !b ? a : gcd(b, a % b);
}

拓展欧几里得

拓展欧几里得用于在已知自然数 $a,b$ ，求解 $ax+by=gcd(a,b)$ 的 $(x,y)$ 的整数解时。

$ax+by=gcd(a,b)$

$=gcd(b,a\bmod b)$

$\Rightarrow bx+(a\bmod b)\,y$

$=bx+(a-\lfloor\dfrac{a}{b}\rfloor\,b)\,y$

$=ay+b\,(x-\lfloor\dfrac{a}{b}\rfloor\,y)$

所以 $x$ 变成了 $y$ ， $y$ 变成了 $x-\lfloor\dfrac{a}{b}\rfloor\,y$

于是我们可以愉快地递归求解。这里也需要注意边界： $b=0$ 时，$a=1,\,ax+by=1$ ，因此 $x=1,y=0$ 。

代码

1
2
3
4
5
6
7
void exgcd(int a, int b, int &x, int &y)
{
	if (!b)
		x = 1, y = 0;
	else
		exgcd(b, a % b, y, x), y -= a / b * x;
}

乘法逆元

当我们想要求形如 $\dfrac{a}{b} \bmod p$ 的值的时候，就需要用到乘法逆元。

逆元定义

若 $a \times x \equiv 1 \pmod{b}$ ，且 $a \perp b$ ，则我们定义 $x$ 为 $a$ 的逆元

所以对于 $\dfrac{a}{b} \bmod p$ ，我们就可以求出 $b$ 在 $\bmod p$ 意义下的逆元 $x$ ，原分数的值便可以表示为 $a \times x \bmod{p}$

求解逆元的方法

拓展欧几里得

这个我们刚刚讲过。这种做法就是将 $a \times x \equiv 1 \pmod {b}$ 转换为 $a \times x + b \times y = 1 $ ，然后求解。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void exgcd(int a, int b, int &x, int &y)
{
	if (!b)
		x = 1, y = 0;
	else
		exgcd(b, a % b, y, x), y -= a / b * x;
}

int main()
{
	int x, y;
	exgcd(a, p, x, y)
	x = (x + p) % p; // x 就是 a 在 mod p 意义下的逆元
}

快速幂

费马小定理：若 $p$ 为质数， $a$ 为正整数， 且 $a \perp p$ ，则有 $a^{p-1} \equiv 1 \pmod{p}$

所以我们可以进行推导：

$a \times x \equiv 1 \equiv a^{p-1} \pmod{p}$

$x \equiv a^{p-2} \pmod{p}$

因此我们可以用快速幂求出 $a^{p-2} \pmod{p}$ 的值，这个数就是 $a$ 的逆元了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int qpow(int a, int b, int p)
{
	int res = 1;
	while (b)
	{
		if (b & 1)
			res = res * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return res;
}

int main()
{
	int x = qpow(a, p - 2, p);
}

线性递推

这个可以用来求一连串数对于$\bmod p$ 的逆元。

首先我们知道 $1^{-1} \equiv 1 \pmod{p}$

设 $k = \lfloor\dfrac{p}{i}\rfloor,\,r = p \bmod{i}$

$k \times i + r \equiv 0 \pmod{p}$

两边同时乘上 $i^{-1},\,r^{-1}$

$k \times r^{-1} + i^{-1} \equiv 0 \pmod{p}$

$i^{-1} \equiv -k \times r^{-1} \pmod{p}$

$i^{-1} \equiv -\lfloor\dfrac{p}{i}\rfloor \times (p \bmod{i})^{-1} \pmod{p}$

于是我们可以从前推出当前的逆元。

代码

1
2
3
inv[1] = 1;
for (int i = 2; i < p; i ++)
	inv[i] = (p - p / i) * inv[p % i] % p;

阶乘逆元

这个一般在求组合数的值得时候用到。比较简单，就一笔带过了。

一般求 $1\sim n$ 的阶乘逆元有两种方法：

  • 先求出 $1\sim n$ 每个数的逆元，然后正推： $(i!)^{-1} \equiv (i - 1)! ^ {-1} \times i ^ {-1} \pmod{p}$

代码

1
2
3
4
5
inv_fac[1] = 1;
for (int i = 2; i <= n; i ++)
	inv_fac[i] = (p - p / i) * inv_fac[p % i] % p;
for (int i = 2; i <= n; i ++)
	inv_fac[i] = inv_fac[i] * inv_fac[i - 1] % p;
  • 先求出 $n$ 的阶乘逆元，然后倒推： $(i!)^{-1} \equiv (i + 1)! ^ {-1} \times (i + 1) \pmod{p}$

代码

1
2
3
inv_fac[n] = inv(fac[n]);
for (int i = n - 1; i >= 1; i --)
	inv_fac[i] = inv_fac[i + 1] * (i + 1) % p;

欧拉函数

$$\varphi(n) = \sum\limits_{i=1}^{n-1} [n \perp i]$$

通俗的来讲， $\varphi(n)$ 表示小于 $n$ 的正整数当中有多少个数与 $n$ 互质，特别的，我们规定 $\varphi (1)=1$

这里我们有一个欧拉函数的计算公式；

$$\varphi(n) = n \times \prod\limits_{p\,|\,n}(1-\dfrac{1}{p})$$

证明先咕一会儿，有时间再写。