【朝夕的ACM笔记】数论-欧几里德算法相关
本文内容：欧几里德算法、最小公倍数、拓展欧几里德算法。
欧几里德算法（Euclidean Algorithm）又叫辗转相除法，用于求解两个非负整数的最大公约数，由古希腊数学家欧几里德提出。在竞赛中常有出现。该算法主要依赖于下面的定理：设两个非负整数a和b，其最大公约数为d，则d为正整数，a = dm，b = dn，其中m和n为整数，且d为a和b的公约数。证明了欧几里德算法的正确性。
代码阐释：使用递归实现算法，直到余数为0时，除数即为最大公约数。无需判断a和b的大小，递归过程中会自动交换位置。求多个数的最大公约数时，先求出其中两数的最大公约数，然后将结果与其余数依次进行操作即可。
最小公倍数：设非负整数a和b，其最小公倍数为lcm。证明了若a和b互质，则lcm等于ab。洛谷：P1029题可以运用此公式优化程序。
拓展欧几里德算法：裴蜀定理表明，对于非负整数a和b，存在整数x和y使得ax + by = gcd(a, b)。证明了若存在整数x和y使得ax + by = gcd(a, b)，则a和b互质。代码实现通过递归求解一组可行解。若要求解一组可行解，只需求解gcd(a, b)，然后将求得的x和y分别乘以gcd(a, b)即可。若结果不是gcd(a, b)的倍数，则无解。
例题：同余方程洛谷P1082，求关于x的同余方程的最小正整数解，需要通过拓展欧几里德算法求解逆元。有理数取余洛谷P2613，给定有理数，求其取余值，通过拓展欧几里德算法求解。【模板】裴蜀定理洛谷P4549，多个元素最大公因数的拓展应用。【模板】二元一次不定方程洛谷P5656，利用裴蜀定理判定是否存在正整数解，并求其最大最小整数解。Line CF7C题则需关注特定的算法应用。
欧几里德算法（Euclidean Algorithm）又叫辗转相除法，用于求解两个非负整数的最大公约数，由古希腊数学家欧几里德提出。在竞赛中常有出现。该算法主要依赖于下面的定理：设两个非负整数a和b，其最大公约数为d，则d为正整数，a = dm，b = dn，其中m和n为整数，且d为a和b的公约数。证明了欧几里德算法的正确性。
代码阐释：使用递归实现算法，直到余数为0时，除数即为最大公约数。无需判断a和b的大小，递归过程中会自动交换位置。求多个数的最大公约数时，先求出其中两数的最大公约数，然后将结果与其余数依次进行操作即可。
最小公倍数：设非负整数a和b，其最小公倍数为lcm。证明了若a和b互质，则lcm等于ab。洛谷：P1029题可以运用此公式优化程序。
拓展欧几里德算法：裴蜀定理表明，对于非负整数a和b，存在整数x和y使得ax + by = gcd(a, b)。证明了若存在整数x和y使得ax + by = gcd(a, b)，则a和b互质。代码实现通过递归求解一组可行解。若要求解一组可行解，只需求解gcd(a, b)，然后将求得的x和y分别乘以gcd(a, b)即可。若结果不是gcd(a, b)的倍数，则无解。
例题：同余方程洛谷P1082，求关于x的同余方程的最小正整数解，需要通过拓展欧几里德算法求解逆元。有理数取余洛谷P2613，给定有理数，求其取余值，通过拓展欧几里德算法求解。【模板】裴蜀定理洛谷P4549，多个元素最大公因数的拓展应用。【模板】二元一次不定方程洛谷P5656，利用裴蜀定理判定是否存在正整数解，并求其最大最小整数解。Line CF7C题则需关注特定的算法应用。