This page looks best with JavaScript enabled

欧几里得算法学习笔记

 ·  ✏️ About  1822 words  ·  ☕ 4 mins read · 👀... views

关于最大公约数的欧几里得算法及其拓展。

前置知识

整除

定义

对于 $a,b \in \mathbb Z$ ,若存在 $q\in \mathbb Z$ 使 $a = qb$ 成立,则称 $b$ 整除 $a$$a$ 被 $b$ 整除,记作 $b\mid a$ 。
我们称 $b$ 是 $a$ 的因数, $a$ 是 $b$ 的倍数
否则,我们称 $b$ 不整除 $a$$a$ 不被 $b$ 整除,记作 $b\nmid a$ 。

性质

  1. $c\mid b,b\mid a \implies c \mid a$
  2. $x,y \in \mathbb Z, m|a,m|b \implies m|(ax+by)$

带余数除法

定义

若 $a,b\in \mathbb Z,b>0$ ,则存在唯一的 $q,r\in \mathbb Z$ ,使
$$
a = bq+r,0\leq r < b
$$
这里的 $q$ 称作不完全商, $r$ 称为余数。

取整

定义

$\lfloor x \rfloor$ 和 $\lceil x \rceil$ 分别代表向下和向上取整。

性质

  1. 在带余除法中,$q = \lfloor \frac{a}{b} \rfloor$.
  2. 若$n\in \mathbb Z$:$\lfloor x + n \rfloor = \lfloor x \rfloor + n$
  3. $\lceil x \rceil = − \lfloor −x \rfloor , − \lfloor x\rfloor = − \lceil −x \rceil$
  4. $\lceil \frac{n}{m} \rceil = \lfloor \frac{n+m-1}{m} \rfloor$
  5. $round(x) = \lfloor x+0.5\rfloor$
  6. $\lfloor\frac{\lfloor x \rfloor}{n}\rfloor = \lfloor \frac{x}{n}\rfloor$
  7. $\lfloor\frac{n}{\lfloor x \rfloor}\rfloor \neq \lfloor \frac{n}{x}\rfloor$
  8. $\lfloor \sqrt{x}\rfloor = \lfloor \sqrt{\lfloor x \rfloor} \rfloor$
  9. $\lfloor \frac{n}{ab} \rfloor = \lfloor \frac{\lfloor \frac{n}{a} \rfloor }{b} \rfloor$

