AtCoder题解｜ABC 109B Skip

题目信息 📚

【题目描述】

There are $N$ cities on a number line. The $i$-th city is located at coordinate $x_i$.

Your objective is to visit all these cities at least once.

In order to do so, you will first set a positive integer $D$.

Then, you will depart from coordinate $X$ and perform Move 1 and Move 2 below, as many times as you like:

Move 1: travel from coordinate $y$ to coordinate $y + D$.
Move 2: travel from coordinate $y$ to coordinate $y - D$.

Find the maximum value of $D$ that enables you to visit all the cities.

Here, to visit a city is to travel to the coordinate where that city is located.

【输入】

The input is given from Standard Input in the following format:

$N$ $X$

$x_1$ $x_2$ $\ldots$ $x_n$

【输出】

Print the maximum value of $D$ that enables you to visit all the cities.

【数据范围】

$1 \leq N \leq 10^5$
$1 \leq X \leq 10^9$
$1 \leq x_i \leq 10^9$
$x_i$ are all different.
$x_1, x_2, …, x_N \neq X$

【输入样例1】

3 3
1 7 11

【输出样例1】

Setting $D=2$ enables you to visit all the cities as follows, and this is the maximum value of such $D$:

Perform Move 2 to travel to coordinate $1$.
Perform Move 1 to travel to coordinate $3$.
Perform Move 1 to travel to coordinate $5$.
Perform Move 1 to travel to coordinate $7$.
Perform Move 1 to travel to coordinate $9$.
Perform Move 1 to travel to coordinate $11$.

【输入样例2】

3 81
33 105 57

【输出样例2】

【输入样例3】

1 1
1000000000

【输出样例3】

999999999

【题目来源】

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

题目解析 🍉

【题目分析】

求出 X 与所有点距离（abs(a[i] - X)）的最大公约数即可。

【C++代码】

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
LL n, x, tmp, cnt, d;

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    cin >> n >> x;
    for (int i = 1; i <= n; i++) {
        cin >> tmp;
        d = __gcd(d, abs(tmp - x));  // 求距离的最大公约数
    }
    cout << d << endl;

    return 0;
}