# Codeforces - 1166E - The LCMs Must be Large

## 地址

http://codeforces.com/contest/1166/problem/E

## 原文地址

https://www.lucien.ink/archives/434

## 题目

Dora the explorer has decided to use her money after several years of juicy royalties to go shopping. What better place to shop than Nlogonia?

There are $n$ stores numbered from $1$ to $n$ in Nlogonia. The $i$-th of these stores offers a positive integer $a_i$.

Each day among the last $m$ days Dora bought a single integer from some of the stores. The same day, Swiper the fox bought a single integer from all the stores that Dora did not buy an integer from on that day.

Dora considers Swiper to be her rival, and she considers that she beat Swiper on day $i$ if and only if the least common multiple of the numbers she bought on day $i$ is strictly greater than the least common multiple of the numbers that Swiper bought on day $i$.

The least common multiple (LCM) of a collection of integers is the smallest positive integer that is divisible by all the integers in the collection.

However, Dora forgot the values of $a_i$. Help Dora find out if there are positive integer values of $a_i$ such that she beat Swiper on every day. You don't need to find what are the possible values of $a_i$ though.

Note that it is possible for some values of $a_i$ to coincide in a solution.

## 题解

$$LCM(D_i) > LCM(S_i) = LCM(D_j) > LCM(S_j) = LCM(D_i)$$

$$LCM(D_i) > LCM(S_i) \ge LCM(D_j) > LCM(S_j) \ge LCM(D_i)$$

2019年5月22日补充

$m$ 的范围只有 $50$ ，所以直接 $O(nm^2)$ 暴力判断一下即可。

### 代码

https://pasteme.cn/8174

#include <bits/stdc++.h>
const int maxm = 57, maxn = int(1e4) + 7;
int m, n;
bool vis[maxm][maxn];
int main() {
scanf("%d%d", &m, &n);
for (int i = 1, cnt, buf; i <= m; i++) {
scanf("%d", &cnt);
while (cnt--) scanf("%d", &buf), vis[i][buf] = true;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= m; j++) {
bool flag = false;
for (int k = 1; k <= n && !flag; k++) {
if (vis[i][k] && vis[j][k]) flag = true;
}
if (!flag) return 0 * puts("impossible");
}
}
puts("possible");
return 0;
}