cf1166 E. The LCMs Must be Large

题意：

有一个长度为 \(n\) 的未知正整数组，再给 \(m\) 个限制，每个限制会给一个位置集合 \(S\)，要求 \(S\) 中所有位置上的数的lcm 严格大于其余数的 lcm，问是否存在合法的数组

\(1\le m \le 50, 1\le n\le 1e4\)

思路：

若 \(i\neq j\) 且 $ S_i\cup S_j=\emptyset$，则 \(S_i\subseteq \overline{S_j}, S_j\subseteq \overline{S_i}\)，那么 \(lcm (S_i)\le lcm(\overline{S_j}),lcm (S_j)\le lcm(\overline{S_i})\)。而依题意有 \(lcm (\overline S_i) < lcm(S_i),lcm (\overline S_j) < lcm(S_j)\)，矛盾

所以任意两个不同的 \(S\) 一定要有交

考虑这样构造：初始化所有数为 \(1\)。对每个限制 \(S_i\)，令所有 \(a_j(j\in S_i)\) 乘上第 \(i\) 个质数 \(p_i\)

那么对所有 \(i\)，\(lcm (S_i)=\prod_{i=1}^m p_i\)。而 \(\overline{S_i}\) 一定没有 \(p_i\) 这个因子，所以 \(lcm(S_i)>lcm(\overline{S_i})\)

数据不大，\(O(m^2n)\) 暴力验证即可

const signed N = 5 + 1e4, M = 55;
int n, m; bool g[M][N];
void sol() {
    cin >> m >> n;
    for(int i = 1; i <= m; i++) {
        int s; cin >> s; while(s--) {
            int p; cin >> p; g[i][p] = true;
        }
    }

    for(int i = 1; i <= m; i++)
        for(int j = i+1; j <= m; j++) {
            bool fl = 0; for(int p = 1; p <= n; p++)
                if(g[i][p] && g[j][p]) fl = 1;
            if(!fl) return cout << "impossible", void();
        }

    cout << "possible";
}