这道题COCI的竞赛题。我的代码在本地运行时,可通过官网提供的全部31组数据,但是我在洛谷提交时却老是不通过 求大佬帮我看一下是哪出了问题
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
long long i;
long long left_border,right_border;//left和right分别表示序列的左右边界(即刚开始输入的两数)
int sign;//sign用于标记是否找到解
long long sequence[50];//数组sequence用于记录可能要输出的序列
int if_prime_number(long long x)//判定x是否为质数
{
long long i;
if(x<=1)//0和1都不是质数
{
return 0;//返回假值
}
if(x==2)
{
return 1;
}
if(x%2==0)
{
return 0;
}
for(i=3;i*i<=x;i+=2)
{
if(x%i==0)
{
return 0;
}
}
return 1;//返回真值
}
int DFS(long long insert_num,long long right_num,long long t)//insert_num表示当前要插入序列的数,right_num就是right_border
{//t表示当前要插入第几个数
int a,b;
if(sign)//sign=1表示已经找到可行解,此时不需继续搜索,直接返回
{
return 1;
}
sequence[t]=insert_num;//printf("sequence[%I64d]=%I64d\n",t,sequence[t]);
if(if_prime_number(abs(insert_num-right_num)))//要插入的质数与左边数的差已经是质数,若其与右界的差也是质数,则说明已找到可行序列
{
sign=1;//将标记赋为真值
printf("%I64d\n",t+1);//输出序列元素数目
for(i=1;i<=t;i++)
{
printf("%I64d ",sequence[i]);
}
printf("%I64d",right_num);
return 1;
}
if(insert_num!=2)//若本次要插入的数不是2,则inser_num是奇质数.
{
a=if_prime_number((insert_num+2));
if(a)//当这两个奇质数之间的差值要为质数时,这个差值只能为2
{
DFS(insert_num+2,right_border,t+1);
}
a=if_prime_number((insert_num-2));
if(a)//当这两个奇质数之间的差值要为质数时,这个差值只能为2
{//若inser_num与2的差值为质数
DFS(2,right_border,t+1);//则尝试下一次插入2
DFS(insert_num-2,right_border,t+1);//则尝试下一次插入insert_num-2
}
}
else//若本次要插入的数是2
{
a=if_prime_number((right_num+2));
if(a)
{
DFS(right_num+2,right_border,t+1);
}
a=if_prime_number((right_num-2));
b=if_prime_number((right_num-4));
if(a&&b)
{
DFS(right_num-2,right_border,t+1);
}
}
return 0;
}
int main()
{
//输入数据
scanf("%I64d%I64d",&left_border,&right_border);
//搜索
DFS(left_border,right_border,1);
//输出结果
if(!sign)//
{
printf("-1");
return 0;
}
return 0;
}