题解 | #能被多个质数整除的第K长子段#

思路：

题目的主要信息：

• 从~中挑选,作为区间，其中，即边界点可以重合
• 如果存在至少个不同的质数，每个质数都可以整除~之间的每一个数
• 我们要找到第k长的这样的区间，返回其长度即

方法一：暴力法
具体做法：
根据题意，首先我们准备了2到数组最大值中的所有质数，记录到primes中。然后我们暴力遍历每一个数对，每次对于数对区间中的元素，对每一个primes中的质数，查看是否能整除区间中所有的元素，如果可以计数加1，当计数不小于时，我们就可以记录这对数对。
然后我们重载sort函数的比较，使其排序时按照的大小来排序，这样我们就可以直接在排好序的数组中找到第大的数对了。

class Solution {
public:
    static bool comp(pair<int, int>& a, pair<int, int>& b){ //重载比较，按区间大小排序
        return a.second - a.first < b.second - b.first;
    }
    int GetKthLength(vector<int>& A, int X, int K) {
        int maxnum = *max_element(A.begin(), A.end()); //取数组最大数
        int n = A.size();
        vector<int> primes;  //记录小于最大值的所有质数
        vector<int> notPrime(maxnum + 1, 0); //辅助数组，运算质数的时候用
        notPrime[1] = 1;
        for(int i = 2; i <= maxnum; i++){ //遍历到最大值，找到所有质数
            if(!notPrime[i]) //非合数
                primes.push_back(i);
            for(int j = 0; j < primes.size() && i * primes[j] <= maxnum; j++)
                notPrime[i * primes[j]] = 1;  //这是合数
        }
        vector<pair<int, int> > leftRight;  //记录左右区间
        for(int i = 0; i < n; i++){ //遍历所有数对
            for(int j = i; j < n; j++){
                int count = 0; //统计能整除全部区间内元素的质数个数
                for(int k = 0; k < primes.size(); k++){
                    bool flag = true;
                    for(int x = i; x <= j; x++){
                        if(A[x] % primes[k] != 0){ //不能整除，这个质数不计算了
                            flag = false;
                            break;
                        }
                    }
                    if(flag)  //所有整除计数加1
                        count++;
                }
                if(count >= X) //质数个数不小于X
                    leftRight.push_back(make_pair(i, j));
            }
        }
        sort(leftRight.begin(), leftRight.end(), comp); //按照区间大小排序
        int m = leftRight.size();
        if(m < K)
            return -1; 
        return leftRight[m - K].second - leftRight[m - K].first + 1; //返回第K大  
    }
};

复杂度分析：

• 时间复杂度：，其中n为数组A的长度，m为质数数组的长度，找到所有的质数最坏遍历两层到数组A的最大值，后续嵌套了四层循环，排序和找最大值函数相对较小，可忽略。
• 空间复杂度：，多个辅助数组

方法二：改进
具体做法：
方法一嵌套循环太多，我们换种思路。
计算质数数组的时候我们就可以找到到中每个数的质因数有多少个，然后排除质因数达不到的元素。然后我们可以根据子段的最大公约数来计算，最大公约能够被不小于个质数整除即可。我们可以从到最长段开始找，利用二分思想找到第大

class Solution {
public:
    //依据长度，计算有多少个质因数，从x到结尾
    int CountMoreThanX(int x, vector<bool>& isOk, vector<vector<pair<int, int>>>& gcd){
        int s = 0, n = gcd.size();
        for(int i = 0; i < n; i++){  //遍历寻找共同的质因数个数
            for(int j = 0; j < gcd[i].size() - 1; j++){
                if(!isOk[gcd[i][j].second])
                    break;
                int len0 = i - gcd[i][j].first + 1, len1 = i - gcd[i][j + 1].first;
                if(len0 >= x)
                    s += (len1 - len0 + 1);
                else if(len1 >= x)
                    s += (len1 - x + 1);
            }
        }
        return s;
    }
    int GetKthLength(vector<int>& A, int X, int K) {
        int maxnum = *max_element(A.begin(), A.end()); //取数组最大数
        int n = A.size();
        vector <int> nums(maxnum + 1, 0); //统计每个数质因数个数
        vector <int> notPrime(maxnum + 1, 0); //记录某个数是否是质数
        vector <int> primes; //质数数组
        nums[1] = 0;
        nums[2] = 1;
        notPrime[1] = 1;
        for(int i = 2; i <= maxnum; i++){//遍历到最大值，找到所有质数
            if(!notPrime[i]){//非合数
                primes.push_back(i);
                nums[i] = 1;
            }
            for(int j = 0; j < primes.size() && i * primes[j] <= maxnum; j++){
                int p = primes[j];
                notPrime[i * p] = 1;  //这是合数
                if(i % p == 0){  //因数的个数
                    nums[i * p] = nums[i];
                    break;
                }else
                    nums[i * p] = nums[i] + 1;
            }
        }
        vector<bool> isOk(maxnum + 1, false);
        for(int i = 2; i <= maxnum; i++) //有不小于x个质因数的才标记为1
            isOk[i] = (nums[i] >= X);
        vector<vector<pair<int, int> > > gcd(n);
        for(int i = 0; i < n; i++){
            gcd[i].push_back(make_pair(i, A[i]));
            if(i > 0){
                for(auto pre : gcd[i - 1]){
                    int curgcd = __gcd(A[i], pre.second); //计算前后两个数的最大公约数
                    if(curgcd != gcd[i].back().second) //公约数不等于后面来的数
                        gcd[i].push_back(make_pair(pre.first, curgcd));  //加入前面的数
                }
            }
        }
        for(int i = 0; i < n; i++)
            gcd[i].push_back(make_pair(-1, 0));
        if(CountMoreThanX(1, isOk, gcd) < K) //数对数量小于K
            return -1;
        int l = 1, r = n;
        while (l < r) { //二分法找第k大
            int mid = l + ((r - l + 1) / 2);
            if (CountMoreThanX(mid, isOk, gcd) < K)
                r = mid - 1;
            else
                l = mid;
        }
        return l;
    }
};

复杂度分析：

• 时间复杂度：，二分法这层为，二分法里面的函数是，找到所有的质数最坏遍历两层到数组A最大值，找最大值函数相对较小，可忽略。
• 空间复杂度：，多个辅助数组