素数环 题解

题目描述

输入正整数n，把整数1，2，3，…，n组成一个环，使得相邻两个整数之和均为素数。为了阻止大家打表，需要把全部的解按字典序排序后，从1开始编号，依次输出指定编号的k组解。最后一行输出总的方案数。同一个素数环只算一次。

输入格式

第1行：2个整数，n(n<=18) 和 k(1<=k<=10)

第2行：共有k个从小到大排列的整数，表示要输出的解的编号。

输出格式

前k行，每行一组解，对应于一个输入。

第k+1行：一个整数，表示总的方案数。

#include 
using namespace std;
const int MAXN = 40;
bool p[MAXN], vis[MAXN];
int a[MAXN], b[MAXN], n, ans = 0, k, cnt = 1;

bool prime(int x) {
	for(int i = 2; i <= sqrt(x); i ++) {
		if(x % i == 0) return 0;
	}
	return 1;
}

void dfs(int i) {
	if(i > n) {
		if(p[a[n] + a[1]] == 1) {
			ans ++;
			if(ans == b[cnt]) {
				cnt ++;
				for(int j = 1; j <= n; j ++) {
					printf("%d ", a[j]);
				}
				printf("n");
			}
		}
		return;
	}
	for(int j = 1; j <= n; j ++) {
		if(!vis[j] && p[j + a[i - 1]]) {
			vis[j] = 1;
			a[i] = j;
			dfs(i + 1);
			vis[j] = 0;
		}
	}
}

int main() {
	scanf("%d %d", &n, &k);
	for(int i = 2; i <= n * 2; i ++) p[i] = prime(i);
	for(int i = 1; i <= k; i ++) scanf("%d", &b[i]);
	a[1] = 1;
	vis[1] = 1;
	dfs(2);
	printf("%d", ans);
	return 0;
}