AtCoder ABC 109 C - Skip (茶色, 300 点)

一瞬「訪れる順番によって状況が変わらないか...」と不安になるかもな問題だけど、よく考えたら訪れる順番を考える必要もない。ソートしても OK だけどソートする必要はなかった。

問題へのリンク

問題概要

個の点が一直線上に並んでいて、各頂点の座標は である。今、 から出発してすべての頂点に行くことを考える。以下の条件を満たすような最大の整数 を求めよ:

• から出発して以下の操作を好きなだけ行い、各座標に一度以上ピッタリと止まることが可能である
  • 現在地を として に移動する
  • 現在地を として に移動する

制約

• 

考えたこと

とりあえず で出発という条件を

• から出発して , , ..., をめぐる

という風にしても特に変わらないので、そうする。こうすると、何度移動を繰り返しても、

• たどり着く場所の座標は必ず の倍数
• 逆に の倍数の地点には必ずたどり着ける

ということがわかる。したがって必要十分条件は、

• は の約数
• ...
• は の約数

となること、すなわち、

• は の約数

となることがわかる。よって最大値は になる。

#include <iostream>
#include <vector>
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; long long X;
    cin >> N >> X;
    vector<long long> x(N); for (int i = 0; i < N; ++i) cin >> x[i], x[i] -= X;
    long long g = abs(x[0]);
    for (int i = 0; i < N; ++i) g = GCD(g, abs(x[i]));
    cout << g << endl;
}