题解：P15032 [UOI 2021 II Stage] 棋子

· · 题解

P15032 [UOI 2021 II Stage] 棋子题解

此题不难，核心：最大步长 = 所有距离差的最大公约数。

关键思路

设每个点与起点的距离差为 d_i = |a_i - x|， 要访问点 i，需要 k \mid d_i（k 整除 d_i）， 要访问所有点，需要 k \mid \gcd(d_1, d_2, \dots, d_n)，最大 k 就是这个最大公约数本身。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll n,x;
ll a[100005];
int main(){
    cin>>n>>x>>a[1];
    a[1]=llabs(a[1]-x);
    for(int i=2;i<=n;++i)cin>>a[i],a[i]=llabs(a[i]-x),a[i]=__gcd(a[i-1],a[i]);
    cout<<a[n];
    return 0;
}