自动搬运

查看原文

来自洛谷，原作者为

	matrixPower &Kevin1211 || 一只鸡块 || 坐标 CQ || 蛋五双修（最近主玩五）|| 关注被清了，原因：JC，要壶关的私信，无条件，先到先得

搬运于2025-08-24 23:09:35，当前版本为作者最后更新于2025-02-11 09:33:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

传送门

声明：

本题我的代码从 kunkunge 的 0 分代码调试而来，使用已经经得他本人同意。

非常好的数位 DP 题。

最近正好学了数位 DP，直接将这一道题拿来练手了。

从题目中可以得知，质数 $x$ 只能拆成 $1 \times x$，所以不完全质数的各位只能由 $1,2,3,5,7$ 构成，且质数最终只能出现一次。

输入是经典的 $l\sim r$，由于此题 $l$ 很大，无法快速算出 $l-1$（除非你想写高精），所以最终表达式是这样：$f(r)-f(l)+\operatorname{check(l)}$。其中 $\operatorname{check(l)}$ 表示 $l$ 是否为不完全质数，是则答案为 $1$，不是则答案为 $0$。

$\operatorname{check(l)}$ 很好计算，在此就不过多赘述。

接下来看到 $f(x)$ 如何计算。

考虑到求 $1 \sim x$ 中的个数与 $x$ 非常巨大，可以使用数位 DP 加记忆化。

而我写数位一般使用递归做法。定义递归函数 dfs，传 $p,lim,vis,st$ 这四个参数，分别表示现在算到了第 $p$ 位、$lim=1$ 则前面所有位置都顶着上限、$vis=1$ 则表示前面已经用过唯一的指数了，后面只能填 $1$ 了、$st=1$ 表示前面的位置都填的 $0$，即在前导零范围内。

消化了这几个参数后，就可以写题了。

在注意递归边界情况（严格按照我的顺序来写）：

1. $vis=1$，则质数已经用过了，后面的位置只能为 $1$。如果此时顶着上线，即 $lim=1$，我们需判断后面所有的位置能否都写下 $1$（比如说 $x=120,lim=1,vis=1$ 就不行）。

2. $p=-1$，由于数位已经用完了还没有用上质数，直接返回 $0$。

3. 如果 $dp_{p,vis} \ne -1$，则说明这次已经查找过了，直接返回这个值即可。

但注意到第一个条件中每次判断时写循环判断是否能全部写下 $1$，每次到这里都要循环，时间复杂度太过巨大，可以开数组 $b$，$b_i$ 表示 $i \sim 0$ 这几位能否存下 $1$。

具体不懂的可以参照代码。

#include <bits/stdc++.h>
#define int long long int
using namespace std;
int dp[100005][2],b[100005];
int f[] = {0, 1, 2, 3, 5, 7};
vector<int> num;
int dfs(int p, bool lim, bool vis, bool st)
{
	if(vis) 
	{
		if(p==-1) return 1;
		return !lim || b[p];
	}
    if (p == -1) return 0;
    if (!lim && ~dp[p][vis] && !st)
        return dp[p][vis];
    int up = lim ? num[p] : 9;
    int ans = 0;
    for (auto i : f)
    {
        if (i > up || (vis && i > 1)) break;
        if (st && !i)
        {
            ans += dfs(p - 1, (lim && (i == up)), 0, 1);
		}
        else
        {
            if (i == 0)	
                continue;
            ans += dfs(p - 1, (lim && (i == up)), i != 1, 0);
        }
    }
    if (!lim && !st)
        dp[p][vis] = ans;
    return ans;
}
int get(string s)
{
    reverse(s.begin(), s.end());
    num.clear();
    for (auto i : s)
        num.push_back(i - '0');
    b[0]=(num[0]>=1);
    for(int i=1;i<num.size();i++) 
	{
    	if(num[i]>=2) b[i]=1;
		else if(num[i]==1) b[i]=b[i-1]; 
		else b[i]=0;
	}
    return dfs(num.size() - 1, 1, 0, 1);
}
int check(string s)
{
    int flag = 0;
    for (auto i : s)
    {
        if(i!='1')
        {
        	if(i=='0' || i=='4' || i=='6' || i=='8' || i=='9') return 0;
        	if(flag) return 0;
        	flag=1;
		}
    }
    return flag;
}
signed main()
{
//	freopen("1.in","r",stdin);
    memset(dp, -1, sizeof(dp));
    string l, r;
    cin >> l >> r;
	int sum1=get(r);
	int sum2=get(l);
    cout << sum1 - sum2 + check(l);
    return 0;
}