题意

求两个正整数的最小公倍数

限制: 两个数均不大于100000

方法

最小公倍数 = 乘积 除以 最大公约数

如果两个数 a,ba,b 满足

a=mka = m \cdot k

b=nkb = n \cdot k

其中 n,mn,m 互质

那么 kk为它们最大公约数,而它们的最小公倍数为nmk=abkn\cdot m \cdot k = \frac{a\cdot b}{k}


那么问题变成了如何求两个数的最大公约数

那么,最大公约数不会大于原数,所以我们从b向1依次找

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long a,b;
    cin>>a>>b;
    for(int i = b;;i--){ // 从 b 向下找 
        if(a%i == 0 && b%i == 0){ // 最大的 同时是两个数的约数
            printf("%lld\n",a*b/gcd(a,b));
            return 0;
        }
    }
    return 0;
}

复杂度分析

时间复杂度: 最坏的情况,两个数互质,需要遍历到1,所以时间复杂度为O(b)O(b)

空间复杂度: 用了常数大小的空间,所以空间复杂度为O(1)O(1)

辗转相除法

考虑 上述表示法

a=mka = m \cdot k

b=nkb = n \cdot k

那么 令 c=bmoda=(nmodm)kc = b \bmod a = (n\bmod m) \cdot k

那么 b 和 c 的 最大公约数依然是kk, 而 c<b/2c < b/2

因此,可以采取这种,交替取mod的方法,获得两个数的最大公约数

以题目样例数据5 7为例

- a b
初始 5 7
5%7=5 7 5
7%5=2 5 2
5%2=1 2 1
2%1=0 1 0

所以 5和7的最大公约数为 1

代码

#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b){ // 最大公约数
    return b == 0?a:gcd(b,a%b);
}
int main(){
    long long a,b;
    cin>>a>>b;
    printf("%lld\n",a*b/gcd(a,b));
    return 0;
}

复杂度分析

时间复杂度: 采用辗转相除法,所以时间复杂度为O(log(n))O(log(n))

空间复杂度: 用了常数大小的空间,但是递归的时候与递归深度相关,所以空间复杂度为O(log(n))O(log(n))