小明的密码

teach

小明的密码题解

小明的密码

题型: 编程题 语言: 无限制

问题描述

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

题解

1.简单方法：用欧拉筛先找出质数，然后递归

1
2
3
4
5
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
long v[100]= {0},prime[50]= {0},prin=0,n,m,ans,a[20];
void Euler()
{
    v[0]=1; v[1]=1;
    long i,j;
    for(i=2; i<=100; i++)
    {
        if(!v[i]) prime[prin++]=i;
        for(j=0; j<prin; j++)
        {
            if(i*prime[j]>100) break;
            v[i*prime[j]]=prime[j];
            if(!i%prime[j])
                break;
        }
    }
}
void solve(long w)
{
    long temp;
    if(w==n+1) {ans++; return;}
    if(w<m)
        for(long i=0; i<=9; i++)
        {
            a[w]=i;
            solve(w+1);
        }
    else for(long i=0; i<=9; i++)
    {
        temp=0;
        for(long j=m; j>1; j--)
            temp+=a[w-j+1];
        temp+=i;
        if(!v[temp]) {a[w]=i; solve(w+1);}
    }
    return;
}
main()
{
  long i,j,casen;
  scanf("%ld",&casen);
  Euler();
  while(casen--)
 {
  ans=0;
  scanf("%ld%ld",&n,&m);
  if(m!=1)
  for(i=0; i<=9; i++)
  {
      a[1]=i;
      solve(2);
  }
  else
  {
      ans=1;
      for(i=1; i<=n; i++)
      ans*=4;
  }
  printf("%ld\n",ans);
 }
}

2.用数位dp快速求解

写在最后

其实我们在面对同一道题的时候，往往会有多种解法，在这题里面，因为时间限制给的比较宽松，所以简单的递归就可以解决，当然正解应该是用数位dp。只能说，当你有更简单的方法水过去的时候，不要一开始就码正解。