题解 | #求最小公倍数#

求最小公倍数

http://www.nowcoder.com/practice/22948c2cad484e0291350abad86136c3

a、b的最大公倍数 = a * b / a、b的最大公约数
最大公约数用更相减损法来求,即让两个数相减,然后用差和减数的较大值和较小值更新被减数和减数,直到被减数和减数相等为止,此时被减数就是最大公约数。

#include <bits/stdc++.h>
using namespace std;

// 利用最大公倍数和最大公约数的关系
// 两个数的最大公倍数 = 两个数相乘 / 最大公约数
// 例:8和10的最大公约数==2,最大公倍数=8*10/2=40
// 求最大公约数的方法是辗转相减法,将两个数相减,然后取减数和差相减

int greatestcommondivisor(int a, int b) {
    // 求a和b的最大公约数Minus and minuend
    int minuend = max(a, b);  // 被减数
    int minus = min(a, b);  // 减数

    int difference = 0;
    while (minus != minuend) {
        difference = minuend - minus;
        minuend = max(minus, difference);
        minus = min(minus, difference);
    }
    return minus;
}

int main() {
    int a, b;
    while (cin >> a >> b) {
        int gcdivisor = greatestcommondivisor(a, b);  // 最大公约数
        cout << a * b / gcdivisor << endl;

    }
    return 0;
}

递归写法

#include <bits/stdc++.h>
using namespace std;

// 利用最大公倍数和最大公约数的关系
// 两个数的最大公倍数 = 两个数相乘 / 最大公约数
// 例:8和10的最大公约数==2,最大公倍数=8*10/2=40
// 求最大公约数的方法是辗转相减法,将两个数相减,然后取减数和差相减


int func(int minuend, int minus) {
    if (minuend == minus) return minuend;
    int difference = minuend - minus;
    return func(max(minus, difference), min(minus, difference));  // 这个递归貌似并没有重复计算
    // 这道题中的原问题和子问题有相同的问题结构,是指都是两者相减,直到两者相等
}

int main() {
    int a, b;
    while (cin >> a >> b) {
        // int gcdivisor = greatestcommondivisor(a, b);  // 最大公约数
        int gcdivisor = func(max(a, b), min(a, b));

        cout << a * b / gcdivisor << endl;

    }
    return 0;
}
全部评论
存粹靠数学知识啊
点赞 回复 分享
发布于 2021-12-04 15:21

相关推荐

湫湫湫不会java:1.在校经历全删了2.。这些荣誉其实也没啥用只能说,要的是好的开发者不是好好学生3.项目五六点就行了,一个亮点一俩行,xxx技术解决,xxx问题带来xxx提升。第一页学历不行,然后啥有价值的信息也没有,到第二页看到项目了,第一个项目九点,第二个项目像凑数的俩点。总体给人又臭又长,一起加油吧兄弟
点赞 评论 收藏
分享
每晚夜里独自颤抖:这个在牛客不是老熟人了吗
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务