题解

问题分析

题目要求统计区间 $[l, r]$ 中质乘数的数量。质乘数的定义是：该数各位数字的乘积为质数。

由于 $l$ 和 $r$ 的长度可达 $10^5$ 位，无法直接枚举所有数字。

关键观察

1. 质乘数的数字特征：

   • 数字乘积为质数 ⇒ 乘积只能是 $2, 3, 5, 7$ 这四个质数之一
   • 因此数字只能包含 $1$ 和至多一个质数字（$2,3,5,7$）

2. 数字组合规律：

   • 质乘数 = 若干个 $1$ + 至多一个质数字
   • 例如：$12$, $1113$, $1111117$ 等
   • 不能有多个非 $1$ 数字（否则乘积为合数）

算法思路

容斥计数法：

1. 按数字长度分层计数
2. 对于每个长度 $len$，质乘数的数量 = $4 \times len$（因为质数字有4种选择，可以放在任何位置）
3. 用前缀和数组 sum[i] 快速计算长度区间内的总数
4. 使用 Get() 函数处理边界情况，确保不重复不遗漏

核心函数说明

• dy()：检查 $r$ 本身是否为质乘数
• check(p, s)：检查从位置 $p+1$ 开始是否全为 $1$ 或更小
• Get(num, s)：计算字符串 $s$ 之前有多少个以 $num$ 为质数字的质乘数

算法步骤

1. 预处理前缀和数组
2. 计算所有长度在 $[len(l), len(r)]$ 之间的质乘数总数
3. 减去 $l$ 之前的多计数部分
4. 加上 $r$ 本身如果是质乘数的情况

复杂度分析

• 时间复杂度：$O(|r|)$，其中 $|r|$ 是数字的位数
• 空间复杂度：$O(|r|)$，存储前缀和数组

算法标签

• 组合数学
• 数位统计
• 字符串处理
• 容斥原理
• 大数处理