Question

求教一道c语言的题目 感激不尽

小明的密码由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

求代码
输入 3 1 ，输出64，输入 4 1,输出64

Answer 1

#include<stdio.h>
#include<math.h>
#include<string.h>
int n,m,cnt;
int prime[45];
void Selectprime()
{//该函数用于选择素数,prime[i]=1,i为质数,否则不为质数
    memset(prime,0,sizeof(prime));
    int s,flag,i,j;
    for(i=2; i<45; i++)
    {
        flag=0;
        s=sqrt(i);
        for(j=2; j<=s; j++)
            if(i%j==0)
            {
                flag=1;
                break;
            }
        if(!flag)
            prime[i]=1;
    }
}
int Judge(int* a,int pos)
{//判断a数组中pos之前m个数的和是否为质数
    if(pos<m-1)return 1;
    int sum=0;
    int i,j=pos-m+1;
    for(i=pos; i>=j; i--)
        sum+=a[i];
    return prime[sum];
}
void Fill(int* a,int cur)
{
    int i;
    if(cur==n)
    {
        cnt++;
        return ;
    }
    for(i=0; i<=9; i++)
    {
        a[cur]=i;
        if(!Judge(a,cur))
            continue;
        Fill(a,cur+1);
    }
}
int main()
{
    Selectprime();
    int c;
    int a[20];
    scanf("%d",&c);
    while(c--)
    {
        cnt=0;
        scanf("%d%d",&n,&m);
        Fill(a,0);
        printf("%d\n",cnt);
    }
    return 0;
}

追问

不好意思，您的代码答案是正确的，可是oj提示我超时了，请问能不能把你的代码改一下呢，谢谢，拜托了，或者修改成打表的形式呢

追答

int main()
{
    Selectprime();
    int res[13][5];
    int a[20];
    memset(res,0,sizeof(res));
    for(int i=1;i<=12;i++)
    {
        for(int j=1;j<=4;j++)
        {
            cnt=0;
            n=i;
            m=j;
            Fill(a,0);
            res[i][j]=cnt;
        }
    }
    int c;
    scanf("%d",&c);
    while(c--)
    {
        scanf("%d%d",&n,&m);
        printf("%d\n",res[n][m]);
    }
    return 0;
}
//打表的,好像也超时吧..

追问

int d[13][5]; d[1][1] = 4; d[2][1] = 16; d[2][2] = 37;
根据你的代码 ，我把表打出来了 ，，万分感谢，这样就不会超时了，oh yeah!!!!

Answer 2

#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;

int in(){							//读入优化 ，加快读入速度 
	int x=0;char ch=getchar();
	while(ch>'9' || ch<'0')	ch=getchar();
	while(ch>='0' && ch<='9')	x=x*10+ch-'0',ch=getchar();
	return x;
}

#define maxn 101

int n,m,ans;
int a[maxn];
bool no_prime[maxn];

void get_prime(){					//筛选法求素数 
	int x=sqrt(maxn);
	no_prime[1]=no_prime[0]=true;
	for(int i=2;i<=x+1;i++)
		if(!no_prime[i])
			for(int j=i*i;j<=maxn;j+=i)
				no_prime[j]=true;
}

void prework(){
    n=in();m=in();ans=0;
}

void dfs(int t){
	if(t>n){						//如果到达n位说明构造成功 
		ans++;
		return;
	}
	int sum=0;
	if(t>=m)
		for(int i=t-1;i>=t-m;i--)
			sum+=a[i];				//计算前 m-1位的值 
	for(int i=0;i<=9;i++)
		if(!no_prime[sum+i]){		//如果加上这一位是一个质数才向下遍历 
			a[t]=i;
			dfs(t+1);
		}
		
}

void mainwork(){
	dfs(1);							//从第一位开始枚举，深度优先搜索 
	printf("%d\n",ans);
}

int main(){
	//freopen("x.in","r",stdin);
	int T=in();
	get_prime();
	while(T--){
    	prework();
    	mainwork();
	}
    return 0;
}

追问

不好意思，您的代码好像有个问题，输入 3 1 的话，有64种，输入为4 1的情况，应该输出256种，可是您的代码输出是61 和233种，能不能把你的代码再改一下呢，谢谢拜托了，感激不尽！！！

追答

程序39行....
        for(int i=t-1;i>t-m;i--) //sorry这里多算了一位，将>=改成> 就好啦