AcWing 809. 最小公倍数    原题链接    中等

作者： 作者的头像   无语的小高 ,  2020-02-27 10:28:46 ,  所有人可见 ,  阅读 5693

36


18

最小公倍数 = 两数乘积 / 最大公约数

#include<iostream>
using namespace std;

int gcd(int a, int b){
    do{
        int c = a%b;
        a = b;
        b = c;
    }while(b);
    return a;
}

int lcm(int a, int b){
    return a*b / gcd(a, b);
}

int main(){
    int a, b;
    cin>>a>>b;
    if(a>b){
        cout << lcm(a, b);
    }else{
        cout << lcm(b, a);
    }
    return 0;
}

8 评论

用户头像
zhoukangyang   2022-06-11 10:44      8    踩      回复 
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int f(int a,int b){
    for(int i=max(a,b);;i++){
        if(i%a==0 && i%b==0){
            return i;
        }
    }
}
int main()
{
    int a,b;
    cin>>a>>b;
    cout<<f(a,b);
}

$$直接暴力AC$$

用户头像
acw_zyx   2021-06-12 13:04      2    踩      回复

最后main函数里的if(a >b)这个不用判断的，因为gcd对于传入参数的大小顺序没有影响

用户头像
Tender_4   2021-11-21 13:06      3    踩      回复

对！昨天我也加了if条件 现在明白a<b时a%b之后的操作相当于自动交换ab的值

用户头像
zhoukangyang   2023-01-01 15:36      1    踩      回复 
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;
    cout<<a*b/__gcd(a,b);
}

$$好像这样也可以$$

用户头像
低能所以不学算法   2022-11-11 13:30         踩      回复

暴力枚举也可以

用户头像
lixiaoqian_qwq   2020-02-27 11:11         踩      回复

递归还是递推

用户头像
Jeck_Lin   2020-03-30 14:51         踩      回复

递推吧

用户头像
蒜白   2022-12-03 16:11         踩      回复

递推