题目描述

给定一个连续整数序列 $n, n+1, n+2, \dots, m$，反素数序列是指这些整数的一个排列，使得任意相邻的两个数之和均为合数（非素数）。例如，当 $n = 1$ 且 $m = 10$ 时，一个反素数序列为：

这是字典序最小的**$2$ 度反素数序列**。

进一步定义 $d$ 度反素数序列，要求所有长度为 $2, 3, \dots, d$ 的连续子序列之和均为合数。例如，上述序列是 $2$ 度的，但不是 $3$ 度的，因为子序列 $5, 4, 2$ 之和为 $11$（素数）。字典序最小的 $3$ 度反素数序列为：

输入格式

• 输入包含多组数据，每组数据为一行，包含三个整数 $n$、$m$ 和 $d$（$1 \leq n < m \leq 1000$，$2 \leq d \leq 10$）。
• 输入以 0 0 0 结束，该行不需处理。

输出格式

对于每组输入：

• 如果存在符合条件的序列，输出字典序最小的逗号分隔的整数序列（不带空格）。
• 如果不存在，输出：

  No anti-prime sequence exists.
  

样例输入

1 10 2
1 10 3
1 10 5
40 60 7
0 0 0

样例输出

1,3,5,4,2,6,9,7,8,10
1,3,5,4,6,2,10,8,7,9
No anti-prime sequence exists.
40,41,43,42,44,46,45,47,48,50,55,53,52,60,56,49,51,59,58,57,54

解题思路

关键观察

1. 素数判定：需要快速判断一个数是否为素数（可用筛法预处理）。
2. 回溯法：尝试构造字典序最小的排列，每一步检查是否满足所有子序列和均为合数。
3. 剪枝优化：在构造过程中，如果当前部分序列不满足条件，立即回溯。

算法步骤

1. 预处理素数表：使用埃拉托斯特尼筛法标记 $2$ 到 $2000$ 的素数（因为 $d \leq 10$，最大子序列和不超过 $10 \times 1000 = 10000$）。
2. 回溯构造序列：
   • 从最小字典序开始尝试。
   • 每次添加一个数时，检查所有长度 $\leq d$ 的新子序列和是否为合数。
3. 输出结果：找到第一个合法序列或判定无解。

代码实现（C++）

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 1010;
 
bool Prime[MAXN*10],vis[MAXN];
int Ans[MAXN];
int N,M,D;
 
void IsPrime()
{
    Prime[0] = Prime[1] = false;
    for(int i = 2; i < MAXN*10; ++i)
        Prime[i] = true;
    for(int i = 2; i < MAXN*10; ++i)
        if(Prime[i])
            for(int j = i+i; j < MAXN*10; j+=i)
                Prime[j] = false;
}
 
int Judge(int Cnt,int Value)
{
    int sum,ValueLeft;
    ValueLeft = Cnt - D + 1;
    if(ValueLeft < 0)
        ValueLeft = 0;
    sum = Value;
    for(int i = Cnt-1; i >= ValueLeft; i--)
    {
        sum += Ans[i];
        if(Prime[sum])  //连续2、3、…、D个数的和都为素数才满足
            return false;
    }
    return true;
}
int Dfs(int Cnt)
{
    if(Cnt == M-N+1)
        return true;
    for(int i = N; i <= M; ++i)
    {
        if(!vis[i] && Judge(Cnt,i))
        {
            Ans[Cnt] = i;
            vis[i] = true;
            if(Dfs(Cnt+1))
                return true;
            vis[i] = false;
        }
    }
    return false;
}
 
int main()
{
    IsPrime();
    while(~scanf("%d%d%d",&N,&M,&D) && (N||M||D))
    {
        memset(vis,0,sizeof(vis));
        if(Dfs(0))
        {
            for(int i = 0; i <= M-N; ++i)
                if(i != M-N)
                    printf("%d,",Ans[i]);
                else
                    printf("%d\n",Ans[i]);
        }
        else
            printf("No anti-prime sequence exists.\n");
    }
 
    return 0;
}

复杂度分析

• 时间复杂度：最坏情况下为 $O((m-n)!)$，但实际因剪枝优化远小于该值。
• 空间复杂度：$O(m-n)$，用于存储当前序列和标记数组。

