CF1985G

对于每一个数 $$$n$$$，设 $$$n_i$$$ 为其第 $$$i$$$ 个数位，则 $D(k\cdot n) = \sum D(k\cdot n_i)$，$k\cdot D(n)=k\sum D(n_i)$。

若 $$$D(k\cdot n)=k\cdot D(n)$$$，即满足对任意 $$$i$$$，有 $$$k\cdot n_i=D(k\cdot n_i)$$$，显然 $$$k\cdot n_i < 10$$$ 时满足，若 $$$k\cdot n_i > 0$$$，则显然 $$$k\cdot n_i>D(k\cdot n_i)$$$，则当且仅当数 $$$n$$$ 任意数位乘 $$$k$$$ 后不进位时满足。则对于每个数位，有 $$$\left\lfloor\dfrac{10}{k}\right\rfloor$$$ 选择，则对于一个 $$$n$$$ 位数，共有 $$$n^{\lfloor\frac{10}{k}\rfloor} - 1$$$ 种可能（排除 $0$）。

因此对于计算满足区间 $$$[10^l,10^r)$$$ 中的答案可变为计算满足 $$$[0,10^r)$$$ 减去满足 $$$[0,10^l)$$$ 的数量，而对于在 $$$[0,10^r)$$$ 中满足的数量，则答案为 $$$r^{\lfloor\frac{10}{k}\rfloor}-l^{\lfloor\frac{10}{k}\rfloor}$$$ 种。

$$$\texttt{CODE}$$$

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;

template <typename T> void read(T &x) {
	char ch = getchar();
	int sgn = 1; x = 0;
	while (!isdigit(ch)) {
		if (ch == '-') sgn = -1;
		ch = getchar();
	}
	while (isdigit(ch)) {
		x = (x << 3) + (x << 1) + (ch ^ 48);
		ch = getchar();
	}
	x *= sgn;
}

const ll mod = 1e9 + 7;

ll qpow(int a, ll b) {
	if (b == 0) return 1;
	ll res = 1, base = a;
	while (b) {
		if (b & 1) res *= base, res %= mod;
		base *= base, base %= mod;
		b >>= 1;
	}
	return res;
}

int main() {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	int t; read(t);
	while (t--) {
		ll l, r, k; read(l), read(r), read(k);
		if (k >= 10) printf("0\n");
		else {
			printf("%lld\n", (((qpow(10 / k, r) - qpow(10 / k, l)) % mod) + mod) % mod);
		}
	}
	return 0;
}