18025 小明的密码

时间限制:4000MS  内存限制:65535K
提交次数:0 通过次数:0

题型: 编程题   语言: G++;GCC

Description

小明的密码由N（1<=N<=12）个数字构成，每个数字都可以是0至9中任意一个数字，但小明的密码还有
一个特点就是密码中连续的M（1<=M<=4）个数字的和是质数，现给定M和N，求满足条件的密码共有多少
个？

第1行是T，case数量，此后T行，每行两个数，N和M

每个case输出一个满足条件的密码总数

输入样例

2
1 1
2 1

输出样例

4
16

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <math.h>int X[40],A[12];
int count;void is_zhishu()
{int i,k,j;X[0]=0;X[1]=0;for(i=2;i<=40;i++){k=sqrt(i);for(j=2;j<=k;j++){if(i%j==0){X[i]=0;break;}}if(j>k) X[i]=1;
}
}void mima(int n,int m,int cur,int sum)
{int i;if(cur==n){for(i=0;i<=9;i++){if(X[sum+i]) count++;}return;}else for(i=0;i<=9;i++){if(cur<m){A[cur]=i;mima(n,m,cur+1,sum+i-A[cur-m+1]);}else{if(X[sum+i]){A[cur]=i;mima(n,m,cur+1,sum+i-A[cur-m+1]);}}}
}int main()
{is_zhishu();int T;scanf("%d",&T);while(T--){int n,m;count=0;scanf("%d%d",&n,&m);mima(n,m,1,0);printf("%d\n",count);}return 0;
}