Logfiles

AGC018: A - Getting Difference

AGC

問題

A - Getting Difference

回りくどい解説

2つのボールからはじめて、できるだけ小さい値のボールを作ろうと思う。例として (16, 6) を考える。 16 - 6 = 10 となり、更に小さい値を作るには、10 - 6 = 4 である。これは、16 - 2 * 6 = 4 (16 ÷ 6 = 2 あまり 4) をしている。更に小さい値を作るには 6 - 4 = 2 をする (6 ÷ 4 = 1 あまり 2)

割れるだけ割る操作を、商とあまりを利用して繰り返すため、ユークリッド互除法を行っている。このとき、2つの数から作ることのできる最も小さい数は、最大公約数である。 $N$ 個の数の最大公約数を取ると、減算できる値の最小値がわかる。

入力の数列に $K$ が含まれないとき、 $K$ を作るためには $K$ より大きい数が数列に含まれている必要があることはすぐわかる。減算できる値の最小値＝最大公約数 $G$ を用いて、 $K$ より大きい値 $M$ から減算によって $K$ が作れれば良い。作れる値は [tex:[M-G, M-2G, M-3G, ..., 0]] であり、この数列上に $K$ が含まれている必要がある。（最小値でない作ることのできる値と最小値との最大公約数は、最小値に一致することに注意する）すなわち、 $K$ は $G$ の倍数である必要がある。 $M$ は数列の最大値のみ考えれば良い。

参考

上の解説読むより、以下の記事を一読したほうが良いです。

拡張ユークリッドの互除法〜一次不定方程式 ax + by = c の解き方〜

コード

#define OK { cout << "POSSIBLE\n"; exit(0); }
#define NG { cout << "IMPOSSIBLE\n"; exit(0); }

int main() {
  int N, K; cin >> N >> K;
  vector<unsigned> a(N); cin >> a;
  if (N == 1 && a[0] == K) OK;
  unsigned g = a[0];
  REP(i, 1, N) {
    if (a[i] == K) OK;
    g = __gcd(g, a[i]);
  }
  if (*max_element(a.begin(), a.end()) > K && K % g == 0) OK;
  NG;
}