C++ 解法, 执行用时: 281ms, 内存消耗: 5376K, 提交时间: 2021-10-23 14:17:53

#include<cstdio>
#include<map>
typedef long long LL;
std::map<LL, int>m;
const int N = 5e4, P = 20120427;
int pw[21], bit[21], g[21][N], f[21][N], af[21], ag[21], tp, L;
long long K, st[N];
void Up(int &a, int b) {a += b; if(a >= P) a -= P;}
void Pre() {
    pw[0] = 1; for(int i = 1;i <= 20; ++i) pw[i] = pw[i - 1] * 10 % P;
    for(int i = 0;i <= 9; ++i) {
        m[i] = ++tp; st[++L] = i;
        f[1][tp] = 1; g[1][tp] = i;
    }
    for(int i = 1, nL = L;i <= 18; ++i, L = nL)
        for(int j = 1;j <= L; ++j) {
            LL x = st[j]; int pr = m[x];
            for(int k = 0;k <= 9; ++k) {
                if(!m[x * k]) st[++nL] = x * k, m[x * k] = ++tp; 
                int nx = m[x * k]; Up(f[i + 1][nx], f[i][pr]);
                Up(g[i + 1][nx], (1LL * f[i][pr] * pw[i] * k + g[i][pr]) % P);
            }
        }
    for(int i = 1;i < 20; ++i)
        for(int j = 1;j <= L; ++j)
            Up(af[i], f[i][j]), Up(ag[i], g[i][j]);
}
int Dfs0(int i, int s, bool Z, bool e, bool z) {
    if(!i) return Z ? s : 0;
    if(!e && !z) {
        int A = !Z ? f[i][1] : af[i], B = !Z ? g[i][1] : ag[i];
        return (1LL * s * A % P * pw[i] + B) % P;
    }
    int end = e ? bit[i] : 9, r = 0;
    for(int v = 0;v <= end; ++v) 
        Up(r, Dfs0(i - 1, (s * 10 + v) % P, Z | !v & !z, e && (v == end), z && !v));
    return r;
}
int Dfs(int i, int s, LL K, bool e, bool z) {
    if(!i) return K == 1 ? s : 0;
    int t = m[K]; if(!t) return 0;
    if(!e && !z) return (1LL * s * f[i][t] % P * pw[i] + g[i][t]) % P;
    int end = e ? bit[i] : 9, r = 0;
    if(z) Up(r, Dfs(i - 1, s, K, e && !end, 1));
    for(int v = 1;v <= end; ++v) 
        if(!(K % v)) Up(r, Dfs(i - 1, (s * 10 + v) % P, K / v, e && (v == end), 0));
    return r;
}
int Cal(long long x) {
    int tp = 0; for(;x; x /= 10) bit[++tp] = x % 10;
    if(K != 0) return Dfs(tp, 0, K, 1, 1);
    else return Dfs0(tp, 0, 0, 1, 1);
}
int main() {
    Pre();
    int T; for(scanf("%d", &T); T--; ) {
        LL A, B; scanf("%lld%lld%lld", &A, &B, &K);
        printf("%d\n", (Cal(B) - Cal(A - 1) + P) % P);
    }
    return 0;
}