問題一覧 > 通常問題

No.1711 Divide LCM

レベル : / AI推定難易度 : 2450 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 14
作問者 : chineristAC / テスター : chocorusk 👑 hitonanode
お気に入りにしたユーザー ProblemId : 6803 / 自分の提出
問題文最終更新日: 2025-02-02 01:52:36
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 318 (順位表) の他の問題:

Problem Statement

For a non-empty set $S$ of positive integers, let $\mathrm{LCM}(S)$ denote the least common multiple of all elements contained in $S$.

You are given $N$ pairwise distinct positive integers $A_i\ (1\le i \le N)$. Let $S$ be the set $S=\{A_1,\ A_2,\ \dots,\ A_N \}$.

Find the minimum $k$ for which there exists a tuple of $k$ non-empty sets $S_1,\ S_2,\ \dots,\ S_k$ satisfying the following conditions, and for that $k$, construct $S_1,\ S_2,\ \dots,\ S_k$ satisfying the conditions.

If no such $k$ exists, output $-1$.

Conditions

  • The union of $S_i\ (1\le i \le k)$ is equal to the set $S$.
  • If $i\neq j$, the intersection of $S_i,\ S_j$ is the empty set.
  • For $1\le i \le k$, $\mathrm{LCM}(S_i) \neq \mathrm{LCM}(S)$ holds.

In this problem, instead of $A_i$, the number of distinct prime factors $m_i$ of $A_i$ and the prime factorization $A_i=p_{i1}^{e_{i1}}p_{i2}^{e_{i2}}\dots p_{im_{i}}^{e_{i{m_i}}}$ are given as input.

Input

$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$
  • The sum of $m_i\ (1\le i \le N)$ is at most $2\times 10^{5}$.
  • $p_{ij}$ is a prime number not exceeding $10^6$.
  • If $j\neq k$, then $p_{ij}\neq p_{ik}$.
  • $1\le e_{ij}$
  • If $i\neq j$, then $A_i \neq A_j$.
  • All input values are integers.

Output

If there is no $k$ for which a tuple of $S_i\ (1\le i \le k)$ satisfying the conditions exists, output only $-1$.

Otherwise, output the minimum $k$ on the $1$st line, and, with $n_i=|S_i|$, output $S_i\ (1\le i \le k)$ from the $2$nd line onward in the following format.

If multiple tuples of $S_i\ (1\le i \le k)$ satisfy the conditions, you may output any of them.

Also, the elements $S_{i1},\ S_{i2},\ \dots,\ S_{in_i}$ of $S_i$ may be output in any order.

$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}$

Print a newline at the end.

Sample

Sample 1
Input
3
1
3 1
1
2 2
1
7 1
Output
2
2 3 4
1 7

We have $A_1=3^1=3,\ A_2=2^2=4,\ A_3=7^1=7$.

For $k=1$, there is clearly no tuple of $S_i$ satisfying the conditions.

For $k=2$, taking $S_1=\{3,\ 4\},\ S_2=\{7\}$ gives $\mathrm{LCM}(S_1)=12,\ \mathrm{LCM}(S_2)=7$ while $\mathrm{LCM}(S)=84$, so the conditions are satisfied.

Therefore, output as shown above.

Outputting, for example, $S_{1}=\{3,\ 7\},\ S_{2}=\{4\}$ is also judged as correct.

Sample 2
Input
4
2
2 1
3 2
3
2 1
3 2
5 1
2
2 2
3 2
2
2 2
5 1
Output
3
2 18 90
1 20
1 36

We have $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$.

For $k=2$, for example, taking $S_1=\{18,\ 36\},\ S_2=\{90,\ 20\}$ gives $\mathrm{LCM}(S)=\mathrm{LCM}(S_2)=180$, so the conditions are not satisfied.

There are several other ways to divide into $2$ sets, but none of them satisfies the conditions.

Sample 3
Input
3
1
2 1
1
3 1
2
2 1
3 1
Output
-1

We have $A_1=2^1=2,\ A_2=3^1=3,\ A_3=2^1 \times 3^1=6$.

Since $\mathrm{LCM}(S)=6$ and any set containing $A_3=6$ always has $\mathrm{LCM}(S_i)=6$, there is no $k$ for which $S_i\ (1\le i \le k)$ satisfying the conditions exists.

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