問題一覧 > 通常問題

No.1083 余りの余り

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 286
作問者 : tyawanmusityawanmusi / テスター : CleyLCleyL
55 ProblemId : 3822 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-11-11 00:26:02

問題文

長さ $N$ の正整数列 $A$ と整数 $K$ があります。$A$ の $i(1 \le i \le N)$ 番目の要素は $A_i$ です。

茶碗蒸しくんは、次の操作を行います。

  • $A$ を自由に並び替える。
  • $X = K\ \mathrm{mod}\ A_1\ \mathrm{mod}\ A_2\ \mathrm{mod}\ A_3\ \dots \mathrm{mod}\ A_N$ を求める。

$X$ の最大値を求めてください。

制約

  • $1 \le N \le 20$
  • $1 \le K \le 10^9$
  • $1 \le A_i \le 10^9$
  • $N, K, A_i$ は整数

入力

$N\ K$
$A_1\ A_2\ \dots\ A_N$

$1$ 行目には $N, K$ が空白区切りで入力されます。$2$ 行目には $A$ が空白区切りで入力されます。

出力

$X$ の最大値を1行に出力してください。最後に改行してください。

サンプル

サンプル1
入力
3 100
11 13 17
出力
9

$A$ の並び替え方としては、$(11,13,17),(11,17,13),(13,11,17),(13,17,11),(17,11,13),(17,13,11)$ があります。

このうち、 $A$ が $(13,11,17)$ のときに $X = 100\ \mathrm{mod}\ 13\ \mathrm{mod}\ 11\ \mathrm{mod}\ 17\ = 9$ となり、これが最大値となります。

また、$A$ が $(13,17,11)$ のときにも $X = 9$ となります。

サンプル2
入力
5 100
1 1 1 1 1
出力
0

どのように $A$ を並び替えても $X=0$ となります。

サンプル3
入力
8 93871
47 36 12 71 79 85 81 74
出力
9

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