No.1083 Remainder of Remainder
タグ : / 解いたユーザー数 300
作問者 :
tyawanmusi
/ テスター :
👑 
CleyL
Problem Statement
You are given a sequence $A$ of positive integers of length $N$ and an integer $K$. The $i(1 \le i \le N)$-th element of $A$ is $A_i$.
Chawanmushi-kun performs the following operations.
- Rearrange $A$ freely.
- Compute $X = K\ \mathrm{mod}\ A_1\ \mathrm{mod}\ A_2\ \mathrm{mod}\ A_3\ \dots \mathrm{mod}\ A_N$.
Find the maximum value of $X$.
Constraints
- $1 \le N \le 20$
- $1 \le K \le 10^9$
- $1 \le A_i \le 10^9$
- $N, K, A_i$ are integers
Input
$N\ K$
$A_1\ A_2\ \dots\ A_N$
The first line $1$ contains $N, K$ separated by spaces. The second line $2$ contains $A$ separated by spaces.
Output
Print the maximum value of $X$ on one line. End the output with a newline.
Sample
Sample 1
Input
3 100
11 13 17
Output
9
The possible rearrangements of $A$ are $(11,13,17),(11,17,13),(13,11,17),(13,17,11),(17,11,13),(17,13,11)$.
Among these, when $A$ is $(13,11,17)$, we get $X = 100\ \mathrm{mod}\ 13\ \mathrm{mod}\ 11\ \mathrm{mod}\ 17\ = 9$, which is the maximum value.
Also, when $A$ is $(13,17,11)$, we also get $X = 9$.
Sample 2
Input
5 100
1 1 1 1 1
Output
0
No matter how $A$ is rearranged, $X=0$.
Sample 3
Input
8 93871
47 36 12 71 79 85 81 74
Output
9
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。