自动搬运

查看原文

来自洛谷，原作者为

	diqiuyi heaksicn你真唐吧

搬运于2025-08-24 23:15:32，当前版本为作者最后更新于2025-05-07 18:44:11，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

先把 $ans=0$ 判了。

先给 $a$ 排个序，然后考虑 $\gcd$ 的性质，把 $a$ 替换成它的差分。这时候的操作相当于 $a_i\gets a_i+1,a_{i+1}\gets a_{i+1}-1$。这时候 $\sum a_i$ 是 $O(V)$ 的。

有这样的结论：我们只要找到两个非空的无交的子序列且它们的和相同，那么 $ans=1$。证明就是找到这两个子序列中最靠后的那个，利用操作把它 $+1$，此时的 $\gcd$ 已经是 $1$ 了。

由抽屉原理可知，当 $2^n>V$ 时，$ans=1$。

所以我们只要考虑 $n\le 23$ 的情况，这时候直接从小到大枚举答案然后爆搜即可，复杂度不是很清楚，反正跑得很快，也完全卡不满。（其实由于上面的分析，$n>23$ 时也可以直接爆搜，不过无所谓了。并且实测这个 $n$ 的上界看起来是 $\omega(n)$ 级别的）

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int p[1000005],n,g;
void dfs(int x,int y,int now,int g){
	if(x==n){
		if(__gcd(g,p[x]+y-now)==1) cout<<y<<'\n',exit(0);
		return ;
	}
	for(int i=0;i<=y-now;i++)
		dfs(x+1,y,now+i,__gcd(g,p[x]+i));
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>p[i],g=__gcd(g,p[i]);
	if(g==1) return cout<<"0\n",0;
	if(n>23) return cout<<"1\n",0;
	for(int i=1;;i++)
		dfs(1,i,0,0);
	return 0;
}