https://www.luogu.com.cn/problem/P8292
题解
先把小于等于\(\sqrt{2000}\)的质数打一个表,发现只有\(14\)个,其中第\(14\)个是\(43\).
令前\(14\)个质数为小质数,其它的为大质数.
一个数因式分解后最多只会含有一个大质数.
于是,我们可以令\(f[s][i]\)表示含有第\(i\)个大质数,小质数的选择情况为\(s\)的子集的数字个数.
这样,给定的\(n\)个数就被划分成了两部分,要么含有大质数,要么不含大质数.
假设询问的小质数的集合为\(S\).
考虑每一个大质数,如果包含在询问中,它至少选一个,选法为\(2\)的幂减\(1\),如果没有包含在询问中,它可选可不选,选法为\(2\)的幂.注意,最后答案还应该包括满足条件的小质数随便选.
假设我们把集合\(s\)按照如上方法求得的答案为\(F[s]\).
如果只求\(F[S]\),必然会使得一些方案并不包含集合\(S\).
这怎么办呢?
可以考虑容斥.
对于\(S\),我们考虑枚举没有选择的\(1\)个小质数强制它不选,减去它的\(F\),但是这会使得没有选择\(2\)个小质数的方案被多减,于是要加上它的\(F\).
最后我们发现这是一个容斥系数为\(-1\)的幂的容斥.
时间复杂度为\(O(C2 ^ {14}m+2 ^ {14} \sum _ i c _ i)\),其中\(C\)为一个较大的常数.
总结
考试的时候发现了质数个数很少的性质,但过度关注了质因子的组合情况很多,而忽略了一个数至多只含一种大质数的性质.
1.与质因数有关的题目,要想到大于等于\(\sqrt{N}\)的数只含有一种大质因子的性质.
2.要求满足集合\(S\)的方案数,可以考虑求满足集合\(S\)子集的方案数再容斥,或对补集的子集进行容斥.
代码
#include <bits/stdc++.h>
using namespace std;
const int maxp = 2000;
const int maxn = 1e6;
const int mod = 998244353;
int inc(int x, int y) { return (x + y >= mod) ? (x + y - mod) : (x + y); }
int dec(int x, int y) { return (x - y < 0) ? (x - y + mod) : (x - y); }
int mul(int x, int y) { return 1ll * x * y % mod; }
int mo(int x) { return (x % mod + mod) % mod; }
int n, m;
int tot, p[maxp + 5], pid[maxp + 5], cnt[maxp + 5];
int f[304][1 << 14], a[18005], pw[maxn + 5];
bool vis[maxp + 5];
void sieve() {
for(int i = 2; i <= maxp; i++) {
if(!vis[i])
p[++tot] = i, pid[i] = tot;
for(int j = 1; j <= tot; j++) {
vis[i * p[j]] = 1;
if(i % p[j] == 0) break;
if(i * p[j] > maxp) break;
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
sieve();
int lim = 1;
while(p[lim + 1] * p[lim + 1] <= maxp)
lim++;
cin >> n;
for(int i = 1, x; i <= n; i++) {
cin >> x;
cnt[x]++;
}
// O(2 ^ 14 * 2000 * C)
for(int s = 0; s < (1 << lim); s++) {
for(int i = 1; i <= maxp; i++) vis[i] = 0;
for(int i = 1; i <= lim; i++)
if((1 << (i - 1)) & s)
for(int j = 1; j * p[i] <= maxp; j++)
vis[p[i] * j] = 1;
for(int i = 1; i <= maxp; i++)
if(!vis[i])
f[0][s] = inc(f[0][s], cnt[i]);
for(int i = lim + 1; i <= tot; i++)
for(int j = 1; j * p[i] <= maxp; j++)
if(!vis[j * p[i]])
f[i][s] = inc(f[i][s], cnt[j * p[i]]);
}
pw[0] = 1;
for(int i = 1; i <= n; i++)
pw[i] = mul(pw[i - 1], 2);
cin >> m;
// O(2 ^ 14 * 300 * 1500)
// O(2 ^ 14 * 1500)
while(m--) {
int k;
cin >> k;
for(int i = 1; i <= k; i++)
cin >> a[i];
sort(a + 1, a + 1 + k);
k = unique(a + 1, a + 1 + k) - a - 1;
int ss = 0, si = k + 1;
for(int i = 1; i <= k; i++)
if(pid[a[i]] <= lim)
ss |= (1 << (pid[a[i]] - 1));
else {
si = i;
break;
}
int ans = 0;
for(int s = ss; ; s = (s - 1) & ss) {
int res = 1, t = f[0][s];
for(int i = si; i <= k; i++) {
res = mul(res, pw[f[pid[a[i]]][s]] - 1);
t = dec(t, f[pid[a[i]]][s]);
}
res = mul(res, pw[t]);
if(__builtin_parity(s))
ans = dec(ans, res);
else
ans = inc(ans, res);
if(s == 0) break;
}
cout << ans << '\n';
}
return 0;
}