😽

AGC 018 | A - Getting Difference

2020/12/19に公開

競プロ

tech

問題

解法

前提として操作のあとは操作した2つの数より小さい値しかでてこない。よって $K$ がどの $A_i$ より大きい場合はそもそもできない。

ここで、入力例1の9と4を例にして操作が実際どのようになるか見てみる。

見たことのある操作だが、GCD(最小公約数)を出す操作と同じである。すべての $A_i$ に対して最小公約数をもとめるとこの値が操作してできる一番小さい数である。

ここですべての $i$ に対して $A_i$ の最小公約数を $g$ とすると、 $A_i$ は $g \times x$ として表せる。よって、 $K$ が $g \times x$ として表せるなら $K$ を作ることは可能である。

コード

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

string ok = "POSSIBLE";
string ng = "IMPOSSIBLE";

ull gcd(ull a, ull b) {
  if (b == 0) {
    return a;
  } else {
    return gcd(b, a % b);
  }
}

int main() {
  ll n, k;
  cin >> n >> k;
  ll g;
  ll mx = 0;
  for (int i = 0; i < n; i++) {
    ll a;
    cin >> a;
    mx = max(a, mx);
    if (i == 0) {
      g = a;
    } else {
      g = gcd(a, g);
    }
  }
  if (mx < k) {
    cout << ng << endl;
    return 0;
  }
  if (k % g == 0) {
    cout << ok << endl;
    return 0;
  }
  cout << ng << endl;
}

AGC 018 | A - Getting Difference

問題

解法

コード

参考

Discussion