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;
}