[题解]《算法零基础100讲》(第14讲)最小公倍数

一. 概念定义

??最小公倍数就是两个数a，b他们的公共倍数中最小的那个(感觉说了跟没说一样)。

1.1 lcm算法

在学习lcm算法之前我们需要先补充一下gcd的算法，推荐博客：

最大公约数

??lcm算法就是计算两个数的最小公倍数算法。我们有定理可知，a和b两数的最小公倍数lcm(a，b) = a * b / gcd(a，b);
代码如下：

//计算表最大公约数
int gcd(int a, int b){
    return !b ? a : gcd(b, a % b);
}
//计算最小公倍数
int lcm(int a, int b){
    return a / gcd(a, b) * b;
}

二. 课后练习

1819. 序列中不同最大公约数的数目

这道题是真的难。正常人能够想到的可能就是列举所以子序列，并对每个子序列找出其应有的最大公约数，这个想法先不说时间复杂度，光是列举所有子序列，如果没有库的支持也很难写出，所以暴力是不可能的。

所以我们先来整理一下思路：

1. 对于每个数组，其数组内的每一个元素本身也算一个子序列，固每个不同的元素也算一个子序列的最大公约数
2. 我们可以定义一个bool类型的数组f[200001]，用于标记nums所包含的数据，标记的同时找出最大值max，应为公约数的范围肯定实在[1，max]的区间内。
3. 假设a，b两个数的最大公约数等于gcd(a，b)，则a，b，c的最大公约数为gcd(gcd(a，b)，c)，以此类推，通过这种方式我们可以找出一组数的最大公约数。
4. 我们可以考虑用素数筛选法的思想方式，找出序列中所有的x的倍数的元素，然后判断者须倍数是不是序列的最大公因数

代码如下：

int gcd(int a, int b){
    return !b ? a : gcd(b, a % b);
}int countDifferentSubsequenceGCDs(int* nums, int numsSize){
    int ans = 0;//统计bool f[200001] = {
    0};//记录nums中的数据int max = 0;for(int i = 0; i < numsSize; i++){
    if(!f[nums[i]]){
    f[nums[i]]++;ans++;//nums的每个元素都时子序列[nums[i]]的一个最大公约数} if(nums[i] > max)max = nums[i];}for(int i = 1; i <= max; i++){
    if(f[i])continue;int g = 0;for(int j = i; j <= max; j += i){
    if(f[j]){
    g = gcd(j, g);if(g == i){
    ans++;break;}}}}return ans;
}