51nod1230 幸运数 (数位dp)

2018年03月05日 10点热度 0人点赞 0条评论

题目来源: HackerRank
基准时间限制:1 秒 空间限制:131072 KB 分值: 320 难度:7级算法题

51nod1230 幸运数 (数位dp) 收藏

51nod1230 幸运数 (数位dp) 关注
如果一个数各个数位上的数字之和是质数,并且各个数位上的数字的平方和也是质数,则称它为幸运数。
例如: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示例
2
1 20
120 130
Output示例
4
1

/*记忆化搜索
和最大为18*9=162,平方和最大为162*9=1458
dp[i][j][k]的意思为后i位和为j平方和为k的组成的个数(不被限制)
*/
#include
#include
#include
#include
using namespace std;
long long dp[20][165][1500],x,y;
int T,vis[2000]= {1,1},p[20];
long long dfs(int pos,int limit,int sum,int sqt_sum) {
	if(pos<0) return !vis[sum]&&!vis[sqt_sum];
	if(!limit&&dp[pos][sum][sqt_sum]!=-1) return dp[pos][sum][sqt_sum];
	int last=limit?p[pos]:9;
	long long ret=0;
	for(int i=0; i<=last; ++i) {
		ret+=dfs(pos-1,limit&&(i==last),sum+i,sqt_sum+i*i);
	}
	if(!limit)dp[pos][sum][sqt_sum]=ret;
	return ret;
}
long long solve(long long t) {
	int pos=0;
	while(t) {
		p[pos++]=t%10;
		t/=10;
	}
	return dfs(pos-1,1,0,0);
}
int main() {
	memset(dp,-1,sizeof(dp));
	for(int i=2; i*i<2000; ++i)
		if(!vis[i])
			for(int j=i*i; j<2000; j+=i)
				vis[j]=1;
	scanf("%d",&T);
	while(T--) {
		scanf("%lld%lld",&x,&y);
		printf("%lldn",solve((long long)y)-solve((long long)x-1));
	}
	return 0;
}

未经允许不得转载!51nod1230 幸运数 (数位dp)

update

纸上得来终觉浅, 绝知此事须躬行。