题意:输入m, n, d。
求出m,m+1,m+2,````m+n的一个排列。使得任意的连续k个数之和都为合数,2<=k<=d。
题解:暴力,依次枚举第一个数,第二个数····,第n-m+1个数。
#include<cstdio> #include<memory> #include<cstring> using namespace std; const int N = 1005; bool p[N*10], used[N]; // p[0] = false 表示素数 int m, n, d, set[N]; void prime () { memset(p,0,sizeof(p)); p[0] = p[1] = 1; for ( int i = 2; i <= 100; i++ ) { if ( p[i] ) continue; for ( int j = 2; i * j < 10001; j++ ) p[i*j] = 1; } } bool judge ( int index, int value ) { if ( index == 0 ) return true; int left = index - d + 1; if ( left < 0 ) left = 0; int sum = value; for ( int i = index-1; i >= left; i-- ) { sum += set[i]; if ( ! p[sum] ) return false; } return true; } bool dfs ( int index ) { if ( index == n - m + 1 ) return true; for ( int i = m; i <= n; i++ ) { if ( !used[i] && judge(index,i) ) { set[index] = i; used[i] = true; if ( dfs(index+1) ) return true; used[i] = false; } } return false; } int main() { prime(); while ( 1 ) { scanf("%d%d%d",&m,&n,&d); if ( m + n + d == 0 ) break; memset(used,0,sizeof(used)); if ( dfs(0) ) { for ( int i = 0; i < n-m; i++ ) printf("%d,",set[i]); printf("%d\n",set[n-m]); } else printf("No anti-prime sequence exists.\n"); } return 0; }