Recursive Queries [ICM Technex 2018 and Codeforces Round #463 (Div. 1 + Div. 2, combined) B]

http://codeforces.com/contest/932/problem/B

f(n) := nの非ゼロの桁の総積
g(n) := n (n ＜ 10)
g(n) := g(f(n))
と定義する。
Q個の以下のクエリを処理せよ。
「x=[L,R]の中でg(x)=Kとなる個数を求めよ」

前提知識

• 累積和

解法

http://codeforces.com/contest/932/submission/35298768

種類ごとに分ける累積和。
まずは、関数fとgの引数は最大10^6なので、関数fとgの値を全て用意しよう。
次に、次の累積和を用意する
「sm[i][j] := x=[0,j]の中でf(x)=iとなる個数」
これを用意したら、答えはsm[K][R] - sm[K][L - 1]である。

int f[1010101], g[1010101];
int sm[10][1010101];
//---------------------------------------------------------------------------------------------------
void _main() {
    rep(i, 0, 1010101) {
        int x = i;
        int sm = 1;
        while (x) {
            int d = x % 10;
            x /= 10;
            if (d) sm *= d;
        }
        f[i] = sm;
    }

    rep(i, 0, 1010101) {
        if (i < 10) g[i] = i;
        else g[i] = g[f[i]];
    }

    rep(i, 0, 1010101) sm[g[i]][i] = 1;
    rep(i, 0, 10) rep(j, 1, 1010101) sm[i][j] += sm[i][j - 1];

    int Q; cin >> Q;
    rep(q, 0, Q) {
        int l, r, k; cin >> l >> r >> k;

        int ans = sm[k][r] - sm[k][l - 1];
        printf("%d\n", ans);
    }
}