自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:12:12，当前版本为作者最后更新于2019-10-02 19:28:42，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

$\color{orange}T1.\ Escape$

$\color{orange}\text{题面}$

官方题解

结论水题，部分分留给你们瞎打的（逃

结论：设所有的可行步数为 $b_1,b_2, \dots ,b_x$

• 如果 $gcd(b_1,b_2,\dots,b_x,n)=1$，则答案为 $n$

• 否则不可行，输出 $-1$

---

注意到 $k\leq n$ 而不是 $k<n$

如果 $n=k$，那么答案肯定是 $-1$

看看你有没有特判下面这组数据

input
1
1 1
1
output
-1

---

解析：

设 $d=gcd(b_1,b_2,\dots,b_x,n)$

• 如果 $d>1$，易知不可能完成，即只能跳到编号为 $d$ 的倍数的平台

易知 “如果有一个 $b_i$ 与 $n$ 互质，就可以用 $n$ 步跳遍所有平台”

现在需要证明 "如果 $d=1$，则一定能走遍所有平台，且步数为 $n$”

（注：以下为这道题目结论的证明，并不是的真正实现方法）

---

设 $d_1=gcd(b_1,n)$

如果 $d_1=1$，则可以完成任务（跳 $n$ 次即可）

否则只能跳到 编号是 $d_i$ 倍数的平台上

接下来是很重要的一点！

• 如果我们能跳到 $mod\ d_1=1$ 的任意一个平台，$mod\ d_1=2$ 的任意一个平台，$\dots$，$mod\ d_1=d_1-1$ 的任意一个平台，那么我们就能跳到所有平台

因为如果你跳到了任意一个 $mod\ d_1=i$ 的平台上，那么你就能跳到 所有 $mod\ d_1=i$ 的平台上(每次跳 $b_1$ 个)

例如 $b_1=3,b_2=4,n=12$

跳 $4$ 步 $3\ ->0,3,6,9,pos=0\ (0\ mod\ 3=0)$

跳 $1$ 步 $4\ ->0,3,4,6,9,pos=4\ (4\ mod\ 3=1)$

跳 $3$ 步 $3\ ->0,1,3,4,6,7,9,10,pos=1$

跳 $1$ 步 $4\ ->0,1,3,4,5,6,7,9,10,pos=5\ (5\ mod\ 3=2)$

跳 $3$ 步 $3\ ->0,1,2,3,4,5,6,7,8,9,10,11,pos=2$

这样，问题就从原来的

$b_1,b_2,b_3,\dots,b_x$ 遍历所有 $n$

被简化成了 $b_2,b_3,\dots,b_x$ 遍历所有 $d_1$

又因为 $d=1$，所以 必定有一次 $gcd(b_i,d_{i-1})=1$，于是就能完成任务啦 $qwq$

---

有了结论，代码可好打了：

/*
DO NOT CHEAT!
author : Alex_Wei 
time : 2019.9.13
language : C++
*/
#include<bits/stdc++.h> 
using namespace std;
/*
快读 
inline void read(int &x)
{
	x=0;char s=getchar();
	while(!isdigit(s))s=getchar();
	while(isdigit(s))x=(x<<1)+(x<<3)+s-'0',s=getchar();
}
*/
int t,a[19260817];
bool pd[19260817];
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
int main()
{
	scanf("%d",&t);
	for(int l=0;l<t;l++){
		int n,k,d;
		scanf("%d%d",&n,&k),d=n;
		for(int i=1;i<=k;i++)
			scanf("%d",&a[i]),pd[a[i]]=1;//标记一下
		if(n==1&&k==1){cout<<"-1\n",pd[1]=0;continue;}//特判 n=k=1 的情况
		for(int i=1;i<=n;i++)
			if(!pd[i])//如果可以走，求 gcd
				d=gcd(d,i);
		if(d>1)cout<<"-1\n";//d>1 
		else cout<<n<<endl;
		for(int i=1;i<=k;i++)
			pd[a[i]]=0;//取消标记，不然 memset （可能会）超时
	}
	return 0;
}