题意

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

限制: 两个数均不大于100000

方法

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

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

$a=m\cdot ka\; =\; m\; \backslash cdot\; k$

$b=n\cdot kb\; =\; n\; \backslash cdot\; k$

其中 $n,mn,m$ 互质

那么 $kk$为它们最大公约数,而它们的最小公倍数为$n\cdot m\cdot k=\frac{a\cdot b}{k}n\backslash cdot\; m\; \backslash cdot\; k\; =\; \backslash frac\{a\backslash 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)$，如果找到了同时是两个数的因数的i，那么gcd运算为$O(log(min(a,b)))O(log(min(a,b)))$,并且gcd只会算一次，所以总时间复杂度为$O(b+log(min(a,b)))=O(b)O(b+log(min(a,b)))\; =\; O(b)$

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

辗转相除法

考虑 上述表示法

$a=m\cdot ka\; =\; m\; \backslash cdot\; k$

$b=n\cdot kb\; =\; n\; \backslash cdot\; k$

那么 令 $c=b\mathrm{m}\mathrm{o}\mathrm{d}a=(n\mathrm{m}\mathrm{o}\mathrm{d}m)\cdot kc\; =\; b\; \backslash bmod\; a\; =\; (n\backslash bmod\; m)\; \backslash cdot\; k$

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

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

以题目样例数据5 7为例

所以 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))$