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;
}
