能被多个质数整除的第K长子段 （849126) 题解

暴力做法：
首先我们转换一下题意，要求存在至少X个质数可以整除A[l]~A[r]之间的所有数，等价于GCD(A[l], A[l + 1], A[l + 2], ..., A[r])存在至少X个不同的质因数。因此我们可以暴力枚举所有可能的数对(l, r)，然后求出GCD(A[l], A[l + 1], A[l + 2], ..., A[r])，并对其进行质因数分解，如果存在至少X个不同的质因数，说明这是一个合法的数对。那么我们最后只需记录下所有合法的数对并排序，找到第K长的数对即可。

int GetKthLength(vector<int>& A, int X, int K) {
    int N = 10000000;
    int n = A.size();
    vector <int> isOk(N + 5, false);
    for (int i = 2; i <= N; i++) {
        int cur = i;
        int s = 0, p = 2;
        while (p * p <= cur) {
            if (cur % p == 0) {
                s++;
                while (cur % p == 0) {
                    cur /= p;
                }
            }
            p++;
        }
        if (cur > 1) {
            s++;
        }
        isOk[i] = (s >= X);
    }
    vector <int> v;
    for (int l = 0; l < n; l++) {
        int gcd = A[l];
        if (isOk[gcd]) {
            v.push_back(-1);
            for (int r = l + 1; r < n; r++) {
                gcd = __gcd(gcd, A[r]);
                if (isOk[gcd]) {
                    v.push_back(-(r - l + 1));
                } else {
                    break;
                }
            }
        }
    }
    if (v.size() < K) {
        return -1;
    }
    sort(v.begin(), v.end());
    return -v[K - 1];
}

正解：
使用欧拉筛法，可以用O(N)时间计算出1到N之间每个数的最小质因数，并可以在筛法过程中统计1到N之间每个数有多少个不同的质因数。
然后我们考虑在枚举数对的过程中，如果r固定，因为GCD满足结合律，有

也就是说GCD随着在l递减的过程中不会增加。进一步的，如果

那么有

根据GCD的定义，显然上述左式是上述右式的一个真因数，那么左式大小不超过右式的一半，易证数对中的r固定之后

最多有 种不同的取值，且每种取值时都对应连续的一段l，因此我们可以对于每个r维护所有这些区间
最后考虑计算第K大长度，我们可以通过二分答案Ans，将原问题转换为计算有多少长度大于等于Ans的数对，只需要对于所有可能的r，枚举所有可能的，根据上一步预处理的结果得到可能的l的范围，并累加有多少个长度大于等于Ans的数对即可。
至此问题完美解决，复杂度为
欧拉筛法预处理复杂度 + 对于每个r预处理不同GCD的复杂度 + 二分答案计算复杂度，既
O(1000w) + O(n * log(1000W)) + O(log(n) * n * log(1000w)
是可以接受的复杂度

int CountMoreThanX(int x, vector <bool> &isOk, vector <vector <pair <int, int> > > &gcd) {
    int s = 0, n = (int)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;
}

/**
 * 求满足条件的第K大长度
 * @param A int整型vector 牛牛的数组A
 * @param X int整型 至少要存在X个不同的质数
 * @param K int整型 牛牛希望找到第K大的长度
 * @return int整型
 */
int GetKthLength(vector<int>& A, int X, int K) {
    int N = 10000000;
    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;
            }
        }
    }
    vector <bool> isOk(N + 5, false);
    for (int i = 2; i <= N; i++) {
        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) {
        return -1;
    }
    int l = 1, r = n;
    while (l < r) {
        int mid = l + ((r - l + 1) >> 1);
        if (CountMoreThanX(mid, isOk, gcd) < K) {
            r = mid - 1;
        } else {
            l = mid;
        }
    }

    return l;
}