DAY-1 | 求两个正整数的最大公约数与最小公倍数之和——辗转相除法

这里是C语言刷题日志，整理了博主本人平时做练习遇到的问题以及相关的总结。

---

目录

一、题干

二、题解

1. 辗转相除法 

  2. 试除法

三、总结

1. 辗转相除法求最大公约数和最小公倍数

2. 迭乘法求最小公倍数

---

一、题干

牛客网链接

BC115 小乐乐与欧几里得https://www.nowcoder.com/practice/da13e0cf321e4df9acd0fdf0a433cbb0?tpId=107&&tqId=33396&rp=1&ru=/ta/beginner-programmers&qru=/ta/beginner-programmers/question-ranking

 

二、题解

1. 辗转相除法 

//辗转相除法求最大公约数、最小公倍数

int main()
{
    long long n = 0;
    long long m = 0;
    //输入两个数
    scanf("%lld %lld", &n, &m); 
 
    /*因为求最大公约数和最小公倍数都需要用到m、n，且辗转相除的过程会改编n、m的值，
    故再创建两个变量n2、m2，把m和n的值拷贝一份再做运算*/
    long long m2 = m;
    long long n2 = n;

    long long r = 0;

    //最大公约数
    while (r = n2 % m2)
    {
        n2 = m2;
        m2 = r;    //注意：m2才是所求的最大公约数的结果，而不是r
    }

    //最小公倍数 == m*n/最大公约数
    printf("%lld", m * n / m2 + m2);    //直接求最大公约数和最小公倍数的和

    return 0;
}

优点：效率更高；不用比较m和n的大小即可计算。

---

  2. 试除法

int main()
{
    int n = 0;
    int m = 0;
    scanf("%d %d", &n ,&m);
    int max = (n>m?m:n);//假设最大公约数，是n和m的较小值
    while(1)
    {
        if(n%max==0 && m%max==0)
        {
            break;
        }
        max--;
    }
    int min = (n>m?n:m);//假设最小公倍数，是n和m的较大值
    while(1)
    {
        if(min%n==0 && min%m==0)
            break;
        min++;
    }
    printf("%d\n", max+min);

    return 0;
}

三、总结

1. 辗转相除法求最大公约数和最小公倍数

//辗转相除法求最大公约数和最小公倍数

int main(){

    int m,n;
    int tmp = 0;
    scanf("%d %d",m,n);

    int m2 = m;
    int n2 = n;

    while(tmp = m % n){
        m = n;
        n = tmp;
    }
    
    printf("%d",n);    //注意，最后的n才是要求的最大公约数
    
    printf("%d",(m2*m1)/n);
}

 最小公倍数 == 两数相乘再除以其最大公约数。

2. 迭乘法求最小公倍数

int main(){
    int a=0;
    int b=0;
    cin >> a >> b;
  
    int i = 1;
    while((a*b) % b != 0){
        i++;
    }

    cout << i*a;    //最小公倍数：i*a

    return 0;
}