ABC 109 C問題

問題概要

数直線状に \(N\) 個の都市があり、\(i\) 番目の都市は、座標\(x_i\) にある。座標 \(X\) から出発し、全ての都市を訪れなければならない。移動方法は正整数Dを定めると次のとおりである。

  • 座標 \(y\) から座標 \(y+D\) に移動する
  • 座標 \(y\) から座標 \(y-D\) に移動する

全ての都市を１度以上訪れることのできるDの最大値を求めよ。

制約

  • 入力は全て整数
  • 1 ≤ \(N\) ≤ 105
  • 1 ≤ \(X\) ≤ 109
  • 1 ≤ \(x_i\) ≤ 109
  • \(x_i\) はすべて異なり、\(X\) とも異なる

考えたこと

全ての都市を訪問することのできる時の移動距離の最大値はどんな数かを考察すると、\(X\) と \(x_i\) との距離を考えた時に、その距離が \(D\) の整数倍になる \(D\) を求めることと一致する。

つまり、\(X\)と\(x_i\)の距離の最大公約数の最小値が\(D\)と一致する

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int main() {
  ll n, X; cin >> n >> X;
  vector<ll> x(n);
  for(ll i = 0; i < n; i++){
    cin >> x[i];
    x[i] = abs(x[i] - X);
  }
  ll ans = x[0];
  for(int i = 0; i < n-1; i++) {
    ans = min(ans, __gcd(x[i], x[i+1]));
  }
  cout << ans << endl;

  return 0;
}