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

· · 题解

P15032 [UOI 2021 II Stage] 棋子 题解

题目传送门

题目描述

近日，哥萨克胡子发现了一枚棋子以及位于同一条直线上的 n 个点。棋子的初始坐标为 x，第 i 个点的坐标为 a_i。

哥萨克胡子可以首先选择任意一个正整数 k。之后，他可以任意多次地改变棋子的坐标，为其加上或减去 k，也就是说，将棋子向任意一侧移动距离 k。

哥萨克胡子想知道：在 k 最大为多少时，棋子能够访问所有给定的 n 个点。

输入格式

第一行包含两个整数 n 和 x (2 \le n \le 10^5, -10^{18} \le x \le 10^{18}) —— 分别表示直线上的点数以及棋子的初始坐标。

第二行包含 n 个整数 a_1, a_2, \dots, a_n (-10^{18} \le a_i \le 10^{18}) —— 点的坐标。保证数组 a 中的所有数两两不同。

输出格式

输出一个数字 —— 棋子能够访问所有 n 个给定点的最大 k 值。

做法分析

棋子能到 a_i 的条件是 (a_i-x) 是 k 的倍数。

要让所有点到达，需满足 k 是 a 数组中所有元素的最大公因数。

代码

#include<bits/stdc++.h>
#define endl '\n'
#define kuaitou ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define baoliu(n) fixed<<setprecision(n)
#define int long long
using namespace std;
signed main(){
    kuaitou;
    int n,x;//定义变量
    cin>>n>>x;//输入
    int a[n+1]={};//定义数组
    int ans=0;//定义答案
    for(int i=1;i<=n;i++){//遍历数组
        cin>>a[i];//输入
        ans=__gcd(ans,abs(a[i]-x));//是ans是最大公因数
    }
    cout<<ans;//输出
    return 0;//完结散花
}

AC记录