能被多个质数整除的第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; }