[每日一题]1819.序列中不同最大公约数的数目
1819. 序列中不同最大公约数的数目 给你一个由正整数组成的数组 nums 。数字序列的 最大公约数 定义为序列中所有整数的共有约数中的最大整数。
例如，序列 [4,6,16] 的最大公约数是 2 。
数组的一个 子序列 本质是一个序列，可以通过删除数组中的某些元素（或者不删除）得到。
例如，[2,5,10] 是 [1,2,1,2,4,1,5,10] 的一个子序列。
计算并返回 nums 的所有 非空 子序列中 不同 最大公约数的 数目 。
举例：
-
输入：nums = [6,10,3] 输出：5 解释：上图显示了所有的非空子序列与各自的最大公约数。 不同的最大公约数为 6 、10 、3 、2 和 1 。 -
输入：nums = [5,15,40,5,6] 输出：7
Solution
class Solution {
public int countDifferentSubsequenceGCDs(int[] nums) {
// 求出当前数组的最大值
int maxVal = Arrays.stream(nums).max().getAsInt();
// 定义一个长度为 maxVal + 1 的数组
boolean[] occured = new boolean[maxVal + 1];
// 用 true 表示 occured 中对应下标的数在 nums 中存在
for (int num : nums) {
occured[num] = true;
}
// 初始化答案
int ans = 0;
// 核心代码
// 遍历 occured 数组，i [1, maxVal]，这个范围是最大公因数的范围
for (int i = 1; i <= maxVal; i++) {
// 设 当前 subGcd 为 0
int subGcd = 0;
// 暴力，j = i, j += i，此时 j 是 i 的倍数，j + i 也是 i 的倍数
for (int j = i; j <= maxVal; j += i) {
// 若当前下标 j 在 nums 中存在
if (occured[j]) {
// 若当前 subGcd 为零，说明刚遇到第一个 i 的倍数，设置当前的 subGcd = j
if (subGcd == 0) {
subGcd = j;
} else { // 遇到其他 i 的倍数，这时取最大公约数，就可能出现最大公约数 i
subGcd = gcd(subGcd, j);
}
// 如果，subGcd == i，说明存在最大公约数 i，累加一次
if (subGcd == i) {
ans++;
break; // 当前 i 值已经有符合条件的，则寻找下一个 i 是否有满足条件的子数组
}
// 否则继续循环寻找
}
}
}
return ans;
}
public int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}