题目传送门：P11698 [ROIR 2025] 不完全质数。

思路

使用类似前缀和的思想，将求 $[l,r]$ 不完全质数的个数，转化成 $[1,r]$ 不完全质数的个数减去 $[1,l-1]$ 不完全质数的个数。

我们考虑不完全质数的定义是十进制各位数字之积为质数，而质数的定义为除 $1$ 和本身没有其他因数的数，由此我们可以推得，这个十进制数有且仅有一位是质数，其余的位置都是一。

我们可以考虑数位 dp 了，设 $f_{i,limit,zs,qd}$ 表示现在处理到了第 $i$ 位，这一位取数是否限制，是否有一个质数出现，之前的数是否都是 $0$。

转移按照 $zs,qd$ 等取值分类讨论即可。

代码

在这里实现的是用记忆化搜索来做的数位 dp。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int b[N],c[N],a[N],d[N],n;
inline int read(){
	char c=getchar();
	int f=1,ans=0;
	while(c<48||c>57) f=(c==45?f=-1:1),c=getchar();
	while(c>=48&&c<=57) ans=(ans<<1)+(ans<<3)+(c^48),c=getchar();
	return ans*f;
}
int f[N][2][2][2];
inline bool check(int x){
	return x==2||x==3||x==5||x==7;
}
int dfs(int i,bool limit,bool zs,bool qd){
	if (i==n+1) return zs;
	if (~f[i][limit][zs][qd]) return f[i][limit][zs][qd];
	int now=limit?9:a[i];
	if (zs){
		if (now==0) return f[i][limit][zs][qd]=0;
		return f[i][limit][zs][qd]=dfs(i+1,limit||(1<now),zs,qd);
	} 
	else{
		if (qd){
			int ans=0;
			for (int j=0;j<=now;j++){
				if (j==0) ans+=dfs(i+1,limit||(j<now),zs,1);
				else if (j==1) ans+=dfs(i+1,limit||(j<now),zs,0);
				else if (check(j)) ans+=dfs(i+1,limit||(j<now),1,0);
			}
			return f[i][limit][zs][qd]=ans;	
		}
		else{
			int ans=0;
			for (int j=0;j<=now;j++){
				if (j==1) ans+=dfs(i+1,limit||(j<now),zs,0);
				else if (check(j)) ans+=dfs(i+1,limit||(j<now),1,0);
			}
			return f[i][limit][zs][qd]=ans;	
		}
	}
}
inline int calc(int n){
	::n=n;
	memset(f,-1,sizeof(f));
	return dfs(1,0,0,1);
}
main(){//由于数据范围很大，需要使用高精减
	string x;
	cin>>x;
	b[0]=x.size();
	for (int i=0;i<x.size();i++) b[i+1]=x[i]-48;
	cin>>x;
	c[0]=x.size();
	for (int i=0;i<x.size();i++) c[i+1]=x[i]-48;
	d[b[0]]=1;
	for (int i=b[0];i>0;i--){
		if (b[i]<d[i]) b[i]+=10,b[i-1]--;
		b[i]-=d[i];
	}
	for (int i=1;i<=b[0];i++) a[i]=b[i];
	int xx=calc(b[0]);
	for (int i=1;i<=c[0];i++) a[i]=c[i];
    cout <<calc(c[0])-xx;
	return 0;
}