[AGC018A] Getting Difference
题意翻译
已知集合 $A$ 有 $n$ 个数字。你可以将集合 $A$ 中任意两个数的差的绝对值加入集合 $A$,并且你可以做任意次数该操作。
请问能否在集合 $A$ 中出现 $K$。有解输出 `POSSIBLE`,无解输出 `IMPOSSIBLE`.
题目描述
[problemUrl]: https://atcoder.jp/contests/agc018/tasks/agc018_a
箱に $ N $ 個のボールが入っていて、$ i $ 番目のボールには整数 $ A_i $ が書かれています。 すぬけ君は、次の操作を好きな回数だけ行うことができます。
- 箱から二つのボールを取り出し、その二つのボールに書かれている数の差の絶対値を書いた新しいボールと一緒に箱に戻す。
すぬけ君が、整数 $ K $ の書かれたボールが箱の中に入っている状態にできるかどうか判定してください。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ K $ $ A_1 $ $ A_2 $ $ ... $ $ A_N $
输出格式
すぬけ君が、整数 $ K $ がかかれたボールが箱の中に入っている状態にできる場合には `POSSIBLE`、 できない場合には `IMPOSSIBLE` と出力せよ。
输入输出样例
输入样例 #1
3 7
9 3 4
输出样例 #1
POSSIBLE
输入样例 #2
3 5
6 9 3
输出样例 #2
IMPOSSIBLE
输入样例 #3
4 11
11 3 7 15
输出样例 #3
POSSIBLE
输入样例 #4
5 12
10 2 8 6 4
输出样例 #4
IMPOSSIBLE
说明
### 制約
- $ 1\ \leq\ N\ \leq\ 10^5 $
- $ 1\ \leq\ A_i\ \leq\ 10^9 $
- $ 1\ \leq\ K\ \leq\ 10^9 $
- 入力はすべて整数である。
### Sample Explanation 1
まず、$ 9 $ と書かれたボールと $ 4 $ と書かれたボールを取り出し、$ abs(9-4)=5 $ なので、$ 5 $ と書かれた新しいボールと一緒に箱に戻します。 次に、$ 3 $ と書かれたボールと $ 5 $ と書かれたボールを取り出し、$ abs(3-5)=2 $ なので、$ 2 $ と書かれた新しいボールと一緒に箱に戻します。 最後に、$ 9 $ と書かれたボールと $ 2 $ と書かれたボールを取り出し、$ abs(9-2)=7 $ なので、$ 7 $ と書かれた新しいボールと一緒に箱に戻します。 $ 7 $ と書かれたボールを箱に入れることができたので、この例の答えは `POSSIBLE` になります。
### Sample Explanation 2
どれだけ操作を行っても、$ 5 $ の書かれたボールを箱の中に入れることはできません。 よってこの例の答えは、`IMPOSSIBLE` になります。
### Sample Explanation 3
操作を行うまでもなく、箱の中には $ 11 $ の書かれたボールが入っています。 よってこの例の答えは、`POSSIBLE` になります。