示例解释

• 输入 1 10 2：$2$ 度反素数序列，任意相邻两数和为合数。
• 输入 1 10 3：$3$ 度反素数序列，任意连续 $2$ 或 $3$ 数和为合数。
• 输入 1 10 5：无解，因为无法满足更高度的约束。
• 输入 40 60 7：$7$ 度反素数序列，所有长度 $\leq 7$ 的子序列和均为合数。

题意分析

题目要求我们找到由连续整数 n, n+1, ..., m 组成的一个排列，使得该排列满足以下条件：

1. 对于所有长度为 2, 3, ..., d 的连续子序列，这些子序列的和都是合数（非素数）。
2. 如果存在多个满足条件的排列，输出字典序最小的那个。

如果不存在这样的排列，则输出 No anti-prime sequence exists.。

解题思路

1. 素数预处理：首先需要预处理出一定范围内的素数，以便快速判断一个数是否为素数。这里使用埃拉托斯特尼筛法（筛法）来标记素数和非素数。
2. 深度优先搜索（DFS）：使用DFS来尝试构建满足条件的序列。DFS的过程中需要维护当前的序列状态，并确保每一步的选择都满足条件。
   • 剪枝：为了提高效率，需要在DFS中进行剪枝。具体来说，每次选择一个数加入序列时，需要检查所有新生成的子序列的和是否为合数。如果发现不满足条件，则立即回溯。
   • 字典序最小：为了确保找到的序列是字典序最小的，DFS时应从小到大尝试数字。
3. 子序列和检查：对于当前序列的每一个新加入的数字，需要检查所有可能的子序列的和（从长度为2到长度为d）是否为合数。

复杂度分析

• 素数预处理：使用筛法预处理素数的时间复杂度是 O(N log log N)，其中 N 是预处理的数的上限（这里是112345）。
• DFS：DFS的时间复杂度取决于搜索空间的大小。最坏情况下，需要尝试所有可能的排列，即 O((m - n + 1)!)。但由于 m - n + 1 最大为1000，这在实践中是不可行的。因此，需要通过剪枝来减少搜索空间。
  • 实际运行时间取决于输入的具体情况。对于较小的 d 和较小的 m - n + 1，DFS可以较快找到解；但对于较大的 d 或较大的 m - n + 1，DFS可能会超时或无法找到解。

代码实现

#include <cstdio>
#include <cstring>

#define N 112345

int n, m, len;
int a[N];
bool vis[N];
bool mark[N];

// 筛法预处理素数
void sieve() {
    for (int i = 0; i < N; ++i) {
        mark[i] = true;
    }
    mark[0] = mark[1] = false;
    for (int i = 2; i * i <= N; ++i) {
        if (mark[i]) {
            for (int j = i * i; j < N; j += i) {
                mark[j] = false;
            }
        }
    }
}

// DFS尝试构建序列
bool dfs(int pos, int temp[]) {
    if (pos == m - n + 1) {
        return true; // 找到一个合法序列
    }
    for (int i = n; i <= m; ++i) {
        if (!vis[i]) {
            // 检查所有可能的子序列和
            bool valid = true;
            int new_temp[15] = {0};
            new_temp[1] = i;
            for (int j = 2; j <= len; ++j) {
                if (temp[j - 1] == 0) {
                    new_temp[j] = 0;
                    continue;
                }
                new_temp[j] = temp[j - 1] + i;
                if (mark[new_temp[j]]) {
                    valid = false;
                    break;
                }
            }
            if (!valid) {
                continue;
            }
            a[pos] = i;
            vis[i] = true;
            if (dfs(pos + 1, new_temp)) {
                return true;
            }
            vis[i] = false;
        }
    }
    return false;
}

int main() {
    sieve();
    while (scanf("%d%d%d", &n, &m, &len) == 3 && n) {
        memset(vis, 0, sizeof(vis));
        int temp[15] = {0};
        if (dfs(0, temp)) {
            for (int i = 0; i < m - n; ++i) {
                printf("%d,", a[i]);
            }
            printf("%d\n", a[m - n]);
        } else {
            printf("No anti-prime sequence exists.\n");
        }
    }
    return 0;
}