Hard
题目描述
给你一个长度为 n 的整数数组 nums 和一个整数 p。
nums 的一个非空子序列被称为好的，如果：
- 它的长度严格小于
n。 - 它的所有元素的最大公约数（GCD）恰好等于
p。
同时给你一个长度为 q 的二维整数数组 queries，其中每个 queries[i] = [indi, vali] 表示你应该将 nums[indi] 更新为 vali。
在每次查询后，判断当前数组中是否存在任何好子序列。
返回存在好子序列的查询次数。
术语 gcd(a, b) 表示 a 和 b 的最大公约数。
示例 1：
输入：nums = [4,8,12,16], p = 2, queries = [[0,3],[2,6]]
输出：1
示例 2：
输入：nums = [4,5,7,8], p = 3, queries = [[0,6],[1,9],[2,3]]
输出：2
示例 3：
输入：nums = [5,7,9], p = 2, queries = [[1,4],[2,8]]
输出：0
提示：
2 <= n == nums.length <= 5 * 10^41 <= nums[i] <= 5 * 10^41 <= queries.length <= 5 * 10^4queries[i] = [indi, vali]1 <= vali, p <= 5 * 10^40 <= indi <= n - 1
解题思路
这是一道复杂的数论题目。关键思路如下：
核心观察：
- 子序列的GCD恰好为p，意味着所有元素都是p的倍数，且除以p后没有公共质因子
- 将问题转化：只考虑能被p整除的元素，将它们都除以p，问题变成"是否存在没有公共质因子的子序列"
算法步骤：
- 预处理质因数分解： 对每个可能的数值进行质因数分解
- 维护活跃元素： 只关注能被p整除的数组元素
- 质因子计数： 对每个质因子，统计有多少个活跃元素包含它
- 判断条件：
- 如果某个质因子被所有活跃元素包含，则不存在好子序列
- 如果活跃元素数量等于n，则不存在长度小于n的子序列
- 否则存在好子序列
优化要点：
- 使用埃拉托斯特尼筛法预处理质因数
- 动态维护质因子计数，避免重复计算
- 及时剪枝，当发现某质因子覆盖所有元素时立即返回false
代码实现
class Solution {
public:
int countGoodSubseq(vector<int>& nums, int p, vector<vector<int>>& queries) {
int n = nums.size();
const int MAXN = 50000;
// 预处理：找到每个数的最小质因子
vector<int> spf(MAXN + 1);
for (int i = 1; i <= MAXN; i++) spf[i] = i;
for (int i = 2; i * i <= MAXN; i++) {
if (spf[i] == i) {
for (int j = i * i; j <= MAXN; j += i) {
if (spf[j] == j) spf[j] = i;
}
}
}
// 获取质因数的函数
auto getFactors = [&](int x) {
vector<int> factors;
while (x > 1) {
int f = spf[x];
factors.push_back(f);
while (x % f == 0) x /= f;
}
return factors;
};
int result = 0;
vector<int> current = nums;
for (auto& query : queries) {
int idx = query[0], val = query[1];
current[idx] = val;
// 找到所有能被p整除的元素
vector<int> active;
for (int x : current) {
if (x % p == 0) {
active.push_back(x / p);
}
}
if (active.empty() || active.size() == n) {
continue;
}
// 统计每个质因子出现在多少个元素中
map<int, int> factorCount;
for (int x : active) {
vector<int> factors = getFactors(x);
set<int> uniqueFactors(factors.begin(), factors.end());
for (int f : uniqueFactors) {
factorCount[f]++;
}
}
// 检查是否有质因子覆盖所有活跃元素
bool hasGoodSubseq = true;
for (auto& [factor, count] : factorCount) {
if (count == active.size()) {
hasGoodSubseq = false;
break;
}
}
if (hasGoodSubseq) {
result++;
}
}
return result;
}
};
class Solution:
def countGoodSubseq(self, nums: list[int], p: int, queries: list[list[int]]) -> int:
n = len(nums)
MAXN = 50000
# 预处理：计算每个数的最小质因子
spf = list(range(MAXN + 1))
for i in range(2, int(MAXN**0.5) + 1):
if spf[i] == i:
for j in range(i * i, MAXN + 1, i):
if spf[j] == j:
spf[j] = i
def get_factors(x):
factors = []
while x > 1:
f = spf[x]
factors.append(f)
while x % f == 0:
x //= f
return factors
result = 0
current = nums[:]
for idx, val in queries:
current[idx] = val
# 找到所有能被p整除的元素
active = []
for x in current:
if x % p == 0:
active.append(x // p)
if not active or len(active) == n:
continue
# 统计每个质因子出现在多少个元素中
factor_count = {}
for x in active:
factors = get_factors(x)
unique_factors = set(factors)
for f in unique_factors:
factor_count[f] = factor_count.get(f, 0) + 1
# 检查是否有质因子覆盖所有活跃元素
has_good_subseq = True
for count in factor_count.values():
if count == len(active):
has_good_subseq = False
break
if has_good_subseq:
result += 1
return result
public class Solution {
public int CountGoodSubseq(int[] nums, int p, int[][] queries) {
int n = nums.Length;
const int MAXN = 50000;
// 预处理：计算每个数的最小质因子
int[] spf = new int[MAXN + 1];
for (int i = 1; i <= MAXN; i++) spf[i] = i;
for (int i = 2; i * i <= MAXN; i++) {
if (spf[i] == i) {
for (int j = i * i; j <= MAXN; j += i) {
if (spf[j] == j) spf[j] = i;
}
}
}
List<int> GetFactors(int x) {
var factors = new List<int>();
while (x > 1) {
int f = spf[x];
factors.Add(f);
while (x % f == 0) x /= f;
}
return factors;
}
int result = 0;
int[] current = new int[n];
Array.Copy(nums, current, n);
foreach (var query in queries) {
int idx = query[0], val = query[1];
current[idx] = val;
// 找到所有能被p整除的元素
var active = new List<int>();
foreach (int x in current) {
if (x % p == 0) {
active.Add(x / p);
}
}
if (active.Count == 0 || active.Count == n) {
continue;
}
// 统计每个质因子出现在多少个元素中
var factorCount = new Dictionary<int, int>();
foreach (int x in active) {
var factors = GetFactors(x);
var uniqueFactors = new HashSet<int>(factors);
foreach (int f in uniqueFactors) {
factorCount[f] = factorCount.GetValueOrDefault(f, 0) + 1;
}
}
// 检查是否有质因子覆盖所有活跃元素
bool hasGoodSubseq = true;
foreach (int count in factorCount.Values) {
if (count == active.Count) {
hasGoodSubseq = false;
break;
}
}
if (hasGoodSubseq) {
result++;
}
}
return result;
}
}
var countGoodSubseq = function(nums, p, queries) {
const n = nums.length;
const MAXN = 50000;
// 预处理：计算每个数的最小质因子
const spf = new Array(MAXN + 1);
for (let i = 1; i <= MAXN; i++) spf[i] = i;
for (let i = 2; i * i <= MAXN; i++) {
if (spf[i]
复杂度分析
| 复杂度 | 分析 |
|---|---|
| 时间复杂度 | O(MAXN log log MAXN + Q × N × log MAXN) |
| 空间复杂度 | O(MAXN + N × log MAXN) |
其中 MAXN = 50000，Q 为查询次数，N 为数组长度。预处理质因数分解需要 O(MAXN log log MAXN)，每次查询需要 O(N × log MAXN) 进行质因数分解和计数。