問題一覧 > 通常問題

No.1711 Divide LCM

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 16
作問者 : chineristACchineristAC / テスター : chocoruskchocorusk 👑 hitonanodehitonanode
3 ProblemId : 6803 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-10-15 00:38:23

問題文

正整数からなる空でない集合 $S$ に対し $\mathrm{LCM}(S)$ で $S$ が含むすべての要素の最小公倍数を表すものとします。

$N$ 個の互いに相異なる正整数 $A_i\ (1\le i \le N)$ が与えられます。集合 $S$ を $S=\{A_1,\ A_2,\ \dots,\ A_N \}$ と置きます。

以下の条件を満たす $k$ 個の空でない集合の組 $S_1,\ S_2,\ \dots,\ S_k$ が存在するような最小の $k$ を求め、そのような $k$ に対し条件を満たす $S_1,\ S_2,\ \dots,\ S_k$ を構築してください。

そのような $k$ が存在しない場合は $-1$ と出力してください。

条件

  • $S_i\ (1\le i \le k)$ の和集合は集合 $S$ に等しい
  • $i\neq j$ ならば $S_i,\ S_j$ の積集合(共通部分)は空集合
  • $1\le i \le k$ に対し、 $\mathrm{LCM}(S_i) \neq \mathrm{LCM}(S)$ が成り立つ。

この問題では $A_i$ の代わりに $A_i$ の素因数の種類数 $m_i$ と素因数分解 $A_i=p_{i1}^{e_{i1}}p_{i2}^{e_{i2}}\dots p_{im_{i}}^{e_{i{m_i}}}$ が入力で与えられます。

入力

$N$
$m_1$
$p_{11}$ $e_{11}$
$p_{12}$ $e_{12}$
$\vdots$
$p_{1m_1}$ $e_{1m_1}$
$m_2$
$p_{21}$ $e_{21}$
$p_{22}$ $e_{22}$
$\vdots$
$p_{2m_2}$ $e_{2m_2}$
$\vdots$
$m_N$
$p_{N1}$ $e_{N1}$
$p_{N2}$ $e_{N2}$
$\vdots$
$p_{Nm_N}$ $e_{Nm_N}$

  • $1\le N \le 10^5$
  • $2\le A_i \le 10^{9}$
  • $A_i=p_{i1}^{e_{i1}}p_{i2}^{e_{i2}}\dots p_{im_{i}}^{e_{i{m_i}}}$
  • $1\le m_i$
  • $m_i\ (1\le i \le N)$ の総和は $2\times 10^{5}$ 以下
  • $p_{ij}$ は $10^6$ 以下の素数
  • $j\neq k$ ならば $p_{ij}\neq p_{ik}$
  • $1\le e_{ij}$
  • $i\neq j$ ならば $A_i \neq A_j$
  • 与えられる入力はすべて整数

出力

条件を満たす $S_i\ (1\le i \le k)$ の組が存在するような $k$ が存在しない場合は $-1$ とだけ出力してください。

存在する場合は $1$ 行目に最小の $k$ を出力し、 $n_i=|S_i|$ として、 $2$ 行目以降に以下の形式で $S_i\ (1\le i \le k)$ について出力してください。

条件を満たす $S_i\ (1\le i \le k)$ の組が複数存在する場合はいずれを出力してもかまいません。

また、 $S_i$ の要素 $S_{i1},\ S_{i2},\ \dots,\ S_{in_i}$ についてはどのような順序で出力してもかまいません。

$k$
$n_1$ $S_{11}$ $S_{12}$ $\dots$ $S_{1n_1}$
$n_2$ $S_{21}$ $S_{22}$ $\dots$ $S_{2n_2}$
$\vdots$
$n_k$ $S_{k1}$ $S_{k2}$ $\dots$ $S_{kn_k}$

最後に改行してください。

サンプル

サンプル1
入力
3
1
3 1
1
2 2
1
7 1
出力
2
2 3 4
1 7

$A_1=3^1=3,\ A_2=2^2=4,\ A_3=7^1=7$ です。

$k=1$ のとき、明らかに条件を満たす $S_i$ の組は存在しません。

$k=2$ の場合は $S_1=\{3,\ 4\},\ S_2=\{7\}$ とすると $\mathrm{LCM}(S)=84$ に対し $\mathrm{LCM}(S_1)=12,\ \mathrm{LCM}(S_2)=7$ となるので条件を満たします。

よってこのように出力します。

$S_{1}=\{3,\ 7\},\ S_{2}=\{4\}$ などとして出力しても正答となります。

サンプル2
入力
4
2
2 1
3 2
3
2 1
3 2
5 1
2
2 2
3 2
2
2 2
5 1
出力
3
2 18 90
1 20
1 36

$A_1=2^1 \times 3^2 = 18,\ A_2=2^1 \times 3^2 \times 5^1 = 90,\ A_3=2^2\times 3^2=36,\ A_4=2^2\times 5^1=20$ です。

$k=2$ としたとき、例えば $S_1=\{18,\ 36\},\ S_2=\{90,\ 20\}$ とすると $\mathrm{LCM}(S)=\mathrm{LCM}(S_2)=180$ となり条件を満たしません。

ほかにも $2$ つの集合に分ける方法はいくつかありますが、いずれも条件を満たしません。

サンプル3
入力
3
1
2 1
1
3 1
2
2 1
3 1
出力
-1

$A_1=2^1=2,\ A_2=3^1=3,\ A_3=2^1 \times 3^1=6$ です。

$\mathrm{LCM}(S)=6$ であり、 $A_3=6$ を含む集合は必ず $\mathrm{LCM}(S_i)=6$ となるので条件を満たす $S_i\ (1\le i \le k)$ が存在するような $k$ はありません。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。