Skip [AtCoder Beginner Contest 109 C]

https://beta.atcoder.jp/contests/abc109/tasks/abc109_c

前提知識

• GCD

考察過程

1. Dを固定すると、行ける座標と行けない座標が定まってしまう
2. 細かく言うと、X = y mod Dであるyしか行けなくなる
3. よって、X%D=x[0]%D=x[1]%D=...=x[N-1]%Dを満たす最大のDであることが求められる。
4. 変形して0 = (x[0]-X)%D=...=(x[N-1]-X)%D
5. よって、x[0]-X, ..., x[N-1]-Xが全てDの倍数である必要がある
6. x[0]-X,...,x[N-1]-Xの共通の約数で最大のものを求めたい → 最大公約数
7. gcdは効率のいい求め方があるので、それで求めると答え

解法

https://beta.atcoder.jp/contests/abc109/submissions/3165135

理屈は考察過程の通り。
x[i]-Xのgcdを取ると答え。
x[i]-Xは負の数になる可能性があるので、absを渡す。
（なぜこれでOKなのかは実際分かってないけど）

int N, X, x[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> X;
    rep(i, 0, N) cin >> x[i];
 
    int ans = 0;
    rep(i, 0, N) ans = gcd(ans, abs(x[i] - X));
    cout << ans << endl;
}