NC542 能被多个质数整除的第K长子段

题目描述

给你一个数组$AA$和正整数$X\mathrm{，}KX，K$，定义如下的连续子序列$A[l\mathrm{.}\mathrm{.}\mathrm{.}r]A[l...r]$是好的：

存在至少X个不同的质数，可以整除子数组里的每个数

求数组A所有的好的子序列里，第$KK$长的是多长？

1. 暴力

直接根据题意模拟：

1. 求2到$max{A}_{i}max\{A\_i\}$的所有素数
2. 枚举$l,rl,\; r$, 判断这个子序列是不是好的，如果是，记录答案
3. 排序，取第K大

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求满足条件的第K大长度
     * @param A int整型vector 牛牛的数组A
     * @param X int整型 至少要存在X个不同的质数
     * @param K int整型 牛牛希望找到第K大的长度
     * @return int整型
     */
    static const int MAXN = 1e7 + 5;
    int prime[MAXN], cnt;
    bool isprime[MAXN];
    
    // O(N)求素数
    void getPrime(int maxA) {
        memset(isprime, true, sizeof(isprime));
        
        isprime[1] = false;
        cnt = 0;
        
        for (int i = 2; i <= maxA; i++) {
            if (isprime[i]) prime[++cnt] = i;
            for (int j = 1; j <= cnt && i*prime[j] <= maxA; j++) {
                isprime[i*prime[j]] = false;
                if (i % prime[j] == 0)
                    break;
            }
         }
    }

    // 算比x小的素数有多少个
    int pi(int x) {
        int l = 0, r = cnt;
        while (l < r) {
            int mid = l+r>>1;
            if (prime[mid] > x) r = mid - 1;
            else l = mid + 1;
        }
        return l;
    }

    // 判断A[l...r]是不是好的
    bool isGoodSubArray(vector<int>& a, int l, int r, int X) {
        int x = 0;
        int maxa = -1;
        for (int i = l; i <= r; i++)
            maxa = max(maxa, a[i]);
        
        for (int i = 1; i <= min(1, pi(maxa)); i++) {
            bool flag = true;
            for (int j = l; j <= r; j++) {
                if (a[j] % prime[i]) {
                    flag = false;
                    break;
                }
            }
            if (flag) x++;
        }
        
        return x >= X;
    }

    
    int GetKthLength(vector<int>& A, int X, int K) {
        int maxA = *max_element(A.begin(), A.end()); // O(n)
        
        int n = A.size();
        getPrime(maxA); // 求2到$max{A_i}$的所有素数， O(maxa)
        
        vector<int> res;

        // 暴力判断每个区间是不是好的
        // O(n^2)*O(n*pi_maxa) = O(n^3*pi_maxa)
        for (int l = 0; l < n; l++) {
            for (int r = l; r < n; r++) {
                if (isGoodSubArray(A, l, r, X)) res.push_back(r-l+1);
            }
        }
        
        // 极端情况所有的子序列都是好的，O(n^2logn)
        sort(res.begin(), res.end(), greater<int>());

        if (res.size() < K) return -1;
        return res[K-1];
    }
};

• 时间复杂度：最坏情况下是$O(n^3\ast \pi (maxa))O(n^3*\backslash pi(maxa))$, 上述代码最慢的部分是暴力遍历所有区间，两重循环，isGoodSubArray最坏情况遍历所有小于$maxamaxa$素数, 其中$\pi (x)\backslash pi(x)$叫素数计数函数，表示x以内有多少个素数。

• 空间复杂度：最坏情况是$O(n^2+maxa)O(n^2+maxa)$. 最坏情况下，所有子序列都是好的，res的长度达到$O(n^2)O(n^2)$, 还开了$maxamaxa$大小的两个数组用于计算素数。

2. 二分优化

思路1的循环显然太多了，我们看下哪里是优化点。

方法一中，我们遍历了每个素数，其实本题根本不关心具体是哪个素数能整除这个子数组。

我们在这里定义一个数有X个质因数的数是好的合数。那么如果一个子序列的gcd是好的合数，那么这个子序列的所有子序列肯定是答案；相反一个子序列的gcd不是好的合数，那么这个gcd的任何因数一定也不是好的，可以推出它外面的子序列一定不是答案。

