无编辑摘要 |
小无编辑摘要 |
||
| （未显示1个用户的2个中间版本） | |||
| 第12行： | 第12行： | ||
*: 对于 a,b 的任意公约数d，因为 <math>d|a,d|q*b</math>，故 <math>d|(a-qb)</math>，即 <math>d|r</math>，因此d也是b,r的公约数，反之亦成立。 | *: 对于 a,b 的任意公约数d，因为 <math>d|a,d|q*b</math>，故 <math>d|(a-qb)</math>，即 <math>d|r</math>，因此d也是b,r的公约数，反之亦成立。 | ||
*: 故a,b的公约数集合与 <math>b,a \;\mathrm{mod}\; b</math> 的公约数集合相同。于是它们的最大公约数自然也相等。 | *: 故a,b的公约数集合与 <math>b,a \;\mathrm{mod}\; b</math> 的公约数集合相同。于是它们的最大公约数自然也相等。 | ||
证毕。 | |||
== 实现 == | == 实现 == | ||
| 第19行： | 第21行： | ||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
== 注释 == | |||
<syntaxhighlight lang="c" line> | |||
// 计算两个整数的最大公约数 | |||
int gcd(int a, int b) { | |||
// 如果b不为0，则递归调用gcd函数，参数为b和a除以b的余数 | |||
return b ? gcd(b, a % b) : a; | |||
} | |||
</syntaxhighlight> | |||
== 参考资料 == | |||
# 算法竞赛进阶指南，李煜东，143页 | |||
[[Category:数学]] | |||
2023年8月26日 (六) 15:53的最新版本
欧几里得算法又称辗转相除法，是求最大公约数的算法。
[math]\displaystyle{ \forall a,b, \in N,b\not = 0, gcd(a,b) = gcd(b, a \;\mathrm{mod}\; b) }[/math] [math]\displaystyle{ }[/math]
证明
- 若 [math]\displaystyle{ a \lt b }[/math]
- [math]\displaystyle{ gcd(b, a \;\mathrm{mod}\; b) = gcd(b, a) = gcd(a, b) }[/math] ，命题成立
- 若 [math]\displaystyle{ a \geq b }[/math]
- 不妨设 [math]\displaystyle{ a=q*b+r }[/math]，其中 [math]\displaystyle{ 0 \leq r \lt b }[/math]。显然[math]\displaystyle{ r=a \;\mathrm{mod}\; b }[/math]。
- 对于 a,b 的任意公约数d，因为 [math]\displaystyle{ d|a,d|q*b }[/math]，故 [math]\displaystyle{ d|(a-qb) }[/math]，即 [math]\displaystyle{ d|r }[/math]，因此d也是b,r的公约数，反之亦成立。
- 故a,b的公约数集合与 [math]\displaystyle{ b,a \;\mathrm{mod}\; b }[/math] 的公约数集合相同。于是它们的最大公约数自然也相等。
证毕。
实现
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
注释
// 计算两个整数的最大公约数
int gcd(int a, int b) {
// 如果b不为0，则递归调用gcd函数，参数为b和a除以b的余数
return b ? gcd(b, a % b) : a;
}
参考资料
- 算法竞赛进阶指南，李煜东，143页