自动搬运

查看原文

来自洛谷，原作者为

	3350218411ouL **

搬运于2025-08-24 22:27:36，当前版本为作者最后更新于2021-01-26 20:29:00，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

我们可以先分类讨论一下。

两个素数$x$和$y$，其必有两种情况——两个奇数和一奇一偶。

首先来说两个奇数的情况，题目让我们找一些素数使相邻两数之差为素数，而两个奇数之差只能为偶数，即两数之差为2时，$x$与$y$可通。

再说一奇一偶的情况，因为2是唯一的偶素数，所以$x$与$y$中一定有一个为2，假定$x$为2，那么$y$与2的差为素数时，$x$与$y$可通。

我们可以用深搜来枚举以上的所有情况，但既然是要判断素数，自然少不了素数筛子，注意数据范围已经超过了int的最大范围，因此要开long long。

素数筛子：

bool is_prime(long long x){
	if(x==1) return false; //1既不是素数，也不是合数 
	if(x==2) return true; //2是素数 
	if(x%2==0) return false; //但2的倍数不是素数 
	for(long long i=3;i*i<=x;i+=2) //标准素数筛子，但注意数据范围 
		if(x%i==0)
			return false;
	return true; //剩下的必为素数 
}

接下来是最核心的DFS代码，若前面的分析没看懂的可看此处：

void dfs(long long x,long long y,int t){
	if(flag) return; //搜到可行方案就直接返回 
	if(is_prime(abs(x-y))){ //搜到了可行方案 
    	cout<<t+1<<endl; 
		//因为在上一层递归中总方案数为t+2，所以在本层中为t+1 
    	cout<<a<<" ";
    	for(int i=1;i<t;i++) cout<<ans[i]<<" ";
    	cout<<b<<endl;
    	flag=true; //标志已搜到可行方案 
    	return;
	}
	if(x!=2) //两个奇数的情况 
		for(int i=1;i<=3;i++){
			if(i==1&&is_prime(x-2)){ 
				ans[t]=2; //记录方案 
				dfs(2,y,t+1);
			} 
			//将其中一个奇数变为偶数，即变为2 
			if(i==2&&is_prime(x-2)){ 
				ans[t]=x-2;
				dfs(x-2,y,t+1);
			}
			//将其中一个奇数减2，使两个奇数差为2 
			if(i==3&&is_prime(x+2)){
				ans[t]=x+2;
				dfs(x+2,y,t+1);
			}
			//将其中一个奇数加2，使两个奇数差为2
		}
	else{ //一奇一偶的情况 
		if(is_prime(y+2)){
			ans[t]=y+2;
			dfs(y+2,y,t+1);
		}
		//将2变为与另一个奇数相差2的奇数 
	}
	return; //搜索结束 
}

最后再上一遍完整的AC代码：

#include<bits/stdc++.h> //万能头文件 
using namespace std;
long long ans[50]; //记录方案的数组 
long long a,b,n=2;
bool flag;
bool is_prime(long long x){ //素数筛子 
	if(x==1) return false;
	if(x==2) return true;
	if(x%2==0) return false;
	for(long long i=3;i*i<=x;i+=2)
		if(x%i==0)
			return false;
	return true;
}
void dfs(long long x,long long y,int t){ //深搜
	if(flag) return; 
	if(is_prime(abs(x-y))){
    	cout<<t+1<<endl; 
    	cout<<a<<" ";
    	for(int i=1;i<t;i++) cout<<ans[i]<<" ";
    	cout<<b<<endl;
    	flag=true;
    	return;
	}
	if(x!=2)
		for(int i=1;i<=3;i++){
			if(i==1&&is_prime(x-2)){ 
				ans[t]=2;
				dfs(2,y,t+1);
			} 
			if(i==2&&is_prime(x-2)){ 
				ans[t]=x-2;
				dfs(x-2,y,t+1);
			}
			if(i==3&&is_prime(x+2)){
				ans[t]=x+2;
				dfs(x+2,y,t+1);
			}
		}
	else{
		if(is_prime(y+2)){
			ans[t]=y+2;
			dfs(y+2,y,t+1);
		}
	}
	return;
}
void inp(){
	cin>>a>>b; //输入
	return;
}
void work(){
    if(is_prime(abs(a-b))){ //特判，若a和b可达，直接输出 
    	cout<<n<<endl<<a<<" "<<b;
    	return;
	}
    dfs(a,b,1); //因为输出方案时i从1开始，所以t从1开始 
    if(!flag) cout<<"-1"; //若没搜到，输出-1 
	return;
}
int main(){
	ios::sync_with_stdio(false); //输入输出流加速代码 
	inp();
	work();	
	return 0; //代码结束 
}

以上是本蒟蒻的第一份题解，若有错误，请大佬指正，谢谢。

感谢bowlder_lover的提醒，有一段代码是多余的，现已修正。