题目大意

如果一个数各个数位上的数字之和是质数，并且各个数位上的数字的平方和也是质数，则称它为幸运数。

例如：120是幸运数，因为120的数字之和为3，平方和为5，均为质数，所以120是一个幸运数字。

给定x，y，求x，y之间（ 包含x，y，即闭区间[x,y]）有多少个幸运数。

 

Input

第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 10000)第2 - T + 1行：每行2个数，X, Y中间用空格分割。(1 <= X <= Y <= 10^18)

Output

输出共T行，对应区间中幸运数的数量。

Input示例

21 20120 130

Output示例

41|

 

Solution

这一题显然可以这状态为dp[pos][sum][sum1][0/1]经典的数位dp，pos到第pos位

sum数位和maxsum=9*18，sum1平方和maxsum1=9*9*18，状态很少，但0/1不能

传递，所以每次只用重新算压在lim上的数的方案数就行了。记忆化搜索即可。

 

Code

1 #include
       
         2 #include
        
          3 #include
         
           4 #include
          
            5 #define fo(i,a,b) for(int i=a;i<=b;i++) 6 #define fd(i,a,b) for(int i=a;i>=b;i--) 7 #define fh(i,x) for(int i=head[x];i;i=next[i]) 8 typedef long long LL; 9 inline int max(int x,int y) {
     return (x
           
            '9') f=(ch=='-')?-1:f,ch=getchar();14     while(ch>='0'&&ch<='9') x=x*10+(ch-'0'),ch=getchar();return f*x;15 }16 const int N=2e3+50,MAXN=2e3;17 int prime[N],tot;18 LL dp[20][200][N],dig[20];19 bool isprime[N];20 void init() {21     memset(dp,-1,sizeof(dp));22     memset(isprime,1,sizeof(isprime));23     isprime[1]=false;24     for(int i=2;i<=MAXN;i++) {25         if(isprime[i])prime[++tot]=i;26         for(int j=1;j<=tot&&i*prime[j]<=MAXN;j++) {27             isprime[i*prime[j]]=false;28             if(i%prime[j]==0)break;29         }30     }31 }32 LL dfs(int pos,int sum,int sum1,bool flag) {33     if(pos<1) return (isprime[sum]&&isprime[sum1]);34     if(!flag&&dp[pos][sum][sum1]!=-1) return dp[pos][sum][sum1];35     int lim=(flag)?dig[pos]:9;36     LL res=0;37     fo(i,0,lim) res+=dfs(pos-1,sum+i,sum1+i*i,flag&&(i==lim));38     if(!flag) dp[pos][sum][sum1]=res;39     return res;40 }41 LL solve(LL x) {42     int len=0;43     while(x) dig[++len]=x%10,x=x/10;44     return dfs(len,0,0,1);45 }46 int main() {48     init();49     int T=read();50     while(T--) {51         LL x=read(),y=read();52         printf("%lld\n",solve(y)-solve(x-1));53     }54     return 0;55 }