description:

s number is the number which the sum of every digit is a prime number,such as 98,29.output the number of S number in [l,r]

input

2

4   30

49  173

output

12

45

古人云：朝闻夕死，昨晚背gis代码的时候突然想到了卡了的水题正解

题意：求出给定区间的每个各个位上加和是质数的个数

dp[位数][各个位上的和]

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int dp[20][200];
bool isprime[200];
void init()
{
    memset(isprime,0,sizeof(isprime));
    isprime[2]=isprime[3]=1;
    for(int i=4;i<=190;i++)
    {
        bool flag=1;
        for(int j=2;j<i&&flag;j++)
        {
            if(i%j==0)
            {
                flag=0;
              //  isprime[i]=0;
                break;
            }
        }
        if(flag) isprime[i]=1;
    }
  //  for(int i=1;i<180;i++)if(isprime[i])printf("i=%d    ",i);
}
int num[20],len;
void cal(int n)
{
    len=0;
    memset(num,0,sizeof(num));
    memset(dp,-1,sizeof(dp));
    while(n)
    {
        num[++len]=n%10;
        n/=10;
    }
    num[len+1]=0;
}
int dfs(bool flag,int pos,int sum)
{
    if(pos==0)return isprime[sum]==1;
    if(!flag&&dp[pos][sum]!=-1)return dp[pos][sum];
    int ans=0;
    int maxn=flag?num[pos]:9;
    for(int i=0;i<=maxn;i++)
    {
         ans+=dfs(i==maxn&&flag,pos-1,sum+i);
    }
    if(!flag)dp[pos][sum]=ans;
    return ans;
}

int main()
{
    init();
    int t,l,r;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&l,&r);
        cal(l-1);
        int ansl=dfs(1,len,0);
        cal(r);
        int ansr=dfs(1,len,0);
        printf("%d\n",ansr-ansl);
    }
    return 0;
}