最大公约数$\gcd$(greatest common divisor

定义

最大公约数,即给定两个整数 $a,b$ ,求最大的正整数 $w$,满足 $w$ 整除 $a$ 且 $w$ 整除 $b$ ( $w|a$ 且 $w|b$ ).记作 $\gcd(a,b) = w$ .

定义$gcd(0,0) = 0$。

一些性质

  • $gcd(a,0) = |a|$
  • $gcd(a,ka) = |a|,,k \in \mathbb Z$
  • $gcd(a,b) = gcd(b,a)$
  • $gcd(a,b) = gcd(a,-b)$
  • $gcd(a,gcd(b,c)) = gcd(gcd(a,b),c)$
  • 在 $(0,0)$ 到 $(a,b)$( $a,b \in \mathbb Z$ )的线段上,有 $gcd(a,b)+1$ 个整点(包括两端点)

求法

辗转相除法。

其本质上是一个递归算法,通过不断递归的方式计算这两个数的最大公约数。

过程:$gcd(a,b) = gcd(b,a \bmod b)$
边界:$gcd(a,0) = a$

证明

(有限性)
令 $k$ 表示我们计算的步骤数(从 $0$ 开始计数)。

每一步的输入是都是前两次计算的非负余数 $r_{k−1}$ 和 $r_{k−2}$ 。

因为余数肯定小于除数,所以 $r_{k−1}$ 小于 $r_{k−2}$ 。在第 $k$ 步中,算法计算出满足以下等式的商 $q_k$ 和余数 $r_k$ :

$$
r_{k−2} = q_{k} \times r_{k−1} + r_k,; \text{其中}0\leq r_k<r_{k-1}
$$

此时,$r_{k-1}$ 和 $r_k$ 就是下一次递归的输入。

如果把所有式子都列出来,就会是这个样子:

$$
\begin{aligned}{}
a =& q_0 \times b + r_0\
b =& q_1 \times r_0 + r_1\
r_0 =& q_2 \times r_1 + r_2\
r_1 =& q_3 \times r_2 + r_3\
…\
r_{n-2} =& q_n \times r_{n-1} + r_n\
\end{aligned}
$$

这里的 $a,b$ 的大小在第一次除法的时候就会调节,所以不必关心,不妨设 $a>b$ 。

注意到 $a > b > r_1 > r_2 > r_3 > r_4… > r_n >=0$ ,所以一定能在 $n$ 次递归过后使得递归到边界情形,即 $r_n = 0$ 。

此时 $r_{n-1}$ 就是我们求得的 $\gcd(a,b)$ 。

(正确性)
设 $\gcd(a,b) = g$ ,我们需要证明 $r_{n-1} = g$ 。

第一步:
因为 $r_n = 0$ ,又 $r_{n-2} = q_n \times r_{n-1} + r_n$ ,所以 $r_{n-2}$ 是 $r_{n-1}$ 的整数倍。 $r_{n-3}$ 由整数倍的 $r_{n-2}$ 和一个 $r_{n-1}$ 构成,所以 $r_{n-3}$ 是 $r_{n-1}$ 的整数倍。同理可得 $a,b$ 都是 $r_{n-1}$ 的整数倍。

所以 $r_{n-1}$ 就是 $a,b$ 的公因数,又 $g$ 是 $a,b$ 的最大公因数,所以 $g \geq r_{n-1}$ 。

第二步:
因为 $g = gcd(a,b)$ ,令 $a = mg,b = ng$ ,其中 $n,m$ 均为自然数。

因为 $a = q_0 \times b + r_0$ ,所以 $r_0 = (m - q_0 \times n)g$ ,即 $g$ 也为 $r_0$ 的因数。同理下去就可以得到 $g$ 整除 $r_0,r_1,r_2,…,r_{n-1}$ 。所以 $g \leq r_{n-1}$ 。

综上可得: $g = r_{n-1}$ 。

所以,辗转相除法的正确性可以如上证明。

实现

直接按照思路实现即可:

1
2
3
4
template<typename T>
T gcd(T a,T b){
    return b==0?a:gcd(b,a%b);
}

时间复杂度 $O(\log n)$ ,证明参见 Lamé定理

扩展欧几里得算法(exgcd

定义

扩展欧几里得算法,即给定两个正整数 $a,b$ ,我们可以在运用欧几里得算法求出 $gcd(a,b)$ 的同时,我们也可以求出 $ax+by = gcd(a,b)$ 的一组整数解 $x_0,y_0$ 。

其方程所有解为:

$$
\left{
\begin{aligned}{}
x = x_0+\frac{b}{gcd(a,b)}\
y = y_0-\frac{a}{gcd(a,b)}
\end{aligned}
\right.
$$

一个结论: $ax+by$ 的最小正值 $ax_0+by_0 = gcd(a,b)$

求法&证明

现在我们要求 $ax+by = gcd(a,b)$ 的一组整数解。

考虑到欧几里得算法的公式 $gcd(a,b) = gcd(b,a \bmod b)$

若有一组 $x’,y'$ 使得 $bx'+ (a \bmod b) y’ = gcd(b,a \bmod b)$

这个时候我们注意到可以令 $ax+by = bx'+ (a \bmod b) y'$ .

因为 $a \bmod b = a-\lfloor\frac{a}{b}\rfloor b$ ,所以上式可以化为 $ax+by = bx'+(a-\lfloor\frac{a}{b}\rfloor b)y'$ .

这个时候我们已经知道 $x’,y’,a,b$ ,未知数有 $x,y$ 。所以这个方程事实上是要么无解要么无数个解。而我们这里只需要一个特解,所以我们把上式整理成为关于 $a,b$ 的恒成立式子,就可以通过 $x’,y'$ 解出 $x,y$ 。整理得
$$
a(x)+b(y) = a(y’) + b(x’-\lfloor\frac{a}{b}\rfloor y’)
$$

可以得到一组特解:$x = y’,y = x’-\lfloor\frac{a}{b}\rfloor y'$。所以我们就可以递归求解。

精简版过程:
令 $\text{exgcd}(a,b)$ 为 $ax+by = gcd(a,b)$ 的解 $(x,y)$ 。

对于 $\text{exgcd}(a,b)$ ,递归求得 $exgcd(b,a \bmod b)$ 的解 $(x’,y’)$ 。
则 $exgcd(a,b) = (y’, x’-\lfloor\frac{a}{b}\rfloor y’)$ 。

边界情况为 $b = 0$ 时,此时方程即为 $ax + 0y = a$ ,返回 $(1,0)$ 即可。

代码

1
2
3
4
5
6
7
template<typename T>
T exgcd(T a,T b,T &x,T &y){
    if (!b){x=1,y=0;return a;}
    T d = exgcd(b,a%b,y,x);
    y-=(a/b)*x;
    return d;
}

应用

  • $ax+by=c$ 不定方程
    可以证明,仅当 $gcd(a,b)|c$ 时,该方程有整数解。
    先用扩展欧几里得算法求出 $ax+by = gcd(a,b)$ 的一组整数解,然后将得到的解均乘上 $\frac{c}{gcd(a,b)}$ 即可。

  • $ax \equiv c \pmod b$ 一次同余方程
    转化为 $ax + by = c$ 的一个问题,可以得出有解条件当且仅当 $gcd(a,b)|c$ 。运用上面的方法求解即可。

  • 乘法逆元,将 $ax \equiv 1 \pmod p$ 转化成 $ax + py = 1$ 解不定方程即可。

类欧几里得算法

一种用于求解形似
$$
\sum_{i = 0}^n{\lfloor\frac{ai+b}{c}\rfloor}
$$
的问题的算法。

过程

首先对 $a,b$ 关于 $c$ 取模,使得 $a,b<c$ 。
令 $m = \lfloor\frac{an+b}{c}\rfloor$ 。

此时有:
$$
\sum_{i = 0}^n{\lfloor\frac{ai+b}{c}\rfloor} \
= \sum_{j = 0}^{m-1}\sum_{i = 0}^n[j < \lfloor\frac{ai+b}{c}\rfloor]\
= \sum_{j = 0}^{m-1}\sum_{i = 0}^n[i > \lfloor\frac{cj+c-b-1}{a}\rfloor]\
= \sum_{j = 0}^{m-1}n - \lfloor\frac{cj+c-b-1}{a}\rfloor\
= nm - \sum_{j = 0}^{m-1}\lfloor\frac{cj+c-b-1}{a}\rfloor
$$

注意到这个时候 $a,b$ 都是对 $c$ 取模的,所以这个东西很像欧几里得算法,时间复杂度大约也是 $O(\log n)$ .

扩展

$$
\sum_{i = 0}^n{{\lfloor\frac{ai+b}{c}\rfloor}^2}\
\sum_{i = 0}^n{i{\lfloor\frac{ai+b}{c}\rfloor}}
$$


cqqqwq
WRITTEN BY
cqqqwq
A student in Computer Science.

评论: