51nod 1230：幸运数

题目链接：

题目大意：如果一个数各个数位上的数字之和是质数，并且各个数位上的数字的平方和也是质数，则称它为幸运数。例如：120是幸运数，因为120的数字之和为3，平方和为5，均为质数，所以120是一个幸运数字。给定x，y，求x，y之间（ 包含x，y，即闭区间[x,y]）有多少个幸运数。

数位DP

代码如下：

1 #include 
     
       2 #include 
      
        3 using namespace std; 4 typedef long long ll; 5 const int maxn=22; 6 int dig[maxn],prime[1459]={
   0},num_prime=0,T; 7 ll f[maxn][163][1459],x,y; 8 bool p[1459]={
   1,1}; 9 ll dfs(int pos,int sum,int sqrsum,int limit){10     if (pos<0) return (!p[sum])&&(!p[sqrsum]);11     if (!limit&&f[pos][sum][sqrsum]!=-1) return f[pos][sum][sqrsum];12     ll res=0;13     int last=limit?dig[pos]:9;14     for (int i=0;i<=last;i++){15         res+=dfs(pos-1,sum+i,sqrsum+i*i,limit&&(i==last));16     }17     if (!limit) f[pos][sum][sqrsum]=res;18     return res;19 }20 ll solve(ll n){21     int len=0;22     while (n){23         dig[len++]=n%10;24         n/=10;25     }26     return dfs(len-1,0,0,1);27 }28 void init(){29     memset(f,-1,sizeof(f));30     for(long i=2;i<1459;i++){31         if(!p[i])prime[num_prime++]=i;32         for(long j=0;j
       
        <1459;j++){33             p[i*prime[j]]=1;34             if(!(i%prime[j]))break;35         }36     }37 }38 int main(void){39     init();40     scanf("%d",&T);41     while(T--){42         scanf("%lld%lld",&x,&y);43         printf("%lld\n",solve(y)-solve(x-1));44     }45 }