Submission #19563865

---

Source Code Expand

#include <bits/stdc++.h>
#define repr(i, a, b) for (int i = a; i < b; i++)
#define rep(i, n) for (int i = 0; i < n; i++)
#define reprrev(i, a, b) for (int i = b - 1; i >= a; i--) // [a, b)
#define reprev(i, n) reprrev(i, 0, n)
#define _GLIBCXX_DEBUG
#define int long long 
using ll = long long;
using ull = unsigned long long;
template <class T>
inline bool chmax(T &a, T b)
{
  if (a < b)
  {
    a = b;
    return true;
  }
  return false;
}
template <class T>
inline bool chmin(T &a, T b)
{
  if (a > b)
  {
    a = b;
    return true;
  }
  return false;
}
const ll mod = 1e9 + 7;
void chmod(ll &M)
{
  if (M >= mod)
    M %= mod;
  else if (M < 0)
  {
    M += (abs(M) / mod + 1) * mod;
    M %= mod;
  }
}
ll modpow(ll x, ll n)
{
  if (n == 0)
    return 1;
  ll res = modpow(x, n / 2);
  if (n % 2 == 0)
    return res * res % mod;
  else
    return res * res % mod * x % mod;
}

int getl(int i, int N) { return i == 0 ? N - 1 : i - 1; };
int getr(int i, int N) { return i == N - 1 ? 0 : i + 1; };
long long GCD(long long a, long long b)
{
  if (b == 0)
    return a;
  else
    return GCD(b, a % b);
}

using namespace std;
signed main() {
  int n, x; cin >> n >> x;
  vector<int> X(n+1);
  rep(i, n) {
    cin >> X[i];
  }
  X[n] = x;
  sort(X.begin(), X.end());
  vector<int> res(n);
  rep(i, n) {
    res[i] = X[i+1] - X[i];
  }
  sort(res.begin(), res.end());
  int ans = res[0];
  for(auto x: res) {
    ans = GCD(ans, x);
  }
  cout << ans << endl;
  // if(n==1) {
  //   cout << abs(x-X[0]) << endl;
  //   return 0;
  // }
  // auto iter = lower_bound(X.begin(), X.end(), x);
  // if(iter == X.end()) {
  //   cout << abs(x-X[n-1]) << endl;
  //   return 0;
  // }
  // int ind = distance(X.begin(), iter);
  // int ans = min(abs(x-X[ind]), abs(x-X[ind-1]));
  // cout << ans << endl;
}
// int main() {
//   int n, m; cin >> n >> m;
//   vector<int> X(m);
//   rep(i, m) {
//     cin >> X[i];
//   }
//   sort(X.begin(), X.end());
//   vector<pair<int, int>> pr;
//   for(int i = 0; i < n-1; i++) {
//     int res = X[i+1] - X[i];
//     pr.emplace_back(res, i);
//   }
//   sort(pr.begin(), pr.end());
//   vector<bool> check(n);
//   if(n >= m) {
//     cout << 0 << endl;
//     return 0;
//   }
//   for(int i = 0; i < m; i++) {
//     check[pr[i].second] = true;
//   }
//   ll ans;
//   rep(i, n) {
//     if(pr[i].second==0) continue;
//     if(check[pr[i].second]=false) ans += pr[i-1].first;
//   }
//   cout << ans << endl;
// }

// int main() {
//   int n; cin >> n;
//   vector<ll> A(n); 
//   rep(i, n) {
//     cin >> A[i];
//   }
//   sort(A.begin(), A.end());
//   int ans = 0;
//   int res = A[0];
//   for(int i = 1; i < n; i++) {
//     res = GCD(res, A[i]);
//   }
//   ans = res;
//   cout << ans << endl;
// }
// int main() {
//   int H, W;
//   cin >> H >> W;
//   vector<vector<char>> c(H, vector<char>(W));
//   vector<vector<bool>> check(H, vector<bool>(W));

//   void search(int x, int y) {
//     if(x < 0 or W <= x or y < 0 or H <= y or c.at(y).at(x)=='#') {
//       return;
//     }

//     if(check.at(y).at(x)) return;
//     if(c.at(y).at(x)=='g') goal = true;

//     check.at(y).at(x)) = true;

//     // 4方向を試す
//     search(x+1, y);
//     search(x-1, y);
//     search(x, y+1);
//     search(x, y-1);

//   }

//   int sx, sy;
//   rep(i, H) {
//     rep(j, W) {
//       check.at(i).at(j) = false;
//       cin >> c.at(i).at(j);
//       if(c.at(i).at(j) == 's') sx = j, sy = i;
//     }
//   }

//   bool goal = false;



//   search(sx, sy);

//   if(goal) cout << "Yes" << "\n";
//   else cout << "No" << "\n";

// }






// int main() {
//   int n;
//   cin >> n;
  
//   vector<int> fib(n+1, 0);
//   rep(i, n+1) {
//     if(i == 0 or i == 1) fib.at(i) == 1;
//     else fib.at(i) = fib.at(i-1) + fib.at(i-2);
//   }
  
//   cout << fib.at(n) << endl;

// }



// vector<long long> divisor(long long n) {
//     vector<long long> ret;
//     for (long long i = 1; i * i <= n; i++) {
//         if (n % i == 0) {
//             ret.push_back(i);
//             if (i * i != n) ret.push_back(n / i);
//         }
//     }
//     sort(ret.begin(), ret.end()); // 昇順に並べる
//     return ret;
// }

// int main() {
//   long long N;
//   cin >> N;
//   divisor(N);
//   ll ans = 0;
//   rep(i, divisor(N).size()) {
//     ans += divisor(N).at(i);
//   }

