// 603 数数2.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
/*
http://oj.daimayuan.top/course/5/problem/247
读入 l,r,请求出 [l,r]中有多少个数字满足数字的各个数位的和是质数。
输入格式
一行两个整数 l,r。
输出格式
一行一个整数表示答案。
样例输入
1 100
样例输出
37
数据范围
对于 100%的数据,保证 1≤l≤r≤1016。
*/
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <memory.h>
#include <set>
#include <vector>
using namespace std;
const int N = 20;
long long dp[N][N][210];
set<int> primes;
long long l, r;
void init() {
for (int i = 2; i <= 200; i++) {
int flag = 1;
for (int j = 2; j * j <= i; j++) {
if (j != i && i % j == 0) {
flag = 0;
break;
}
}
if (1 == flag) {
primes.insert(i);
}
}
for (int i = 0; i <= 9; i++) dp[0][i][i] = 1;
for (int x = 1; x < N; x++) {
for (int i = 0; i <= 9; i++) {
int de = 1;
for (int j = 0; j <= 9; j++) {
for (int k = 0; k <= 200; k++) {
if(k>=i){
dp[x][i][k] += dp[x - 1][j][k - i];
}
}
}
}
}
return;
}
long long solve(long long u) {
long long cu = u;
vector<int> v;
while (cu) {
v.push_back(cu % 10);
cu /= 10;
}
long long ans = 0; int presum = 0;
for (int i = v.size() - 1; i >= 0; i--) {
int t = v[i];
for (int j = t - 1; j >= 0; j--) {
if (i == v.size() - 1 && j == 0) continue;
for(int k= 0 ;k<=200;k++){
if(primes.count(k+ presum) !=0)
ans += dp[i][j][k];
}
}
if (primes.count(t + presum) && i==0) {
ans++;
}
presum += t;
}
for (int i = v.size() - 2; i >= 0; i--) {
for (int j = 1; j <= 9; j++) {
for (int k = 0; k <= 200; k++) {
if (primes.count(k)) {
ans += dp[i][j][k];
}
}
}
}
return ans;
}
int main()
{
init();
cin >> l >> r;
//cout << solve(r) << endl;
cout << solve(r) - solve(l - 1) << endl;
return 0;
}
标签:数数,int,long,247,dp,include,cu
From: https://www.cnblogs.com/itdef/p/18524934