No.1711 Divide LCM
タグ : / 解いたユーザー数 14
作問者 :
chocorusk
👑
hitonanode
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もしくは右上の雲マークをクリックしてアカウントを作成してください。