😽

AGC 018 | A - Getting Difference

1 min read

問題

https://atcoder.jp/contests/agc018/tasks/agc018_a

解法

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

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

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

ここですべてのiに対してA_iの最小公約数をgとすると、A_ig \times xとして表せる。よって、Kg \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;
}

参考

https://atcoder.jp/contests/agc018/tasks/agc018_a/editorial

Discussion

ログインするとコメントできます