304906: CF932B. Recursive Queries
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Recursive Queries
题意翻译
定义如下函数: $f(x)$ 为 $x$ 各位上非 $0$ 数字之积,$g(x)=\begin{cases}x&x<10\\g(f(x))&x\ge 10\end{cases}$ $Q$ 组询问。每问求使得 $g(x)=k$ 的 $x(x\in[l,r])$ 的个数。题目描述
Let us define two functions $ f $ and $ g $ on positive integer numbers. ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF932B/5ea922a7608f7b43dbb7e14356bf3e8277d2c765.png)![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF932B/c3f9cee55fe0b74363392f2f9845da5254de38c3.png) You need to process $ Q $ queries. In each query, you will be given three integers $ l $ , $ r $ and $ k $ . You need to print the number of integers $ x $ between $ l $ and $ r $ inclusive, such that $ g(x)=k $ .输入输出格式
输入格式
The first line of the input contains an integer $ Q $ ( $ 1<=Q<=2×10^{5} $ ) representing the number of queries. $ Q $ lines follow, each of which contains 3 integers $ l $ , $ r $ and $ k $ $ (1<=l<=r<=10^{6},1<=k<=9) $ .
输出格式
For each query, print a single line containing the answer for that query.
输入输出样例
输入样例 #1
4
22 73 9
45 64 6
47 55 7
2 62 4
输出样例 #1
1
4
0
8
输入样例 #2
4
82 94 6
56 67 4
28 59 9
39 74 4
输出样例 #2
3
1
1
5