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

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

AtCoder AGC 018 A - Getting Difference (緑色, 300 点)

AtCoder AtCoder300点 AGC-A 数学(整数問題) 数列 操作がEuclidの互除法に対応 最大公約数 操作 操作を好きな回数だけ行える Yes/No判定問題 考察：不変量に着目する 緑色diff 隣接2要素に制約や目的関数のある問題 操作:2つのものから新たに1つのものを挿入 絶対値やminを扱う問題

操作の仕方が 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;
}