自动搬运

查看原文

来自洛谷，原作者为

	Silence_water 天天向上，追逐梦想

搬运于2025-08-24 22:20:25，当前版本为作者最后更新于2021-06-23 16:25:44，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目传送门

本题巨大的数据范围仿佛在告诉我们这是一道数位 DP，但是在阅读完题面后却发现自己束手无措。

于是开始写无脑暴力，枚举每个数，然后求位数积，判断。这显然是一种偏离正解的方法，无法进一步进行优化。

换一种想法，如果枚举数不可行，就枚举位数积。记 $S$ 为 $x$ 的位数积，显然对于相同的 $S$ 会对应多个 $x$。如果通过枚举每一位上的数来确定 $S$，无异于暴力。因此考虑两种枚举 $S$ 方法：

1. 枚举 $S$ 中每个数字出现的个数。

   如果直接枚举出现次数，相当于把 $18$ 个位置放进 $10$ 个框，总情况数为 $\mathrm{C_{27}^{9}=4686825}$，无法再继续进行统计对应 $x$ 的个数，必然超时。

   考虑优化。一个较为显然的结论就是 $S\le x$。又 $1\le A\le B\le 10^{18}$，所以 $S\times x\le 10^{18}$，从而推出 $S\le 10^9$。

   还有一个结论就是，如果 $x$ 中某一数位上的数为 $0$，那么 $S\times x=0<A\le B$，一定不存在于 $[A,B]$ 内。

   因此我们只需考虑把 $9$ 个位置放进 $9$ 个框，总情况数就减为 $\mathrm{C_{17}^8=24310}$，使得后续的统计成为可能。

2. 枚举 $S$ 中 $2,3,5,7$ 四个质数出现的个数。

   由于 $S$ 必然是由 $0-9$ 这些数的幂相乘而得的，在第 $1$ 种方法中我们已经得出 $0$ 毫无作用。因此剩下的数除 $1$ 以外在分解质因数后一定是由上述四个质数组成，从而可以推出 $S$ 可以表示成 $2^a\times 3^b\times 5^c\times 7^d$ 的形式的。（$\mathrm{a,b,c,d\in N}$）

   又因为 $S\le 10^9$，因此 $a\le 29$，$b\le 18$，$c\le 12$，$d\le 10$。

   通过相应枚举代码可以得出满足 $S\le 10^9$ 的四元组 $(a,b,c,d)$ 的个数为 $5194$ 种，为后续统计留了较多的时空。

这里着重讲解第 $2$ 种枚举方法后的统计。

首先通过 $S,A,B$ 我们可以得知 $x$ 的范围 $L$ 和 $R$。

void count(ll mul,int fac)
{
	if(mul>B/mul)return;
	if(fac==4)
	{
		ll L=(A-1ll)/mul+1ll;
		ll R=B/mul;
		ans+=solve(R)-solve(L-1);
		return;
	}
	count(mul,fac+1);
	cnt[fac]++;
	count(mul*c[fac],fac);
	cnt[fac]--;
}

然后考虑通过数位 DP 来求得在 $[L,R]$ 中满足条件的 $x$ 的个数。

设计状态 $\mathrm{dp[pos][cnt[0]][cnt[1]][cnt[2]][cnt[3]]}$，其中 $\mathrm{pos}$ 表示当前数位，$\mathrm{cnt[0-3]}$ 分别表示还需填入的 $2,3,5,7$ 的数量。

注意 $0$ 对答案的干扰。除了作为前导零以外，为了与上面枚举过程相契合，我们不能在数位上填 $0$。

ll ans=0;
if(lead)ans+=dfs(pos-1,limit&&a[pos]==0,true);
int up=limit?a[pos]:9;
for(int i=1;i<=up;i++)
{
	if(!enough(i))continue;
	work(i,-1);
	ans+=dfs(pos-1,limit&&i==up,false);
	work(i,1);
}
if(!limit&&!lead)DP=ans;
return ans;

注意 $1-9$ 每个数的组成，如 $6=2\times 3$，那么填入 $6$ 就会对应地消耗 $1$ 个 $2$ 和 $1$ 个 $3$。对应关系如下：

const int dig[10][4]={{0,0,0,0},//0位置无实际意义，无需理会
{0,0,0,0},{1,0,0,0},{0,1,0,0},//1 2 3
{2,0,0,0},{0,0,1,0},{1,1,0,0},//4 5 6
{0,0,0,1},{3,0,0,0},{0,2,0,0}};//7 8 9

统计部分要求无最高位限制和前导零。如果所有数位填完后，还要检查是否 $4$ 个质数都已填完。相应部分如下：

if(pos==0)return (!lead)&&check();
ll &DP=dp[pos][cnt[0]][cnt[1]][cnt[2]][cnt[3]];
if(!limit&&!lead&&DP!=-1)return DP;

本题讲解至此就告一段落了，上述代码块中个别函数请读者自行完成，如有疑问请评论提出，欢迎指正。