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

· · 题解

题意简述

给定起点 m 和 n 个目标点 a_i。

每次可移动 \pm k，求最大 k 使得所有点可达

关键转化

首先考虑从m点开始，能到达的点的集合应该是 \{\, x + t \cdot k \mid t \in \mathbb{Z} \,\}。
要使点 a_i 可达，必须满足：

a_i \equiv x \pmod{k}

等价于：

k \mid (a_i - x)

因此，k 必须是所有 |a_i - x| 的公约数。
为使 k 最大，取最大公约数：

k = \gcd\big(|a_1 - x|,\ |a_2 - x|,\ \dots,\ |a_n - x|\big)

数学证明

设棋子初始位置为 x，目标点为 a_1, a_2, \dots, a_n。
若存在正整数 k 使得所有点均可到达，则对任意 i，有：

a_i \equiv x \pmod{k} \quad \Longleftrightarrow \quad k \mid (a_i - x)

即 k 是所有 |a_i - x| 的公约数。

反之，若 k 是这些差值的公约数，则从 x 出发每次移动 \pm k 必能到达每个 a_i。

因此，满足条件的 k 的集合恰好是：

\left\{ k \,\big|\, k\in \gcd\big(|a_1 - x|, |a_2 - x|, \dots, |a_n - x|\big) \,\right\}

故最大可能的 k 就是：

\gcd\big(|a_1 - x|,\ |a_2 - x|,\ \dots,\ |a_n - x|\big)

复杂度分析

时间复杂度：O(n\log{M}) M为数值大小
空间复杂度：O(n)

代码实现


#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
long long a[N];
int main(){
    int n;
    long long m;
    cin>>n>>m;
    long long ans;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]=abs(a[i]-m);
    }
    ans=a[1];
    for(int i=2;i<=n;i++) ans=__gcd(a[i],ans);
    cout<<ans;
    return 0;
}