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 。
public int countDifferentSubsequenceGCDs(int[] nums) {
//首先定义子序列共有的最大公约数数目 以及 序列的最大数
int ans = 0, mx = 0;
//得到序列最大数
for (int x : nums) mx = Math.max(mx, x);
//以序列的最大数+1为数组的长度 因此也要再new的时候 mx + 1
boolean[] has = new boolean[mx + 1];
//序列中有这些数的时候 在有该数的下标里的 数组的值 定义为true
for (int x : nums) has[x] = true;
//这里用到一个思想 就是文中提到的 利用枚举g的倍数来实现最大公约数的查找
//https://leetcode.cn/problems/number-of-different-subsequences-gcds/solutions/2061079/ji-bai-100mei-ju-gcdxun-huan-you-hua-pyt-get7/
for (int i = 1; i <= mx; ++i) {
int g = 0; // 0 和任何数 x 的最大公约数都是 x
for (int j = i; j <= mx && g != i; j += i) // 枚举 i 的倍数 j 就+= i相当于是 通过倍数来查找
if (has[j]) // 如果 j 在 nums 中
g = gcd(g, j); // 更新最大公约数
if (g == i) ++ans; // 找到一个答案
}
return ans;
}
//最大公约数计算 辗转相除法
private int gcd(int a, int b) {
while (a != 0) {
int tmp = a;
a = b % a;
b = tmp;
}
return b;
}
}