//   cout << ans << "\n";
// }


// int main() {
//   struct Heap {
//     vector<int> heap;
//     Heap() {}

//     /*ヒープに値vを挿入*/
//     void push(int v) {
//       heap.push_back(v);
//       int i = (int)heap.size() - 1; //追加されたノード番号
//       while(i > 0) {
//         int p = (i - 1) / 2; //親のノード番号
//         if (heap.at(p) >= v) break; //逆転がなかったらループを抜ける
//         heap.at(i) = heap.at(p); //自分のノードを親の値にする
//         i = p;
//       }
//       heap.at(i) = v;
//     }

//     /* 最大値を知る */
//     int top() {
//       if(!heap.empty()) return heap.at(0);
//       else return -1; 
//     }

//     /* 最大値を知る */
//     void top() {
//       if (heap.empty()) return;
//       int v = heap.back();
//       heap.pop_back();
//       int i = 0;
//       while (i * 2 + 1 < (int)heap.size()) {
//         // 子供同士を比較して大きい方をchild1とする
//         int child1 = i * 2 + 1, child2 = i * 2 + 2;
        
//         if (child2 < (int)heap.size() && heap.at(child2) > heap.at(child1) child1 = child2;
//         if (heap.at(child1) <= v) break; //逆転がない場合は終了
//         heap.at(i) = heap.at(child1); //自分のノードを子供の値に
//         i = child1;
//     } 
//     heap.at(i) = v; //最終的なvの位置が確定
//     }
//   };


// int main()
// {
//   int N;
//   cin >> N;
//   vector<tuple<string, int, int>> R;
//   rep(i, N)
//   {
//     string S;
//     int a;
//     cin >> S >> a;
//     R.push_back(make_tuple(S, a, i));
//   }

//   sort(R.begin(), R.end());

//   for (tuple<string, int, int> r : R)
//   {
//     string s;
//     int q;
//     int ans;
//     tie(s, q, ans) = r;
//     cout << ans + 1 << endl;
//   }
// }
// }
// /* クイックソートの実装 */
// void Quicksort(vector<int> &a, int left, int right) {
//   //終了条件
//   if(right - left == 1) return;

//   //ピボットに中点を選ぶ
//   int pivot_index = (left - right) / 2;
//   int pivot = a.at(pivot_index)

//   //ピボットと右端を交換
//   swap(a.at(right-1), a.at(pivot_index));

//   //イテレータ
//   int i = left;

//   // [left, right)をループ
//   repr(j, left, right) {
//     //pivot未満のは左へ
//     if (a.at(j) < pivot) {
//       swap(a.at(i++), a.at(j));

//     } 
//   }
//   swap(a.at(i), a.at(j));

//   Quicksort(a, left, i);
//   Quicksort(a, i+1, right);

// }

// int main() {
//   int n;
//   cin >> n;
//   vector<int> a(n);
  
//   rep(i, n) cin >> a.at(i);
  
//   Quicksort(a, 0, n);

//   rep(i, n) printf("%d", a.at(i));
// }


// void Mergesort(vector<int> &a, int left, int right) {
//   if(right - left == 1) return;
//   int mid = left + (right-left)/2 ;

//   Mergesort(a, left, mid);
//   Margesort(a, mid, right);

//   vector<int> buf;
//   repr(i, left, mid) buf.push_back(a.at(i));
//   reprrev(i, mid, right) buf.push_back(a.at(i));

//   int iterator_left = 0;
//   int iterator_right = (int)buf.size();
//   repr(i, left, right) {
//     if(buf[iterator_left] <= buf[iterator_right]) {
//       a.at(i) = buf[iterator_left++];
//     }

//     else  {
//       a.at(i) = buf[iterator_right--];
      
//     }
//   }
//     int main() {
//       int n;
//       cin >> n;
//       rep(i, n) {
//         scanf("%d", &a.at(i));
//       }
//     Mergesort(a, 0, n);
    
//     }
//   }
// }
  


// int main()
// {
//   cin.tie(nullptr);
//   ios_base::sync_with_stdio(false);
//   string S;
//   cin >> S;
//   string T;
//   int N = S.length();
//   rep(i, N)
//   {
//     T.at(N - 1 - i) = S.at(i);
//   }
//   cerr << T << " " << S;

//   //元の文と回文に比較
//   int count = 0;
//   rep(i, N)
//   {
//     if (T.at(i) == S.at(i))
//       count++;
//   }

//   cout << count << endl;
// }

// int main()
// {
//   int N;
//   cin >> N;
//   vector<int> W(N);
//   rep(i, N)
//   {
//     cin >> W.at(i);
//   }
//   const int INF = 1e8;
//   vector<int> S(N + 1, 0);
//   rep(i, N) S.at(i + 1) = S.at(i) + W.at(i);
//   int ans = INF;
//   for (int i = 1; i < N - 1; i++)
//   {
//     int left, right;
//     left = S.at(i);
//     right = S.at(N) - S.at(i);
//     ans = min(ans, abs(right - left));
//   }
//   cout << ans << endl;
// }
// int main()
// {
//   cin.tie(nullptr);
//   ios_base::sync_with_stdio(false);
//   //入力
//   ll A, B, K;
//   cin >> A >> B >> K;

//   //食べた分枚数を減らしていく
//   for (ll i = 0; i < K; i++)
//   {
//     if (A != 0)
//       A--;
//     else if (B != 0)
//       B--;
//   }

//   cout << A << " " << B << endl;
// }

Submission Info

Judge Result