問題一覧 > 通常問題

No.1083 余りの余り

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 175
作問者 : tyawanmusityawanmusi / テスター : luckylatluckylat
36 ProblemId : 3822 / 出題時の順位表
問題文最終更新日: 2020-06-20 05:41:52

お知らせ(6/20 4:12)

チャレンジがあり、いくつか提出が落ちました。

問題文

要素数$N$の正整数列$A$と整数$K$があります。$A$の$i(1 \le i \le N)$番目の要素は$A_i$です。
茶碗蒸しくんは、次の操作を行います。

  • $A$を自由に並び替える。
  • $X = K\ mod\ A_1\ mod\ A_2\ mod\ A_3\ \dots 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\ mod\ 13\ mod\ 11\ 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もしくは右上の雲マークをクリックしてアカウントを作成してください。