Bài B - Codeforces Round #463 (Div.1+ Div.2)

Bài B:
Đề bài: Chúng ta định nghĩa hai hàm f và g trên tập số nguyên dương. Với $f(n)$ bằng tích các chữ số khác không của n và $g(n)=\left\{\begin{array}{I} n \text{ if }n<10\\ g(f(n)) \text{ otherwise }\end{array}\right.$.
 Chúng ta cần xử lý $Q$ truy vấn. Mỗi truy vấn, bạn sẽ được cho ba số nguyên l,r và k. Bạn cần in ra số các số x nằm giữa l và r thỏa mãn $g(x)=k$.
Đầu vào:
+ Dòng đầu tiên chứa số nguyên Q (1<=Q<=2x10^5) đại diện số truy vấn.
+ Q dòng tiếp theo, mỗi dòng chứa 3 số nguyên l,r và k (1<=l<=r<=10^6,1<=k<=9).
Đầu ra:
Với mỗi truy vấn, bạn in ra 1 dòng duy nhất chứa câu trả lời của truy vấn đó.
Ví dụ:
Đầu vào:
4
22 73 9
45 64 6
47 55 7
2 62 4
Đầu ra:
1
4
0
8
/**/
Đầu vào:
4
82 94 6
56 67 4
28 59 9
39 74 4
Đầu ra:
3
1
1
5.
Chú thích:
Ở ví dụ đầu tiên:
. g(33)=9 bởi vì g(33)=g(3x3)=g(9)=9.
. g(47)=g(48)=g(60)=g(61)=6
. Không có số nguyên nào thỏa mãn nằm giữa 47 và 55.
. g(4)=g(14)=g(22)=g(27)=g(39)=g(40)=g(41)=g(58)=4.
Hướng dẫn:
 Nếu chúng ta có thể chứng minh được rằng tất cả số nguyên n>=10, chúng ta có n>f(n) thì chúng ta có thể sử dụng bottum up dp đề tính g(n) cho tất cả các số nguyên 1<=n<=10^6 trong O(n). Và khi 1<=g(n)<=9, sử dụng mảng tổng parialcho mỗi giá trị g(n), chúng ta có thể trả lời truy vấn trong O(1).
Lời giải:

#include<cstdio>
#define MX 1000000
int g[MX+5],s[10][MX+5];
int main()
{
 int q,i,j,k;
 for(i=1;i<=MX;++i)
 {
  if(i<10){g[i]=i;continue;}
  for(j=i,k=1;j;j/=10)if(j%10)k*=j%10;
  g[i]=g[k];
 }
 for(i=1;i<10;++i)for(j=1;j<=MX;++j)s[i][j]=s[i][j-1]+(g[j]==i);
 for(scanf("%d",&q);q--;)
 {
  scanf("%d%d%d",&i,&j,&k);
  printf("%d\n",s[k][j]-s[k][i-1]);
 }
}