[BZOJ2757] [SCOI2012]Blinker的仰慕者

Description

Blinker 有非常多的仰慕者，他给每个仰慕者一个正整数编号。而且这些编号还隐藏着特殊的意义，即编号的各位数字之积表示这名仰慕者对Blinker的重要度。现在Blinker想知道编号介于某两个值A,B之间，且重要度为某个定值K的仰慕者编号和。

Input

输入的第一行是一个整数N，表示Blinker想知道的信息个数。
接下来的N行，每行有三个数，A,B,K。表示 Blinker想知道编号介于A和B之间的，重要度为K的仰慕者的编号和。

Output

输出N行，每行输出介于A和B之间，重要度为 K的仰慕者编号和。结果可能很大，模上20120427。

Sample Input

3
1 14 4
1 30 4
10 60 5
0<=K<=10^18

Sample Output

18
40
66
【样例解释】
第一组样例中，在 1到14之间各位数字之积等于 4的有 4和 14，故编号和为18。

HINT

【数据范围】
对于20%的数据，保证： 2<=A<=B<=1000000000，1<=N<=30
对于50%的数据，保证：2<=A<=B<=1000000000000000000，1<=N<=30
对于100%的数据，保证： 2<=A<=B<=1000000000000000000，1<=N<=5000

试题分析

~~十分优秀地通过这道题知道了数位dp可以不计录当前数字。。。~~
方法非常simple，就是发现合法乘积的个数很小，所以直接预处理压下来。
然后(f_{i,j})表示乘积为i，j位的数的个数，(s_{i,j})表示总和。
注意特判0的情况。

代码丢失。。。