下文中
(
a
,
b
)
(a, b)
(a,b) 可能表示
a
a
a 和
b
b
b 的最大公约数，同理
[
a
,
b
]
[a, b]
[a,b] 可能表示
a
a
a 和
b
b
b 的最小公倍数。
最大公约数
更相减损术（《九章算术》）
内容
?
a
,
b
∈
N
,
a
≥
b
:
(
a
,
b
)
=
(
a
,
a
?
b
)
=
(
b
,
a
?
b
)
?
?
?
①
\forall a, b \in \mathbb{N}, a \geq b: (a, b) = (a, a - b) = (b, a - b) \ \cdots \cdots①
?a,b∈N,a≥b:(a,b)=(a,a?b)=(b,a?b)???①
?
a
,
b
∈
N
:
(
2
a
,
2
b
)
=
2
×
(
a
,
b
)
?
?
?
②
\forall a, b \in \mathbb{N}: (2a, 2b) = 2 \times (a, b) \ \cdots \cdots ②
?a,b∈N:(2a,2b)=2×(a,b)???②
证明
①
设集合
S
=
{
s
∈
N
∣
s
∣
a
,
?
s
∣
b
}
S = \{ s \in \mathbb{N} \mid s | a,\ s | b \}
S={s∈N∣s∣a,?s∣b}，
则
?
s
∈
N
?
:
s
∣
a
,
?
s
∣
b
??
?
??
s
∣
(
a
?
b
)
\forall s \in \mathbb{N}^*: s | a, \ s | b \implies s | (a - b)
?s∈N?:s∣a,?s∣b?s∣(a?b)。
设集合
T
=
{
t
∈
N
∣
t
∣
a
,
?
t
∣
(
a
?
b
)
}
T = \{ t \in \mathbb{N} \mid t | a,\ t | (a - b) \}
T={t∈N∣t∣a,?t∣(a?b)}。
∴
S
=
T
\therefore S = T
∴S=T。
∴
max
?
{
S
}
=
max
?
{
T
}
\therefore \max\{S\} = \max\{T\}
∴max{S}=max{T}。
∴
(
a
,
b
)
=
(
a
,
a
?
b
)
\therefore (a, b) = (a, a - b)
∴(a,b)=(a,a?b)。
同理可得
(
a
,
b
)
=
(
b
,
a
?
b
)
(a, b) = (b, a - b)
(a,b)=(b,a?b)。
∴
(
a
,
b
)
=
(
a
,
a
?
b
)
=
(
b
,
a
?
b
)
\therefore (a, b) = (a, a - b) = (b, a - b)
∴(a,b)=(a,a?b)=(b,a?b)。
②
显然。
代码模板
template <typename uint_t>
uint_t gcd(uint_t a, uint_t b)
{
while (a && b && a ^ b)
{
if (a > b)
{
a -= b;
}
else
{
b -= a;
}
}
return (a ?: b);
}
template <typename uint_t>
uint_t gcd(uint_t a, uint_t b)
{
return ((a && b && a ^ b) ? ((a > b) ? gcd(a - b, b) : gcd(a, b - a)) : a);
}
时间复杂度
且让我引用一段百度百科。
辗转相除法也可以用来求两个数的最大公约数。
更相减损术和辗转相除法的主要区别在于前者所使用的运算是“减”，后者是“除”。从算法思想上看，两者并没有本质上的区别，但是在计算过程中，如果遇到一个数很大，另一个数比较小的情况，可能要进行很多次减法才能达到一次除法的效果，从而使得算法的时间复杂度退化为
Θ
(
max
?
{
a
,
b
}
)
\Theta(\max\{a, b\})
Θ(max{a,b})。相比之下，辗转相除法的时间复杂度稳定于
Θ
(
log
?
(
max
?
{
a
,
b
}
)
)
\Theta(\log(\max\{a, b\}))
Θ(log(max{a,b}))。
用途
- 求整数，尤其高精度整数的最大公约数（不需要实现高精度取模运算）；
欧几里德算法：辗转相除法
内容
?
a
∈
N
,
?
b
∈
N
?
:
(
a
,
b
)
=
(
b
,
a
?
m
o
d
?
b
)
\forall a \in \mathbb{N},\ b \in \mathbb{N}^*: (a, b) = (b, a\ {\rm mod}\ b)
?a∈N,?b∈N?:(a,b)=(b,a?mod?b)
证明
①
a
<
b
a < b
a<b：显然。
②
a
≥
b
a \geq b
a≥b：
设
k
=
?
a
b
?
，
m
=
a
?
m
o
d
?
b
k = \lfloor \frac{a}{b} \rfloor，m = a\ {\rm mod}\ b
k=?ba??，m=a?mod?b，即
a
=
k
×
b
+
m
?
(
k
∈
N
,
m
∈
N
∩
[
0
,
b
)
)
a = k \times b + m\ (k \in \mathbb{N}, m \in \mathbb{N} \cap [0, b))
a=k×b+m?(k∈N,m∈N∩[0,b))
∵
?
d
∈
N
?
,
d
∣
a
,
d
∣
b
:
d
∣
(
k
×
b
)
。
\because \forall d \in \mathbb{N}^*, d | a, d | b: d | (k \times b)。
∵?d∈N?,d∣a,d∣b:d∣(k×b)。
∴
d
∣
(
a
?
k
×
b
)
\therefore d | (a - k \times b)
∴d∣(a?k×b) 即
d
∣
m
d | m
d∣m。
设集合
S
=
{
s
∈
N
?
∣
s
∣
a
,
?
s
∣
b
}
S = \{ s \in \mathbb{N}^* \mid s|a,\ s|b \}
S={s∈N?∣s∣a,?s∣b}，集合
T
=
{
t
∈
N
?
∣
t
∣
b
,
?
t
∣
(
a
?
m
o
d
?
b
)
}
T = \{ t \in \mathbb{N}^* \mid t | b,\ t | (a\ {\rm mod}\ b) \}
T={t∈N?∣t∣b,?t∣(a?mod?b)}，
则
S
=
T
S = T
S=T。
∴
(
a
,
b
)
=
max
?
{
S
}
=
max
?
{
T
}
=
(
b
,
a
?
m
o
d
?
b
)
\therefore (a, b) = \max\{S\} = \max\{T\} = (b, a\ {\rm mod}\ b)
∴(a,b)=max{S}=max{T}=(b,a?mod?b)。
代码模板
template <typename uint_t>
uint_t gcd(uint_t a, uint_t b)
{
uint_t t;
while (b)
{
t = b;
b = a % b;
a = t;
}
return a;
}
template <typename uint_t>
uint_t gcd(uint_t a, uint_t b)
{
return (b ? gcd(b, a % b) : a);
}
时间复杂度：
Θ
(
log
?
2
(
max
?
{
a
,
b
}
)
)
\Theta(\log_2(\max\{a, b\}))
Θ(log2?(max{a,b}))
最小公倍数
算法原理
[
a
,
b
]
=
a
÷
(
a
,
b
)
?
b
[a, b] = a \div (a, b) * b
[a,b]=a÷(a,b)?b
证明
由最大公约数和最小公倍数的定义可得
[
a
,
b
]
=
a
÷
(
a
,
b
)
?
b
[a, b] = a \div (a, b) * b
[a,b]=a÷(a,b)?b
代码模板
template <typename uint_t>
uint_t lcm(uint_t a, uint_t b)
{
return (a / gcd(a, b) * b);
}
注意事项
建议不要写成a * b / gcd(a, b)的形式，以免a * b的结果溢出造成结果错误。
|