Daily LeetCode – day0169 1819. Number of Different Subsequences GCDs

// 1819. Number of Different Subsequences GCDs
class Solution {
    public int countDifferentSubsequenceGCDs(int[] nums) {
        int[] GCDs = new int[200001];
        for (int num : nums) {
            for (int i = 1; i * i <= num; ++i) {
                if (num % i == 0) {
                    if (GCDs[i] == 0) {
                        GCDs[i] = num;
                    } else {
                        GCDs[i] = gcd(GCDs[i], num);
                    }
                    if (GCDs[num / i] == 0) {
                        GCDs[num / i] = num;
                    } else {
                        GCDs[num / i] = gcd(GCDs[num / i], num);
                    }
                }
            }
        }
        int ans = 0;
        for (int i = 1; i < 200001; ++i) {
            if (GCDs[i] == i) {
                ++ans;
            }
        }
        return ans;
    }

    private int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
}

学习笔记：
强迫自己进步的一天，这是一道困难题。
思路用得很巧妙，本来是先归类再计算，然后转化成了一边分类分类进去就顺便计算。
题目说题目数字在20万以内，那么最大的最大公约数也就是20万了。

然后我们可以逐一去考虑，每一个最大公约数怎么检验是否符合呢？
比如要校验4，那么得把所有4的正整数倍数找出来：
情况1：4,8,12,16,20这样的，那么有4在，肯定最大公约数肯定是4了。
情况2：8,16,64这样的，那么最大公约数其实是8，那么就不存在最大公约数为4的情况。
情况3：8,12,16,20这样的，没有4在，但是他们的最大公约数也是4。
总结就是把倍数找出来，然后连续求最大公约数。

接着就遇到了死胡同，这样一个个校验，从1到200000，挑出来要遍历一整遍，然后连续求最大公约数也要时间。总共加起来要做200000个一整遍。

巧妙的来了，其实只要遍历一整遍，每次找到是某个数的倍数，那么就分类顺便把连续求最大公约数的步骤也做了。这样只需要弄个200001的空间存当前的最大公约数们就可以啦。

最后统计有多少个数字的最大公约数是自己那也就是存在。

// 1819. Number of Different Subsequences GCDs
class Solution {
    public int countDifferentSubsequenceGCDs(int[] nums) {
        int[] GCDs = new int[200001];
        for (int num : nums) {
            for (int i = 1; i * i <= num; ++i) {
                if (num % i == 0) {
                    if (GCDs[i] == 0) {
                        GCDs[i] = num;
                    } else if (GCDs[i] != i) {
                        GCDs[i] = gcd(GCDs[i], num);
                    }
                    int numOverI = num / i;
                    if (GCDs[numOverI] == 0) {
                        GCDs[numOverI] = num;
                    } else if (GCDs[numOverI] != numOverI) {
                        GCDs[numOverI] = gcd(GCDs[numOverI], num);
                    }
                }
            }
        }
        int ans = 0;
        for (int i = 1; i < 200001; ++i) {
            if (GCDs[i] == i) {
                ++ans;
            }
        }
        return ans;
    }

    private int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
}

接下来又优化了代码，从572ms变到了446ms。
就是说一旦中途发现gcds[i]已经等于i了，那就没有下探空间了。
所以不需要再调用gcd函数递归去求了。
gcd[num / i]已经等于num / i也是一样的道理。
用上变量可以更快，不用反复去除以。