[AtCoder] ARC 105 B – MAX-=min

2020年10月12日2020年12月12日

問題

方針

シミュレーション

カードの置き換えは全ての \( X \) に対して行われるので、セットを用います。セットは順序付きなので、最小値 \( x \) と最大値 \( X \) の取得を高速にできます。このとき、セットから \( X \) を消去します。ある操作で、\( X \bmod x = 0 \) であるとき、最大値 \( X \) を \( x \) とさせることができます。\( X \) に対して、操作 2. を連続して行っても、最小値は変化しないので、\( X \) を \( x \) にすることができます。\( X \bmod x \neq 0 \) であるとき、操作 2. を連続して行うと、\( X \) が  \( X \bmod x \) となったとき、最小値が \( x = X \bmod x \) と更新されるので、セットに \( X \bmod x \) を追加し、操作 2. を行います。

最大公約数

自然数 \( a \leq b\) の最大公約数を \( g(a, b) \) とすると、\( g(a, b) = g(a, b – a) \) が成り立ちます。したがって、配列 \( a \) の最大公約数が答えとなります。逆に、配列 \( a \) の最大公約数を \( b \) とすると、\( a_i \bmod b = 0 \) より、\( a_i = b \) とすることができます。

コード

シミュレーション

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

int main() {
    int N;
    cin >> N;
    int a[N];
    set<int> s;
    for (int i = 0; i < N; i++) {
        cin >> a[i];
        s.insert(a[i]);
    }
    while (s.size() != 1) {
        int X = *s.rbegin();
        int x = *s.begin();
        s.erase(X);
        if (X % x != 0) {
            s.insert(X % x);
        }
    }
    cout << *s.begin() << "\n";
    return 0;
}

最大公約数

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

ll gcd(ll m, ll n) {
  if (n == 0) return m;
  else return gcd(n, m % n);
}

int main() {
    int N;
    cin >> N;
    int a[N];
    ll g = 0;
    for (int i = 0; i < N; i++) {
        cin >> a[i];
        g = gcd(g, a[i]);
    }
    cout << g << "\n";
    return 0;
}