【创作赢红包】求最大公因数与最小公倍数

客官°小女子只卖身不卖艺 2024-03-24 12:37 48阅读 0赞

### 什么是最小公因数 ###

最大公约数（Greatest Common Divisor）指两个或多个整数共有约数中最大的一个。也称最大公因数、最大公因子，a， b的最大公约数记为（a，b），同样的，a，b，c的最大 公约数记为（a，b，c），多个 整数的最大公约数也有同样的记号。求最大公约数有多种 方法，常见的有 质因数分解法、 短除法、 辗转相除法、 更相减损法。

#### 辗转相除法求最小公因数 ####

用(a，b)表示a和b的最大公因数：有结论(a，b)=(a，ka+b)，其中a、b、k都为自然数。

也就是说，两个数的最大公约数，将其中一个数加到另一个数上，得到的新数，其公约数不变，比如(4，6)=(4+6，6)=(4，6+2×4)=2.

要证明这个原理很容易：如果p是a和ka+b的公约数，p整除a，也能整除ka+b.那么就必定要整除b，所以p又是a和b的公约数，从而证明他们的最大公约数也是相等的.

基于上面的原理，就能实现我们的迭代相减法：(78，14)=(64，14)=(50，14)=(36，14)=(22，14)=(8，14)=(8，6)=(2，6)=(2，4)=(2，2)=(0，2)=2

基本上思路就是大数减去小数，一直减到能算出来为止，在作为练习的时候，往往进行到某一步就已经可以看出得值.

迭代相减法简单，不过步数比较多，实际上我们可以看到，在上面的过程中，由(78，14)到(8，14)完全可以一步到位，因为(78，14)=(14×5+8，14)=(8，14)，由此就诞生出我们的辗转相除法.

即：(a， b) = (a % b， b) = （b, a %b）

相当于每一步都把数字进行缩小，等式右边就是每一步对应的缩小结果。

对（a， b）连续使用辗转相除，直到小括号内右边数字为0，小括号内左边的数就是两数最大公约数。

#### 代码实现 ####

import java.util.*;
    public class Main{
        
        public static void main(String[] args){
        
            Scanner scan = new Scanner(System.in);
            int T = scan.nextInt();
            while(T --> 0){
        
                int a = scan.nextInt();
                int b = scan.nextInt();
                System.out.println(gcd(a,b));
            }
        }
        public static int gcd(int a,int b){
        
            return b!=0 ? gcd(b,a%b):a;
        }
    }

### 最小公倍数 ###

与最大公因数类似，只是把约数换成了倍数

#### 求最小公倍数 ####

十分简单，我们只需知道简单的一个定理，两个数的最小公倍数就等于两个数的乘积/他们的最大公因数

即 `a * b / gcd(a,b)`；

#### 例题 ####

小张是软件项目经理，他带领 33 个开发组。

工期紧，今天都在加班呢。

为鼓舞士气，小张打算给每个组发一袋核桃（据传言能补脑）。

他的要求是：

1.  各组的核桃数量必须相同
2.  各组内必须能平分核桃（当然是不能打碎的）
3.  尽量提供满足 1,21,2 条件的最小数量（节约闹革命嘛）

##### 输入格式 #####

包含 a,b,c 三个正整数，表示每个组正在加班的人数。

##### 输出格式 #####

一个正整数，表示每袋核桃的数量。

##### 数据范围 #####

0<a,b,c<30

##### 输入样例1： #####

2 4 5

##### 输出样例1： #####

##### 输入样例2： #####

3 1 1

##### 输出样例2： #####

#### 代码实现 ####

import java.util.*;
    public class Main{
        
        public static void main(String[] args){
        
            Scanner scan = new Scanner(System.in);
            int a = scan.nextInt();
            int b = scan.nextInt();
            int c = scan.nextInt();
            int a_b = a * b / gcd(a,b);
            int a_b_c =a_b * c / gcd(a_b,c);
            System.out.println(a_b_c);
        }
        public static int gcd(int a,int b){
        
            return b != 0 ? gcd(b , a % b) : a;
        }
    }