けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder AGC 018 A - Getting Difference (300 点)

操作の仕方が Euclid の互除法そのものになっているタイプの問題。

問題へのリンク

問題概要

素数  N の数列  A_{0}, \dots, A_{N-1} が与えられる。これに対して以下の操作を好きな回数だけ行うことができる:

  • 整数を 2 つ選び、その差の絶対値をとり、それを数列に新たに挿入する

整数  K を出現させられるかどうかを判定せよ。

制約

  •  1 \le N \le 10^{5}

考えたこと

「最大公約数」ん関する話題をこの記事に集大成した。

qiita.com

この中で、以下のような Euclid の互除法の原理を紹介した。

  • GCD(a, b) = GCD(a-b, b)

今回の操作はまさにこれっぽさがある。そして Euclid の互除法をシミュレートすることで、数列  A_{1}, A_{2}, \dots, A_{N-1} の最大公約数  g を作ることができる。

さらに  g の倍数のうち、 A の最大値以下のものはすべて作ることができる。 A の最大値より大きいものは作れない。

#include <bits/stdc++.h>
using namespace std;

long long GCD(long long x, long long y) {
    if (y == 0) return x;
    return GCD(y, x%y);
}

int main() {
    int N;
    long long K;
    cin >> N >> K;
    long long ma = 0, g = 0;
    for (int i = 0; i < N; ++i) {
        long long a; cin >> a;
        ma = max(ma, a);
        g = GCD(g, a);
    }
    if (K <= ma && K % g == 0) cout << "POSSIBLE" << endl;
    else cout << "IMPOSSIBLE" << endl;
}