操作が「Euclid の互除法」っぽくなっている系の問題！！！そういう系の問題は次の一覧で示してる

問題概要

$N$ 個の正の整数 $A_{1}, \dots, A_{N}$ に対して次の操作を繰り返し行う。

$N$ 個の整数の最大値を $X$ 、最小値を $x$ とする。
$X = x$ なら手続きを終了し、そうでなければ $X$ が書かれたカードをすべて $X−x$ が書かれたカードに変える

この問題の制約下で、いずれ手続きが終了することが証明できる。手続き終了後の数値を求めよ。

制約

$1 \le N \le 10^{5}$
$1 \le X_{i} \le 10^{9}$

考えたこと

まず $N = 2$ の場合を考える。このとき、たとえば $A = (15, 54)$ とすると

54 を 54 - 15 = 39 に置き換えて (15, 39) となる
39 を 39 - 15 = 24 に置き換えて (15, 24) となる
24 を 24 - 15 = 9 に置き換えて (15, 9) となる
15 を 15 - 9 = 6 に置き換えて (6, 9) となる
9 を 9 - 6 = 3 に置き換えて (6, 3) になる
6 を 6 - 3 = 3 に置き換えて (3, 3) になる

という具合に、答えは 3 になる。上記の手続きを振り返ると、そもそも最初に 54 を 15 で割ったあまりで置き換えていることがわかる。このような操作は Euclid の互除法の各ステップとみなせる。よって最終的に生成される整数は「最大公約数」となる。

一般の N の場合

一般の $N$ であっても、まず次のことがいえる。

「操作を行なっても、 $N$ 個の整数の最大公約数は不変である」

これは

${\rm GCD}(a, b) = {\rm GCD}(a - b, b)$

であることからわかる。よって、シミュレーション終了時の値が「最大公約数」となることがわかった。計算量は $O(N \log A)$ となる。

なお、シミュレーションがかならず終了することは次のようにしてわかる。

とならない限り、0 が生成されることはない
- したがって $N$ 個の整数の総和は $N$ 以上の範囲を動く
操作を行うたびに「 $N$ 個の整数の総和」は減少する

ことから、無限回の操作を行うことはできず、いつかは操作が終了する。

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

long long GCD(long long a, long long b) {
    if (b == 0) return a;
    else return GCD(b, a % b);
}

int main() {
    int N;
    cin >> N;
    long long res = 0;
    for (int i = 0; i < N; ++i) {
        long long A; cin >> A;
        res = GCD(res, A);
    }
    cout << res << endl;
}

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

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

AtCoder ARC 105 B - MAX-=min (灰色, 300 点)

問題概要

制約

考えたこと

一般の N の場合