No.2806 Cornflake Man
タグ : / 解いたユーザー数 91
作問者 :
Magentor
highlighter
keisuke6
fact493
Problem Statement
A musician is performing a trick of playing several different rhythms at the same time.
The musician has a sequence of positive integers $B$ representing the rhythms being played.
On beat $i$, a sound is played if and only if $i$ is a multiple of some element of $B$.
From beat $0$ to beat $M$, the musician played a sound $N$ times.
You are given a sequence of positive integers $A$ recording all the beats on which a sound was played. Find, among all possible $B$, one with the fewest elements.
If none exists, report that.
Here, for any integer $x$, $0$ is a multiple of $x$.
Constraints
- $2 \leq N \leq 2 \times 10^{5}$
- $1\leq M \leq 10^{9}$
- $0 \leq A_i \leq M$
- $A_1 = 0$
- All elements of $A$ are distinct.
- All input values are integers.
Input
The input is given from standard input in the following format.
$N\ M$ $A_1\ A_2\ \dots\ A_N$
Output
If no possible $B$ exists, print only -1, followed by a newline.
If one exists, print $2$ lines.
On the $1$ line, print the minimum possible number of elements of $B$.
On the $2$ line, print a $B$ with the fewest elements among all possible ones, separated by spaces.
If there are multiple such $B$ with the fewest elements, print any of them.
Print $B$ sorted in ascending order of value.
Print a newline at the end.
Sample
Sample 1
Input
10 14 0 2 3 4 6 8 9 10 12 14
Output
2 2 3
Setting $B$ to 2 3 yields the input $A$.
Sample 2
Input
5 6 0 2 3 5 6
Output
-1
No $B$ can yield the input $A$.
Sample 3
Input
12 15 0 5 14 9 2 6 8 4 10 12 3 15
Output
3 2 3 5
The input $A$ may not be sorted in ascending order.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。