我们用一个类似hashmap的拉链维护每个点作为右端点的区间的gcd，并且从上到下保证单调。如下图所示。

然后遍历整个拉链数组，对每一条拉链上的节点遍历，如果这个节点上的gcd不是好的，它以下（对应左端点以左）就一定不是答案，我们break遍历下一条链即可；否则统计对答案的贡献，记得去重。

最后我们可以利用这个性质计算出任意长度的区间有多少条，然后二分答案看一下长度为几的时候恰好超过k。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求满足条件的第K大长度
     * @param A int整型vector 牛牛的数组A
     * @param X int整型 至少要存在X个不同的质数
     * @param K int整型 牛牛希望找到第K大的长度
     * @return int整型
     */
    
    static const int MAXN = 1e5 + 5;
    int prime[MAXN], factor[MAXN];
    bool isprime[MAXN];
    
    bool isGoodNum[MAXN];
    int cnt = 0;
    
    void getPrime(int maxa) {
        memset(isprime, true, sizeof(isprime));
        
        factor[1] = 0, factor[2] = 1;
        isprime[1] = false;
        
        for (int i = 2; i <= maxa; i++) {
            if (isprime[i]) {
                prime[++cnt] = i;
                factor[i] = 1; // 素数是1
            }
            
            for (int j = 1; j <= cnt && i * prime[j] <= maxa; j++) {
                isprime[i * prime[j]] = false;
                
                // i*prime[j] 肯定是合数，算它的因子个数
                if (i % prime[j] == 0) {
                    factor[i * prime[j]] = factor[i];
                    break;
                } else {
                    factor[i * prime[j]] = factor[i] + 1;
                }
            }
        }
    }
    
    void markGoodNum(int maxa, int x) {
        for (int i = 2; i <= maxa; i++)
            if (factor[i] >= x) isGoodNum[i] = true;
    }
    
    vector<vector<pair<int, int>>> getGCDList(vector<int> &a) {
        int n = a.size();
        vector<vector<pair<int, int>>> res(n);
             
        for (int i = 0; i < n; i++) {
            res[i].push_back({i, a[i]});
            
            if (i >= 1) {
                for (auto last : res[i-1]) {
                    int gcd = __gcd(a[i], last.second);
                    if (gcd != res[i].back().second) {
                        res[i].push_back({last.first, gcd});
                    }
                }
            }
            
            res[i].push_back({-1, 0});
        }
        
        return res;
    }
    
    
    bool check(int l, vector<vector<pair<int, int>>> gcd, int k) {
        int n = gcd.size();
        
        int tot = 0;
        for (int i = 0; i < n; i++) {
            int nn = gcd[i].size();
            for (int j = 0; j < nn - 1; j++) {
                auto p = gcd[i][j];
                // 如果第i条拉链的第j个gcd不是好合数，说明这个子区间肯定不会是好区间
                // 该数的gcd就更不是了，直接break！
                
                if (!isGoodNum[p.second]) break;
                
                int l0 = i - p.first + 1;
                int l1 = i - gcd[i][j+1].first;
                
                if (l0 >= l) tot += l1 - l0 + 1;
                else if (l1 >= l) tot += l1 - l + 1;
            }
        }
        
        return tot > k;
    }
    
    int GetKthLength(vector<int>& A, int X, int K) {
        int maxA = *max_element(A.begin(), A.end()); // O(n)
        
        int n = A.size();
        getPrime(maxA); // 求2到$max{A_i}$的所有素数， O(maxa)
        markGoodNum(maxA, X); // 记录下哪个数是有超过X个质因子的, 称为好数
                
        vector<vector<pair<int, int>>> gcdList = getGCDList(A);
        
        
        if (!check(1, gcdList, K)) return -1;
        
        int l = 1, r = n;
        while (l < r) {
            int mid = l+r+1>>1;
            if (check(mid, gcdList, K)) r = mid - 1;
            else l = mid;
        }
        
        
        return l;
    }
};

• 时间复杂度：最坏情况下是$O(n^{2}logn+maxa)O(n^2logn+maxa)$, getPrime和markGoodNum都是遍历$maxamaxa$长度, 二分答案里面的check是两重循环。

• 空间复杂度：$O(n^2+maxa)O(n^2+maxa)$. 一堆maxa级别的数组，和$O(n^2)O(n^2)$的拉链