Getting Difference [AtCoder Grand Contest 018 A]

http://agc018.contest.atcoder.jp/tasks/agc018_a

解法

http://agc018.contest.atcoder.jp/submissions/1445281
注意:この解法はエスパー解法です

色々試してみると、大体作れることが分かる。
作れない場合は以下の場合である

1. 最大値よりも大きい数は作れない
2. Kが全てのgcdで割り切れない

2番目の条件はサンプル2とサンプル4を見てみると、「3 6 9」「2 4 6 8 10」と意味深な数列になっていることからエスパー
既にあるかを先に確認して、あとは上記の二条件をチェックする。

int gcd(int a, int b) { return a ? gcd(b%a, a) : b; }
int N, K, A[101010];
//---------------------------------------------------------------------------------------------------
string ok = "POSSIBLE";
string ng = "IMPOSSIBLE";
string solve() {
    rep(i, 0, N) if (A[i] == K) return ok;
    int ma = A[N - 1];
    if (ma < K) return ng;
    
    int g = A[0];
    rep(i, 1, N) g = gcd(g, A[i]);
 
    if (g == 1) return ok;
    
    if (K % g == 0) return ok;
    return ng;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> A[i];
    sort(A, A + N);
 
    cout << solve() << endl;
}