No.2806 Cornflake Man
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 85
作問者 :
kinugoshi8928
/ テスター :
Magentor
highlighter
hirayuu_yc
keisuke6
silv723
Yoyoyo8128
zeta7532
fact493
タグ : / 解いたユーザー数 85
作問者 :
![Magentor](https://pbs.twimg.com/profile_images/1715389554197495808/7HlNzj_p.jpg)
![highlighter](https://pbs.twimg.com/profile_images/1707374069132439552/b_BWx6c8.png)
![keisuke6](https://pbs.twimg.com/profile_images/1675785204974354432/k3Bvkvyj.jpg)
![fact493](https://pbs.twimg.com/profile_images/1641449306531192836/GjfyenV1.jpg)
問題文最終更新日: 2024-07-12 20:53:40
問題文
ミュージシャンが、異なるいくつかのリズムを同時に奏でる芸を披露しています。
ミュージシャンは自分が奏でているリズムの正整数列 $B$ を持っています。
$i$ 拍子目では、$i$ が $B$ の要素のどれかの倍数の時、またその時に限り音を鳴らします。
ミュージシャンは $0$ 拍子目から $M$ 拍子目の間に $N$ 回音を鳴らしました。
音を鳴らした拍子全てが記録された正整数列 $A$ が与えられるので、$B$ としてありうる中で要素数が一番少なくなるものを求めてください。
存在しない場合は、そのことを報告してください。
ただし、任意の整数 $x$ に対して、$0$ は $x$ の倍数です。
制約
- $2 \leq N \leq 2 \times 10^{5}$
- $1\leq M \leq 10^{9}$
- $0 \leq A_i \leq M$
- $A_1 = 0$
- $A$ の要素はすべて相違なる
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
$N\ M$ $A_1\ A_2\ \dots\ A_N$
出力
ありうる $B$ が存在しない場合、 -1
とだけ出力し、最後に改行してください。
存在する場合、$2$ 行出力してください。
$1$ 行目には、$B$ としてありうる最小の要素数を出力してください。
$2$ 行目には、ありうる中で要素数が一番少なくなる $B$ を空白区切りで出力してください。
ありうる中で要素数が一番少なくなる $B$ が複数ある場合、そのうちのどれかを出力してください。
$B$ は値の昇順にソートした形で出力してください。
最後に改行してください。
サンプル
サンプル1
入力
10 14 0 2 3 4 6 8 9 10 12 14
出力
2 2 3
$B$ を 2 3
とすることで入力の $A$ になります。
サンプル2
入力
5 6 0 2 3 5 6
出力
-1
どのような $B$ でも、入力の $A$ にすることはできません。
サンプル3
入力
12 15 0 5 14 9 2 6 8 4 10 12 3 15
出力
3 2 3 5
入力の $A$ は昇順にソートされていない場合もあります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。