ARC141D Non-divisible Set
这题还是比较有启发性的。
经典的偏序关系下最长反链，第一反应是转化为最小链覆盖，但是在很多以整数的整除关系为背景的题目中这个做法不是最好的。
洛谷的题意翻译中少给了一个信息：值域为 \([1,2M]\)。这个条件看上去就应该和选 \(M\) 个数的限制结合。若由 \(i\) 向 \(2i\) 连边，观察到恰好形成了 \(M\) 条链，又有每条链只能选一个数，所以最多选 \(M\) 个数，且每条链上都需要选一个数。
如果把每条链中唯一的奇数当作这条链的代表元，那么可以将最终选出来的每个数都表示为 \(2^{k_n}n\) 的形式，现在只需要解决 \(k\) 的取值。
重新描述题目中的限制
\[2^{k_i}i | 2^{k_j}j \Leftrightarrow i | j \wedge k_i \leq k_j
\]
考察对于奇数 \(i\)，若有 \(k_i\) 的最大值为 \(r_i\)，最小值为 \(l_i\)，不难发现对于任意 \(x \in [l_i,r_i]\)，\(k=x\) 都是合法的。所以现在只需要求 \(l\) 和 \(r\) 了。这是平凡的。时间复杂度 \(O(m \log m + n)\)
这题关键在于由 \(i\) 向 \(2i\) 连边的分组，利用了值域和限制的特殊关系，通过钦定奇数为代表元化简了问题。
#include <bits/stdc++.h>
#define log2(x) (31 - __builtin_clz(x))
using namespace std;
typedef long long LL;
namespace IO {
#define isdigit(x) (x >= '0' && x <= '9')
template<typename T>
inline void read(T &x) {
x = 0; char ch = getchar(); int f = 0;
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
if(f) x = -x;
}
template<typename T>
inline void write(T x) {
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
#undef isdigit
}
using namespace IO;
const int N = 6e5 + 10;
int n, m;
int a[N], c[N];
int l[N], r[N];
int ans[N];
vector<int> factor[N];
int main() {
read(n), read(m);
for(int i = 1; i <= n; ++i)
read(a[i]), c[a[i]] = 1;
for(int i = 1; i <= 2 * m; i += 2)
for(int j = i * 3; j <= 2 * m; j += i * 2)
factor[j].emplace_back(i);
for(int i = 1; i <= 2 * m; i += 2)
r[i] = log2(2 * m / i), l[i] = 0;
for(int i = 1; i <= 2 * m; i += 2) {
for(int j : factor[i])
r[i] = min(r[i], r[j] - 1);
while(r[i] && !c[i << r[i]]) --r[i];
if(!r[i] && !c[i]) {
for(int i = 1; i <= n; ++i)
puts("No");
return 0;
}
}
for(int i = 2 * m - 1; i >= 1; i -= 2) {
while((i << l[i]) <= 2 * m && !c[i << l[i]]) ++l[i];
if((i << l[i]) > 2 * m) {
for(int i = 1; i <= n; ++i)
puts("NO");
return 0;
}
for(int j : factor[i])
l[j] = max(l[j], l[i] + 1);
}
for(int i = 1; i <= 2 * m; i += 2)
for(int j = l[i]; j <= r[i]; ++j)
ans[i << j] = 1;
for(int i = 1; i <= n; ++i)
puts(ans[a[i]] ? "Yes" : "No");
return 0;
}