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

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

2020-03-22

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;
}