自动搬运

查看原文

来自洛谷，原作者为

	System_Error_ @jiazhichen844 的小号

搬运于2025-08-24 22:55:30，当前版本为作者最后更新于2024-01-27 18:28:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

subtask 1：

超市只有 $1$ 个，所以找到一个速度使得到达这个超市的时间为 $2$ 秒即是最大速度，即最大速度为 $\frac{a_1}{2}$，判断速度是否为整数，是则输出速度，否则无解。

代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a;
int n;
int main() {
	cin>>n>>a;
	if(a%2==0) cout<<a/2;
	else cout<<-1;
	return 0;
}

subtask 2：

显而易见，$v$ 一定小于等于 $a_1$，而 $a_1 \le 2\times10^6$，所以枚举 $v$ 即可，判断到达超市的时间是不是偶数，总时间复杂度 $O(a_1n)$。

代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[55];
signed main() {
	cin>>n;
	for(int i=1; i<=n; i++) cin>>a[i];
	for(int i=a[1]; i>=1; i--) {
		bool f=true;
		for(int j=1; j<=n; j++) 
			if(a[j]%i||a[j]/i%2) f=false;
		if(f) {
			cout<<i;
			return 0;
		} 
	}
	cout<<-1;
	return 0;
}

subtask 3：

在枚举 $v$ 的过程中，如果 $v \nmid a_1$，那么到达第一个超市的时间就不是整数，所以我们就可以只枚举 $a_1$ 的因数，这样就保证了到达第一个超市的时间为整数，总时间复杂度 $O(n\tau(a_1))$，$\tau(a_1)$ 是指 $a_1$ 的正因子个数。

代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[10005],ans=-1;
bool check(int x) {
	for(int i=1; i<=n; i++)
		if(a[i]%x||a[i]/x%2) return false;
	return true;
}
signed main() {
	cin>>n;
	for(int i=1; i<=n; i++) cin>>a[i];
	for(int i=sqrt(a[1]); i>=1; i--) {
		if(a[1]%i==0) {
			if(check(i)) ans=max(ans,i);
			if(check(a[1]/i)) ans=max(ans,a[1]/i);
		}
	}
	cout<<ans;
	return 0;
}

subtask 4：

我们先不管必须在偶数时间经过这个条件，要求出一个 $v$ 使得每次到达某个超市时时间是整数，就要保证 $v \mid a_i$，所以 $v$ 就是所有 $a_i$ 的公因数，最大的 $v$ 就是所有 $a_i$ 的最大公因数。

求出 $v$ 后可以证明至少有一个超市到达时间是奇数，原因是如果每个超市到达时间都是偶数，那么所有的 $a_i$ 除以 $v$ 后还至少有 $2$ 这个公因子，不符合 $v$ 是最大公因数的定义。

接着再看偶数时间经过这个条件，把 $v$ 除以 $2$ 后到达每个超市的时间会多一倍，所以这样就保证了到达时间为偶数，注意：如果 $2 \nmid v$，则 $v$ 除以 $2$ 后不是整数，不符合题意，输出无解，时间复杂度为 $O(n \log V)$。

相信聪明的你一定看得懂简单的代码。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e6+5;
int n,a[N];
signed main() {
	cin>>n;
	for(int i=1; i<=n; i++)
		cin>>a[i];
	int v=a[1];
	for(int i=2; i<=n; i++)
		v=__gcd(v,a[i]);
	if(v%2==1) cout<<-1;
	else cout<<v/2;
	return 0;
}