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

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大
}
};</int></int></int>