AtCoder Regular Contest 048 C: 足の多い高橋君

問題

C: 足の多い高橋君 - AtCoder Regular Contest 048 | AtCoder

解法

AtCoder Regular Contest 048

コード

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

typedef long long ll;

const int MOD = 1e9 + 7;

ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll modpow(ll x, ll e) {
  ll ret = 1;
  ll cur = x;
  while (e) {
    if (e & 1) ret = (ret * cur) % MOD;
    cur = (cur * cur) % MOD;
    e >>= 1;
  }
  return ret;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N;
  cin >> N;
  vector<ll> l(N);
  for (int i = 0; i < N; ++i) cin >> l[i];
  sort(l.begin(), l.end());

  ll D = l[0];
  ll g = l[N - 1] - D;
  for (int i = 0; i < N; ++i) {
    if (l[i] - D > 0) g = gcd(g, l[i] - D);
  }
  ll a = (g + 1) / 2 + D;
  cout << modpow(2, a) << endl;
}