P10183

zhangshengzhe1 · 2024-07-01 20:54:33 · 题解

首先我们看题意。

题目说了，给出一条直线上的 n 个坐标，你需要给出一个速度 v，使得经过每个坐标时都刚好花费偶数单位的时间，最大化这个速度。

我们先简化一下题意：不要求偶数单位的时间，只要求整数单位的时间。

那么，如果经过一个坐标a[i] 时时间为整数，那么a[i]必然是v 的倍数，或者说 v 是a[i]的因数。

同时满足所有的a[i]的v，就是{a[1],a[2],...,a[n]}的公因数。因为题目要求最大化该速度，那我们就求出a序列的最大公因数。

问题来了：如何使经过每个坐标刚好花费偶数时间呢？

其中 t 是时间，s 是路程，v 是速度。

如果要使 t 绝对成为一个偶数，我们将其乘上二即可。 所以我们求出序列 a 的最大公因数后，将其除以二就能得到答案了。

Code Time

本题代码实现其实不难。我求最大公因数的 gcd() 函数是自己手写的辗转相除法，读者也可以采用内置的 __gcd() 函数来完成。

#include<bits/stdc++.h>
#define int long long
using namespace std;

int n,a,g;
int gcd(int x,int y){
return y?gcd(y,x%y):x;
}

signed main()
{
    scanf("%lld",&n);
    while(n--)
    {
        scanf("%lld",&a);
        g = gcd(g,a);
    }
    if(g%2) printf("-1");
    else printf("%lld",g/2);
    return 0;
}