能被多个质数整除的最长子序列 （849126) 题解

暴力做法：
最暴力的做法是dfs枚举每个数是否被选取，然后枚举质数，看是否存在X个不同的质数可以整除选取的所有数。
但这样dfs的复杂度是2^S.size()
复杂度太高，即使加上剪枝也很难通过

正解：
首先我们转换一下题意，要求存在至少X个质数可以整除未被删除的所有数，等价于GCD(剩下的所有数)存在至少X个不同的质因数。
那么我们可以用筛法预处理出1~10^6中每个数有多少个不同的质数，然后枚举每个可行的GCD。
首先可以用cnt[i]记录数组中一共有多少个数i，那么当枚举GCD为g时，最终保留的数为
cnt[g] + cnt[2 * g] + cnt[3 * g] + ... + cnt[10^6 div g * g] (div为整除)
我们可以暴力枚举g的每一个倍数，这样复杂度不超过
10^6 + 10^6 / 2 + 10^6 / 3 + ... + 10^6 / 10^6
根据调和级数
lim(n→∞)∑1/n-ln(n)收敛于欧拉常数
故复杂度不超过10^6 * ln(10^6)，是合理的复杂度
实际上因为合法的质数不多，复杂度要更小

class Solution {
public:
    /**
     * 返回最少删除多少个元素
     * @param A int整型vector 牛牛的数组A
     * @param X int整型 至少存在X个不同的质数可以整除剩下的每一个元素
     * @return int整型
     */
    int GetMinErasedElements(vector<int>& A, int X) {
        int N = 1000000;
        int n = A.size();
        vector <int> cnt(N + 5, 0);
        vector <int> nums(N + 5, 0);
        vector <int> notPrime(N + 5, 0);
        vector <int> primes;
        nums[1] = 0;
        nums[2] = 1;
        notPrime[1] = 1;
        for (int i = 2; i <= N; i++) {
            if (!notPrime[i]) {
                primes.push_back(i);
                nums[i] = 1;
            }
            for (int j = 0; j < (int)primes.size() && i * primes[j] <= N; j++) {
                int p = primes[j];
                notPrime[i * p] = true;
                if (i % p == 0) {
                    nums[i * p] = nums[i];
                    break;
                } else {
                    nums[i * p] = nums[i] + 1;
                }
            }
        }
        for (int i : A) {
            cnt[i]++;
        }
        int ans = n;
        for (int i = 2; i <= N; i++) {
            if (nums[i] >= X) {
                int curAns = n;
                for (int j = i; j <= N; j += i) {
                    curAns -= cnt[j];
                }
                ans = min(ans, curAns);
            }
        }
        return ans;
    }
};