HDU XXXX：求[L,R]的素数数量（数位DP）

Problem G

Time Limit : 2000/1000ms (Java/Other) Memory Limit : 131072/131072K (Java/Other)

Total Submission(s) : 62 Accepted Submission(s) : 28

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

S number is the number which the sum of every digit is a prime number, such as number 98, 29. Output the number of

Input

First line contains

Output

For each case, output the number of

Sample Input

2
4 30
49 173

Sample Output

12
45

题意：找出[L,R]里面素数的总和，即求出[0,R]-[0,L-1]就可以了。
思路：因为数据范围在0~10^16那么大，所以不可以暴力了，考虑到每个位最多是9，那么最多15个9的话就是135个数那么多，因此我打了个判断135里面的数哪个是素数的表，然后就数位DP

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 using namespace std;
 5 #define N 20
 6 int bit[N];
 7 long long dp[N][200][2];
 8 int prime[200];
 9 
10 bool check(int x)
11 {
12     for(int i=2;i*i<=x;i++){
13         if(x%i==0) return false;
14     }
15     return x!=1;
16 }
17 
18 void P()
19 {
20     for(int i=2;i<=200;i++){
21         if(check(i)){
22              prime[i]=1;
23         }
24     }
25 }
26 //flag表示之前的数是否是上界的前缀（即后面的数能否任意填）。
27 //flag为 1 表示之前的数不是前缀，可以任意填
28 long long dfs(int pos,int st,int have,int flag)
29 {
30     if(!pos) return have;
31     if(flag&&dp[pos][st][have]!=-1) return dp[pos][st][have];
32     long long ans=0;
33     int u=flag?9:bit[pos];
34     for(int d=0;d<=u;d++){
35         ans+=dfs(pos-1,st+d,prime[st+d],!flag&&d==u);
36         //判断之前位置的和加上当前位置是否可以是一个素数
37     }
38     if(flag) dp[pos][st][have]=ans;
39     return ans;
40 }
41 
42 long long solve(long long s)
43 {
44     memset(bit,0,sizeof(bit));
45     int l=0;
46     while(s){
47         bit[++l]=s%10;
48         s/=10;
49     }
50     return dfs(l,0,0,0);
51 }
52 
53 int main()
54 {
55     int t;
56     cin>>t;
57     memset(prime,0,sizeof(prime));
58     P();
59     while(t--){
60         memset(dp,-1,sizeof(dp));
61         long long s1,s2;
62         cin>>s1>>s2;
63 //        cout<<solve(s2)<<" "<<solve(s1-1)<<endl;
64         cout<<solve(s2)-solve(s1-1)<<endl;
65     }
66     return 0;
67 }

。