文章汇总归纳整理于：算法竞赛学习之路[Java版]
这里不采用公式定理证明的方法进行讲解，算是讲解欧几里得算法(GCD, 辗转相除法)求解最大公约数的过程吧
以求 104 50 的最大公约数为例
欧几里得算法(GCD, 辗转相除法)求解过程讲解
- 求两个数 a b 的最大公约数，这个最大公约数只会出现在 1 到 两个数中较小的数 的这个范围内，即最大公约数∈[ 1, min(a, b) ]
- 因为两个数的最大公约数必须是两个数共同拥有的因子，所以这个最大公约数不能大于两个数中的其中任何一个数，即最大公约数 ≤ min(a, b)，又因为 1 是任何数的约数，所以最大公约数∈[ 1, min(a, b) ]
- 由于要求最大的公约数，且每个数本身都是自己的最大约数，所以在辗转相除法求解最大公约数的过程中，每次取 min(a, b) 作为本次两个数的约数进行试探
- 104 / 50 = 2 ······ 4
- 此时 104 / 50，除不尽，即应该缩小除数，两个数的最大公约数小于 50，由于 50 * 2 + 4 = 104，被除数减去余数剩余的部分 100 一定可以被 50 除尽，能把 50 除尽的数也一定可以将 100 除尽，而要求 104 的约数，则需要满足所求得的约数应当也能将余数 4 除尽，于是求 104 50 的最大公约数变为求 50 4 的最大公约数
- 根据上述的讲解，50 4 的最大公约数只可能出现在 [ 1, 4 ] 这个区间中，所以取除数为 4 进行试探，判断 4 是否可以成为 50 4 的最大公约数，如果可以，4 也是104 50 的最大公约数
- 50 / 4 = 12 ······ 2
- 由于结果存在余数，所以还需要缩小除数，即两个数的最大公约数小于 4，根据上述的讲解，接下来，最大公约数只可能出现在 [1, 2] 这个区间中，取除数为 2 进行试探
- 4 / 2 = 2
- 此时可以除尽，不存在余数，所以 2 为 4 2 的最大公约数，能将 4 除尽，且可以将 50 / 4 的余数除尽，所以 2 为 50 4 的最大公约数（50 = 4 * 12 + 2），能将 50 除尽，也能将 104 / 50 的余数除尽，所以 2 为 104 50 的最大公约数（104 = 50 * 2 + 4）
- 由此，可得 104 50 的最大公约数为 2
欧几里得算法(GCD, 辗转相除法)代码实现
以 P1888 三角函数 为例，进行欧几里得算法(GCD, 辗转相除法)的代码实现
// package GCD; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int a = sc.nextInt(); int b = sc.nextInt(); int c = sc.nextInt(); // 三个数 a b c 从小到大进行排列 if (a > b) { int t = a; a = b; b = t; } if (a > c) { int t = a; a = c; c = t; } if (b > c) { int t = b; b = c; c = t; } // 计算较小锐角的正弦值 // 较小锐角的正弦值 = 最小的边长 / 最大的边长 // 由于结果要约分，所以要求出两个数的最大公约数 int gcd = gcd(a, c); // 求出两个数的最大公约数 // 输出结果 System.out.println((a / gcd) + "/" + (c / gcd)); } static int gcd(int a, int b) { while (a % b != 0) { // 如果两数相除存在余数，继续进行辗转相除法 int remain = a % b; // 余数 a = b; // 原先的除数变为被除数 b = remain; // 余数变为除数 } // 最终最大公约数在除数的位置（退出循环的条件为两数相除余数为0） return b; // 返回最大公约数 } }
