CF932B Recursive Queries
题目描述
我们定义两个函数 $f$ 和 $g$ 在正整数集合上。
你需要处理 $Q$ 个询问。每个询问会给出三个整数 $l$、$r$ 和 $k$。你需要输出在区间 $[l, r]$ 内，满足 $g(x)=k$ 的整数 $x$ 的个数。
输入格式
输入的第一行包含一个整数 $Q$（$1 \leq Q \leq 2 \times 10^{5}$），表示询问的数量。
接下来的 $Q$ 行，每行包含三个整数 $l$、$r$ 和 $k$（$1 \leq l \leq r \leq 10^{6}, 1 \leq k \leq 9$）。
输出格式
对于每个询问，输出一行，表示该询问的答案。
说明/提示
在第一个样例中：
- $g(33)=9$，因为 $g(33)=g(3\times 3)=g(9)=9$。
- $g(47)=g(48)=g(60)=g(61)=6$。
- 在 $47$ 到 $55$ 之间没有满足条件的整数。
- $g(4)=g(14)=g(22)=g(27)=g(39)=g(40)=g(41)=g(58)=4$。
由 ChatGPT 4.1 翻译