問題一覧 > 通常問題

No.2806 Cornflake Man

レベル : / AI推定難易度 : 1425 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 91
作問者 : kinugoshi8928 / テスター : Magentor highlighter hirayuu_yc keisuke6 silv723 Yoyoyo8128 zeta7532 fact493
お気に入りにしたユーザー ProblemId : 10996 / 自分の提出
問題文最終更新日: 2024-07-12 20:53:40
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 436 ('09 Contest 002 day1) (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。