#P11698. [ROIR 2025] 不完全质数

[ROIR 2025] 不完全质数

题目背景

翻译自 ROIR 2025 D1T2。$%标题解析 by GPT:在俄语中,**"простые числа"**(质数)是由**"простой"**(简单的、普通的)和**"число"**(数字、数)构成的短语,表示“质数”这一数学概念。当在 **"простые"** 后加上 **"-оват-"** 后缀(即变为 **"простоватые"**),这个词的含义就发生了变化。**"-оват-"** 是俄语中的一个后缀,用于形容词或名词,通常会带有一种轻微的、不完全的含义,或者带有一种贬义或降低的语气。**"-оват-"** 后缀通常表示某物处于某种状态,但并不是完全符合该状态或标准,带有一些“接近但不完全”的意味。它强调了某种特性,但并不完全具备。例如:- **"молодой"**(年轻的)变成 **"молодоватый"**(有点年轻、不完全年轻)。- **"сильный"**(强的)变成 **"сильноватый"**(有点强,但不完全强)。在这种情况下,**"простоватые"** 由 **"простой"**(简单的)加上 **"-оват-"** 后缀构成,表示“有点简单的”或者“接近简单的”,即“简单但不完全是质数”的意思。所以,**"простоватые числа"** 指的是“接近质数的数字”,即这些数字的数字乘积是质数,但并不完全符合质数的定义。$

题目描述

如果一个数字在十进制表示下的各位数字之积是一个质数,则称这个数为“不完全质数”。例如,1212 是一个不完全质数,因为 1×2=21 \times 2 = 2 是质数;但是 2929 不是不完全质数,因为 2×9=182 \times 9 = 18 不是质数。

现在,你需要计算出 [l,r][l,r] 的不完全质数的数量。

输入格式

第一行包含一个整数 ll1l101000001 \leq l \leq 10^{100000})。
第二行包含一个整数 rrlr10100000l \leq r \leq 10^{100000})。

请注意:输入中的数字非常大,无法直接存储在大多数编程语言的标准整型数据中,例如 C++。因此,需要以特殊的方式读取输入,例如将其作为字符串读取。

输出格式

输出一个整数,表示 [l,r][l,r] 的不完全质数的数量。

42
179
10

提示

本题使用 Subtask 捆绑测试。数据中 Subtask 0 是样例。

子任务 分数 特殊性质
11 19 19 1lr1061 \leq l \leq r \leq 10^6
22 2626 1lr10181 \leq l \leq r \leq 10^{18}
33 1212 l=1,r=10kl = 1, r = 10^k,其中 1k1051 \leq k \leq 10^5
44 1818 1lr1010001 \leq l \leq r \leq 10^{1000}
55 2525