题目描述
输入正整数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;}