P10183 Running 题解

T_TLucas_Yin · 2024-02-25 19:19:06 · 题解

公路跑拉爆全班。

时间距离公式：

转换一下：

我们可以把每个商店到起点的距离看成一个 s_i，这样就可以通过一个固定的速度 v 计算到每个商店所用的时间 t_i。

到每个商店的时间都是整数，所以对于每个 1\le i\le n，s_i 是速度 v 的倍数。换句话说，v 是所有 s_i 的公因数。

速度尽可能大。所以 v 是所有 s_i 的最大公因数。

但是在这种情况下，所有 s_i 与 v 的商肯定不能都再包含一个公因数 2，否则要使得 v 为它们的最大公因数，v 实际应该为 2v。也就是说，此时的 t_i 肯定不全为偶数，不符合要求。

再看一眼公式，若等式右边的分母 v 缩小的原来的 \frac 1 2，则分数值扩大 2 倍，等式左边同样 \times2。

现在时间 t_i 肯定是偶数了（因数 2 都摆外边了）。

综上，算出到每个商店的距离的最大公因数后，除以 2，所得的商就是答案。如果除法后变成了小数，就说明无解。

#include<bits/stdc++.h>
using namespace std;
long long n,a[2000005],sum=0;
long long gcd(long long a,long long b){
    if(b==0) return a;
    else return gcd(b,a%b);
}
int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++) sum=gcd(min(sum,a[i]),max(sum,a[i]));
    if(sum%2==0) printf("%lld",sum>>1);//通过余数判断有无解
    else printf("-1");
    return 0;
}