一、概念

l c m ( a , b ) = a b g c d ( a , b ) lcmleft( a,b ight) =frac{ab}{gcdleft( a,b ight)} lcm(a,b)=gcd(a,b)ab 推导：

由算术基本定理得： a = p 1 x 1 p 2 x 2 ⋅ ⋅ ⋅ p k x k a=p_{1}^{x_1}p_{2}^{x_2}···p_{k}^{x_k} a=p1x1p2x2⋅⋅⋅pkxk b = p 1 y 1 p 2 y 2 ⋅ ⋅ ⋅ p k y k b=p_{1}^{y_1}p_{2}^{y_2}···p_{k}^{y_k} b=p1y1p2y2⋅⋅⋅pkyk则, g c d ( a , b ) = p 1 min ⁡ ( x 1 , y 1 ) p 2 min ⁡ ( x 2 , y 2 ) ⋅ ⋅ ⋅ p k min ⁡ ( x k , y k )      ( 1 )    gcdleft( a,b ight) =p_{1}^{min left( x_1,y_1 ight)}p_{2}^{min left( x_2,y_2 ight)}···p_{k}^{min left( xk,yk ight)},,,,left( 1 ight) ,, gcd(a,b)=p1min(x1,y1)p2min(x2,y2)⋅⋅⋅pkmin(xk,yk)(1) g c d ( a , b ) = p 1 min ⁡ ( x 1 , y 1 ) p 2 min ⁡ ( x 2 , y 2 ) ⋅ ⋅ ⋅ p k min ⁡ ( x k , y k )      ( 2 )    gcdleft( a,b ight) =p_{1}^{min left( x_1,y_1 ight)}p_{2}^{min left( x_2,y_2 ight)}···p_{k}^{min left( xk,yk ight)},,,,left( 2 ight) ,, gcd(a,b)=p1min(x1,y1)p2min(x2,y2)⋅⋅⋅pkmin(xk,yk)(2) （1）X （2）得： min ⁡ ( x i , y i ) + max ⁡ ( x i , y i ) = x i + y i min left( x_i,y_i ight) +max left( x_i,y_i ight) =x_i+y_i min(xi,yi)+max(xi,yi)=xi+yi即： l c m ( a , b ) × g c d ( a , b ) = a b lcmleft( a,b ight) imes gcdleft( a,b ight) =ab lcm(a,b)×gcd(a,b)=ab

二、模板

给定两个数 a、b，求它们的最小公倍数。

int gcd(int a, int b) {
          
   
    return b == 0 ? a : gcd(b, a%b); 
} 

int lcm(int a, int b) {
          
   
    return a / gcd(a, b) * b;     // 先除法，再乘法，避免溢出；
}

三、例题

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

给你一个由正整数组成的数组 nums 。

数字序列的 最大公约数 定义为序列中所有整数的共有约数中的最大整数。

例如，序列 [4,6,16] 的最大公约数是2。

数组的一个 子序列 本质是一个序列，可以通过删除数组中的某些元素（或者不删除）得到。

例如，[2,5,10]是 [1,2,1,2,4,1,5,10] 的一个子序列。

计算并返回 nums 的所有 非空 子序列中 不同 最大公约数的 数目 。

示例 1：

输入：nums = [6,10,3]
输出：5
解释：上图显示了所有的非空子序列与各自的最大公约数。
不同的最大公约数为 6 、10 、3 、2 和 1 。

示例 2：

输入：nums = [5,15,40,5,6]
输出：7

提示：

1 <= nums.length <= 105
1 <= nums[i] <= 2 * 105

解：

解题思路：

AC代码：

class Solution {
          
   
    static int[] f = new int[200001];
    public int countDifferentSubsequenceGCDs(int[] nums) {
          
   
        int max = Integer.MIN_VALUE;
        int res = 0;
        for(int num : nums){
          
   
            f[num] ++;
            max = (int)(Math.max(num, max));
            res ++; 
        }

        for(int i = 1; i <= max; i ++) {
          
   
            if(f[i] != 0) continue;
            // 枚举该数是否为里面两数的因子，保证因子不一样
            int g = 0;
            for(int j = i; j <= max; j += i) {
          
   
                if(f[j] != 0) {
          
   
                    g = gcd(j, g);
                    if(g == i) break;
                }
            }   
            if(g == i) res ++;
        }
        return res;

    }
    // 辗转相除法获得最大公约数
    public int gcd(int a, int b) {
          
   
        return b == 0 ? a : gcd(b, a%b);
    }
}